opciones - pattern matching haskell

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

Question

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

1. Do length y (!!) (por ejemplo) tienen que iterar a través de la lista?
2. Si es así, ¿se almacenan en caché sus valores de alguna manera (es decir, si invoco 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 comprensiones de la lista? (es decir, para fib = 1:1:zipWith (+) fib (tail fib) , ¿se calculará recursivamente cada valor, o se basará en el valor calculado anterior?)

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

Answer 1

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

GHC no realiza la eliminación de subexpresión común completa . 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 en -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 aaaaaaaaa llama a GHC.List.$wlen dos veces.

(De hecho, debido a que x necesita ser retenido en aaaaaaaaa , es más de 2 x más lento que bbbbbbbbb ).

Answer 2

Las listas no tienen un tratamiento operativo especial en Haskell. Se definen como:

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

Solo con alguna notación especial: [a] para la 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 unidas individualmente. Debido a la pereza, a menudo se usan como iteradores. sum [1..n] 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 al n. ° 4: todos los valores 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 lo definió de esta manera aparentemente equivalente:

-- 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))

(Tómese un momento para notar la similitud con su definición)

Entonces, los resultados no se comparten y se accede al n-ésimo número de fibonacci en el tiempo O (fib n) (que es exponencial). Puede convencer a las funciones para que se compartan con una biblioteca de memorización como data-memocombinators .

Answer 3

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

1. length y (!!) DO tienen que iterar a través de la lista.

2. No creo que haya optimizaciones especiales para las listas, pero hay una técnica que se aplica a todos los tipos de datos.

   Si tienes algo como

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

   entonces la length xs se calculará dos veces.

   Pero si en cambio tienes

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

   entonces solo se computará 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 alcance. (El lenguaje no requiere esto, pero así es como entiendo que se comportan las implementaciones).