Comment les listes sont-elles mises en œuvre dans Haskell (GHC)?

Question

J'étais juste curieux au sujet de certains exacte détails de mise en œuvre de listes en Haskell (GHC-spécifiques, les réponses sont à la fin)--sont-ils naïfs listes liées, ou ont-ils des optimisations spéciales? Plus précisément:

1. N' length et (!!) (par exemple) pour itérer sur la liste?
2. Si oui, sont leurs valeurs mises en cache en quelque sorte (c'est à dire, si je l'appelle, length deux fois, il va à la parcourir deux fois)?
3. L'accès à l'arrière de la liste impliquent une itération à travers l'ensemble de la liste?
4. Sont infinies des listes et des interprétations de la liste memoized? (c'est à dire, pour fib = 1:1:zipWith (+) fib (tail fib), sera chaque valeur doit être calculée de manière récursive, ou que ça va s'appuyer sur la précédente valeur calculée?)

Toute autre intéressants détails de mise en œuvre serait très apprécié. Merci à l'avance!

Answer 1

Les listes n'ont opérationnelle de traitement en Haskell. Ils sont définis comme:

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

Avec quelques une notation spéciale: [a] pour List a, [] pour Nil et (:) pour Cons. Si vous avez définies et redéfinies toutes les opérations, vous obtenez exactement les mêmes performances.

Ainsi, Haskell listes liée individuellement. À cause de la paresse, ils sont souvent utilisés comme des itérateurs. sum [1..n] s'exécute dans la constante de l'espace, parce que le solde non utilisé des préfixes de cette liste sont des ordures collectées comme la somme progresse, et les queues ne sont pas générés jusqu'à ce qu'ils sont nécessaires.

Comme pour le #4: toutes les valeurs en Haskell sont memoized, à l'exception des fonctions de ne pas garder un mémo de la table de leurs arguments. Ainsi, lorsque vous définissez fib comme vous l'avez fait, les résultats seront mis en cache et le n-ième nombre de fibonacci sera accessible en O(n) fois. Cependant, si vous en avez défini dans ce qui, apparemment, équivalent manière:

-- Simulate infinite lists as functions from Integer
cons x xs n | n == 0    = x
            | otherwise = xs (n-1)
tailF xs n = xs (n+1)

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

(Prendre un moment pour noter la similitude de votre définition)

Ensuite, les résultats ne sont pas partagées et le n-ième nombre de fibonacci sera accessible en O(fib n) (qui est exponentiel) de temps. Vous pouvez convaincre les fonctions à être partagées avec un memoization bibliothèque comme données memocombinators.

Answer 2

Autant que je sache (je ne sais pas comment cela est-GHC-spécifique)

1. length et (!!) N'ont pour parcourir la liste.

2. Je ne pense pas qu'il y a des optimisations pour les listes, mais il y a une technique qui s'applique à tous les types de données.

   Si vous avez quelque chose comme

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

   ensuite, length xs sera calculé deux fois.

   Mais si, au contraire, vous avez

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

   ensuite, il ne sera calculé une fois.

3. Oui.

4. Oui, une fois partie d'un nommé la valeur est calculée, elle est conservée jusqu'à ce que le nom est hors de portée. (La langue n'est pas une obligation, mais c'est la façon dont je comprends les implémentations de se comporter.)

Answer 3

Si oui, sont leurs valeurs mises en cache en quelque sorte (c'est à dire, si je l'appelle longueur deux fois, il va à la parcourir deux fois)?

GHC ne procédez à l'Élimination des sous-expressions redondantes. Par exemple:

{-# 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 ()

Donne sur -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)
    }

Notez que aaaaaaaaa des appels GHC.List.$wlen deux fois.

(En fait, parce qu' x doit être conservé en aaaaaaaaa, c'est plus de 2x plus lent que l' bbbbbbbbb.)