takewhile pattern lists drop haskell performance linked-list append idiomatic

pattern - take haskell



Idiomático eficiente Haskell append? (12)

List y el operador de contras (:) son muy comunes en Haskell. Contras es nuestro amigo. Pero a veces quiero agregar al final de una lista en su lugar.

xs `append` x = xs ++ [x]

Esto, tristemente, no es una forma eficiente de implementarlo.

Escribí el triángulo de Pascal en Haskell, pero tuve que usar el anti-idioma ++ [x] :

ptri = [1] : mkptri ptri mkptri (row:rows) = newRow : mkptri rows where newRow = zipWith (+) row (0:row) ++ [1]

Iho, este es un triángulo de Pascal muy agradable de leer y todo, pero el anti-idioma me molesta. ¿Puede alguien explicarme (e, idealmente, señalarme un buen tutorial) sobre cuál es la estructura de datos idiomática para los casos en los que desea anexar al final de manera eficiente? Espero tener una belleza parecida a la lista en esta estructura de datos y sus métodos. O, alternativamente, explíqueme por qué este anti-idioma en realidad no es tan malo para este caso (si usted cree que tal es el caso).

[edit] La respuesta que más me gusta es Data.Sequence , que sí tiene una "belleza parecida a la de una lista cercana". No estoy seguro de cómo me siento sobre el rigor requerido de las operaciones. Sugerencias adicionales e ideas diferentes son siempre bienvenidas.

import Data.Sequence ((|>), (<|), zipWith, singleton) import Prelude hiding (zipWith) ptri = singleton 1 : mkptri ptri mkptri (seq:seqs) = newRow : mkptri seqs where newRow = zipWith (+) seq (0 <| seq) |> 1

Ahora solo necesitamos que List sea una clase, de modo que otras estructuras puedan usar sus métodos como zipWith sin ocultarlo de Prelude ni calificarlo. :PAG

Escribí un ejemplo del enfoque ShowS @ geekosaurio. Puedes ver muchos ejemplos de ShowS en el preludio .

ptri = []:mkptri ptri mkptri (xs:ys) = (newRow xs []) : mkptri ys newRow :: [Int] -> [Int] -> [Int] newRow xs = listS (zipWith (+) xs (0:xs)) . (1:) listS :: [a] -> [a] -> [a] listS [] = id listS (x:xs) = (x:) . listS xs

[edit] Como la idea de @ Dan, reescribí newRow con zipWithS.

newRow :: [Int] -> [Int] -> [Int] newRow xs = zipWithS (+) xs (0:xs) . (1:) zipWithS :: (a -> b -> c) -> [a] -> [b] -> [c] -> [c] zipWithS z (a:as) (b:bs) xs = z a b : zipWithS z as bs xs zipWithS _ _ _ xs = xs

Algo así como esta recurrencia explícita evita que agregues "anti-idioma". Aunque, no creo que sea tan claro como tu ejemplo.

ptri = []:mkptri ptri mkptri (xs:ys) = pZip xs (0:xs) : mkptri ys where pZip (x:xs) (y:ys) = x+y : pZip xs ys pZip [] _ = [1]

Chris Okasaki tiene un diseño para una cola que aborda este problema. Consulte la página 15 de su tesis http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

Es posible que necesite adaptar el código ligeramente, pero el uso de reversa y mantener dos partes de la lista le permite trabajar de manera más eficiente en promedio .

Además, alguien puso un código de lista en el lector de mónadas con operaciones eficientes. Lo admito, realmente no lo seguí, pero pensé que podría resolverlo si me concentraba. Resulta que fue Douglas M. Auclair en Monad Reader número 17 http://themonadreader.files.wordpress.com/2011/01/issue17.pdf

Me di cuenta de que la respuesta anterior no aborda directamente la pregunta. Entonces, para risitas, aquí está mi respuesta recursiva. Siéntete libre de destrozarlo: no es bonito.

import Data.List ptri = [1] : mkptri ptri mkptri :: [[Int]] -> [[Int]] mkptri (xs:ys) = mkptri'' xs : mkptri ys mkptri'' :: [Int] -> [Int] mkptri'' xs = 1 : mkptri'''' xs mkptri'''' :: [Int] -> [Int] mkptri'''' [x] = [x] mkptri'''' (x:y:rest) = (x + y):mkptri'''' (y:rest)

Dependiendo de su caso de uso, el método ShowS (que se ShowS través de la composición de la función) puede ser útil.

Si está buscando una solución de propósito general, ¿qué tal esto?

mapOnto :: [b] -> (a -> b) -> [a] -> [b] mapOnto bs f = foldr ((:).f) bs

Esto le da una definición alterna simple para el mapa:

map = mapOnto []

Podemos una definición similar para otras funciones basadas en foldr, como zipWith:

zipOntoWith :: [c] -> (a -> b -> c) -> [a] -> [b] -> [c] zipOntoWith cs f = foldr step (const cs) where step x g [] = cs step x g (y:ys) = f x y : g ys

Una vez más, derivar zipWith y zip con bastante facilidad:

zipWith = zipOntoWith [] zip = zipWith (/a b -> (a,b))

Ahora, si usamos estas funciones de propósito general, su implementación se vuelve bastante fácil:

ptri :: (Num a) => [[a]] ptri = [] : map mkptri ptri where mkptri xs = zipOntoWith [1] (+) xs (0:xs)

Si solo quieres append (concat) y snoc (contras a la derecha) baratos, una lista de Hughes, también llamada DList en Hackage, es la más simple de implementar. Si quieres saber cómo funcionan, mira el primer trabajo de Wrapper Worker de Andy Gill y Graham Hutton, el artículo original de John Hughes no parece estar en línea. Como otros han dicho anteriormente, ShowS es una lista Hughes / DList especializada en String.

Un JoinList es un poco más trabajo de implementar. Este es un árbol binario pero con una lista de API: concat y snoc son baratos y puedes mapearlo razonablemente: el DList en Hackage tiene una instancia funcionadora pero afirmo que no debería haberlo hecho: la instancia del functor tiene que metamorfarse dentro y fuera de una lista regular Si desea un JoinList, tendrá que hacer su propio - el de Hackage es mío y no es eficiente, ni está bien escrito.

Data.Sequence tiene contras y snoc eficientes, y es bueno para otras operaciones - take, drops, etc. que JoinList es lenta. Debido a que la implementación del árbol de dedo interno de Data.Sequence tiene que equilibrar el árbol, agregar es más trabajo que su equivalente JoinList. En la práctica, porque Data.Sequence está mejor escrito, espero que supere el rendimiento de mi JoinList para agregar.

En su código para el Triángulo de Pascal, ++ [x] no es realmente un problema. Como de todos modos tiene que generar una nueva lista en el lado izquierdo de ++, su algoritmo es intrínsecamente cuadrático; no se puede hacer asintóticamente más rápido simplemente evitando ++.

Además, en este caso particular, cuando compila -O2, las reglas de fusión de lista de GHC (deberían) eliminar la copia de la lista que normalmente crearía ++. Esto se debe a que zipWith es un buen productor y ++ es un buen consumidor en su primer argumento. Puede leer sobre estas optimizaciones en la Guía del usuario de GHC .

No necesariamente llamaría a tu código "anti-idomatic". A menudo, más claro es mejor , incluso si eso significa sacrificar unos pocos ciclos de reloj.

Y en su caso particular, el apéndice al final en realidad no cambia la gran complejidad de tiempo O-O! Evaluar la expresión

zipWith (+) xs (0:xs) ++ [1]

tomará una length xs proporcional de length xs y ninguna estructura de datos de secuencia elegante va a cambiar eso. En todo caso, solo el factor constante se verá afectado.

Tenga en cuenta que lo que parece ser una mala asintonía podría no serlo, porque está trabajando en un lenguaje perezoso. En un lenguaje estricto, agregar al final de una lista vinculada de esta manera siempre sería O (n). En un lenguaje perezoso, es O (n) solo si realmente recorre hasta el final de la lista, en cuyo caso habría gastado O (n) esfuerzo de todos modos. Entonces, en muchos casos, la pereza lo salva.

Esto no es una garantía ... por ejemplo, k añade seguido de un recorrido que aún se ejecutará en O (nk) donde podría haber sido O (n + k). Pero cambia la imagen un poco. Pensar en el rendimiento de las operaciones individuales en términos de su complejidad asintótica cuando el resultado es forzado inmediatamente no siempre le da la respuesta correcta al final.

otra forma sería evitar la concatenación simplemente usando listas infinitas:

ptri = zipWith take [0,1..] ptri'' where ptri'' = iterate stepRow $ repeat 0 stepRow row = 1 : zipWith (+) row (tail row)

Puede representar una lista como una función para crear una lista desde []

list1, list2 :: [Integer] -> [Integer] list1 = /xs -> 1 : 2 : 3 : xs list2 = /xs -> 4 : 5 : 6 : xs

Luego puede agregar fácilmente listas y agregarlas a cualquier extremo.

list1 . list2 $ [] -> [1,2,3,4,5,6] list2 . list1 $ [] -> [4,5,6,1,2,3] (7:) . list1 . (8:) . list2 $ [9] -> [7,1,2,3,8,4,5,6,9]

Puede volver a escribir zipWith para devolver estas listas parciales:

zipWith'' _ [] _ = id zipWith'' _ _ [] = id zipWith'' f (x:xs) (y:ys) = (f x y :) . zipWith'' f xs ys

Y ahora puedes escribir ptri como:

ptri = [] : mkptri ptri mkptri (xs:yss) = newRow : mkptri yss where newRow = zipWith'' (+) xs (0:xs) [1]

Llevándolo más lejos, aquí hay un trazador de líneas que es más simétrico:

ptri = ([] : ) . map ($ []) . iterate (/x -> zipWith'' (+) (x [0]) (0 : x [])) $ (1:)

O esto es más simple aún:

ptri = [] : iterate (/x -> 1 : zipWith'' (+) (tail x) x [1]) [1]

O sin zipWith ''(mapAccumR está en Data.List):

ptri = [] : iterate (uncurry (:) . mapAccumR (/x x'' -> (x'', x+x'')) 0) [1]