¿Cómo se implementan las listas en Haskell (GHC)?

Question

Tenía curiosidad acerca de algunos detalles de implementación exactos de las listas en Haskell (las respuestas específicas de GHC son buenas): ¿son listas vinculadas ingenuas o tienen alguna optimización especial? Más específicamente:

1. hacer length y (!!) (por ejemplo) tienen que recorrer la lista?
2. Si es así, ¿se almacenan en caché sus valores de alguna manera (es decir, si llamo a length dos veces, tendrá que iterar ambas veces)?
3. ¿El acceso a la parte posterior de la lista implica iterar a través de toda la lista?
4. ¿Se han memorado las listas infinitas y las listas de comprensión? (Es decir, por fib = 1:1:zipWith (+) fib (tail fib), cada valor se calculará recurrentemente, o va a depender del valor calculado anterior?)

Cualquier otro detalle de implementación interesante sería muy apreciado. ¡Gracias por adelantado!

Answer 1

Las listas tienen ningún tratamiento especial de funcionamiento en Haskell. Se definen como:

data List a = Nil | Cons a (List a) 

Sólo con un poco de notación especial: [a] para List a, [] para Nil y (:) para Cons. Si definió lo mismo y redefinió todas las operaciones, obtendría exactamente el mismo rendimiento.

Por lo tanto, las listas de Haskell están enlazadas individualmente. Debido a la pereza, a menudo se usan como iteradores. sum [1..n] se ejecuta en un espacio constante, porque los prefijos no utilizados de esta lista se recopilan como basura a medida que avanza la suma, y ​​las colas no se generan hasta que se necesiten.

En cuanto a # 4: todos los valores de en Haskell se memorizan, con la excepción de que las funciones no mantienen una tabla de notas para sus argumentos. Por lo tanto, cuando defina fib como lo hizo, los resultados se almacenarán en caché y se accederá al n-ésimo número de fibonacci en el tiempo O (n). Sin embargo, si ha definido de esta manera aparentemente equivalentes:

-- Simulate infinite lists as functions from Integer 
type List a = Int -> a 

cons :: a -> List a -> List a 
cons x xs n | n == 0 = x 
      | otherwise = xs (n-1) 

tailF :: List a -> List a 
tailF xs n = xs (n+1) 

fib :: List Integer 
fib = 1 `cons` (1 `cons` (\n -> fib n + tailF fib n)) 

(Tome un momento para señalar la similitud con su definición)

A continuación, los resultados no son compartidos y se accederá al número de Fibonacci número n de la O (fib n) (que es exponencial) tiempo. Puede convencer a las funciones para que se compartan con una biblioteca de memorización como data-memocombinators.

Answer 2

Por lo que yo sé (no sé cuánto de esto es GHC-específica)

1. length y (!!) tienen que recorrer la lista.

2. No creo que haya ninguna optimización especial para las listas, pero hay una técnica que se aplica a todos los tipos de datos.

   Si usted tiene algo así como

   foo xs = bar (length xs) ++ baz (length xs) 
   

   continuación length xs se computará el doble.

   Pero si por el contrario tiene

   foo xs = bar len ++ baz len 
       where len = length xs 
   

   entonces sólo será calculado una vez.

3. Sí.

4. Sí, una vez que se calcula parte de un valor con nombre, se conserva hasta que el nombre salga del ámbito. (El idioma no requiere esto, pero esto es como yo entiendo las implementaciones se comportan.)

Answer 3

Si es así, ¿se almacenan en caché sus valores de alguna manera (es decir, si invoco la longitud dos veces, ¿tendrá que iterar ambas veces)?

GHC does not perform full Common Subexpression Elimination. Por ejemplo:

{-# NOINLINE aaaaaaaaa #-} 
aaaaaaaaa :: [a] -> Int 
aaaaaaaaa x = length x + length x 

{-# NOINLINE bbbbbbbbb #-} 
bbbbbbbbb :: [a] -> Int 
bbbbbbbbb x = l + l where l = length x 

main = bbbbbbbbb [1..2000000] `seq` aaaaaaaaa [1..2000000] `seq` return() 

da sobre -ddump-simpl:

Main.aaaaaaaaa [NEVER Nothing] :: forall a_adp. 
            [a_adp] -> GHC.Types.Int 
GblId 
[Arity 1 
NoCafRefs 
Str: DmdType Sm] 
Main.aaaaaaaaa = 
    \ (@ a_ahc) (x_adq :: [a_ahc]) -> 
    case GHC.List.$wlen @ a_ahc x_adq 0 of ww_anf { __DEFAULT -> 
    case GHC.List.$wlen @ a_ahc x_adq 0 of ww1_Xnw { __DEFAULT -> 
    GHC.Types.I# (GHC.Prim.+# ww_anf ww1_Xnw) 
    } 
    } 

Main.bbbbbbbbb [NEVER Nothing] :: forall a_ado. 
            [a_ado] -> GHC.Types.Int 
GblId 
[Arity 1 
NoCafRefs 
Str: DmdType Sm] 
Main.bbbbbbbbb = 
    \ (@ a_adE) (x_adr :: [a_adE]) -> 
    case GHC.List.$wlen @ a_adE x_adr 0 of ww_anf { __DEFAULT -> 
    GHC.Types.I# (GHC.Prim.+# ww_anf ww_anf) 
    } 

Tenga en cuenta que las llamadas aaaaaaaaaGHC.List.$wlen dos veces.

(De hecho, debido x necesidades que deben conservarse en aaaaaaaaa, es más de 2 veces más lento que bbbbbbbbb.)