20 votos

Idiomáticas eficiente Haskell anexar?

Cualquier persona que se precie en Haskell sabe acerca de las listas y los contras operador (:).

Los contras es nuestro amigo. Pero a veces me quiere agregar al final de una lista en su lugar.

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

Esto, tristemente, no de una manera eficiente de implementar.

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

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

en mi humilde opinión, este es un hermoso legible triángulo de Pascal y todo, pero el anti-modismo me molesta. Puede que alguien me explique (e, idealmente, me apunte a un buen tutorial) en lo que el idiomáticas estructura de datos es para los casos donde se desea anexar a la final de manera eficiente? Yo estoy esperando cerca de la-lista-como la belleza en esta estructura de datos y sus métodos. O, alternativamente, que me explique por qué este anti-modismo es realmente no es tan malo para este caso (si usted cree que tal sea el caso).


[editar] La respuesta que más me gusta es Data.Sequence, que de hecho tiene "casi lista-como la belleza." No estoy seguro de cómo me siento acerca de la necesaria rigurosidad de las operaciones. Otras sugerencias e ideas diferentes son siempre bienvenidos.

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 sólo tenemos Lista para ser una clase, de manera que otras estructuras pueden utilizar sus métodos, como por ejemplo zipWith sin ocultar del Preludio, o de calificación. :P

13voto

Chris Smith Puntos 1310

Tenga en mente que lo que se ve pobre asymptotics en realidad podría no ser, porque está trabajando en un perezoso idioma. En un estricto lenguaje, añadiendo al final de una lista enlazada de esta manera siempre sería O(n). En un perezoso idioma, es O(n) sólo si realmente la travesía hasta el final de la lista,en cuyo caso se habría gastado O(n) esfuerzo de todos modos. Así, en muchos casos, la pereza salva.

Esto no es una garantía... por ejemplo, el k anexa seguido por un recorrido se podrá ejecutar en O(nk), que podría haber sido O(n+k). Pero sí cambia la imagen un poco. Pensando en el rendimiento de una sola operación, en términos de su complejidad asintótica cuando el resultado es inmediato forzado no siempre te dan la respuesta correcta en la final.

12voto

Ed'ka Puntos 3810

Estándar Sequence O(1) para la adición de "dos extremos" y O(log(min(n1,n2))) para general concatenación:

http://hackage.haskell.org/packages/archive/containers/latest/doc/html/Data-Sequence.html

La diferencia de las listas es que aunque Sequence es de estricta

9voto

David Powell Puntos 424

Algo como esto explícita la recursividad evita su anexar "anti-lenguaje". Aunque, creo que no es tan claro como el de 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]

5voto

geekosaur Puntos 26170

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

4voto

rampion Puntos 38697

otra forma de evitar la concatenación a todos por el solo uso de listas infinitas:

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

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X