Comment les listes sont-elles implémentées dans Haskell (GHC)?

J’étais juste curieux de connaître les détails exacts d’implémentation des listes dans Haskell (les réponses spécifiques au GHC sont correctes) – s’agit-il de listes liées naïves ou ont-elles des optimisations spéciales? Plus précisement:

  1. Est-ce que la length et (!!) (par exemple) doivent parcourir la liste?
  2. Si oui, leurs valeurs sont-elles mises en cache de quelque manière que ce soit (par exemple, si j’appelle la length deux fois, devra-t-il effectuer une itération des deux fois)?
  3. L’access à l’arrière de la liste implique-t-il une itération dans toute la liste?
  4. Les listes infinies et les compréhensions de liste sont-elles mémorisées? (ie, pour fib = 1:1:zipWith (+) fib (tail fib) , chaque valeur sera-t-elle calculée de manière récursive, ou s’appuiera-t-elle sur la valeur calculée précédente?)

Tout autre détail intéressant sur la mise en œuvre serait très apprécié. Merci d’avance!

Les listes n’ont pas de traitement opérationnel spécial à Haskell. Ils sont définis comme:

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

Juste avec une notation spéciale: [a] pour List a , [] pour Nil et (:) pour Cons . Si vous avez défini la même chose et redéfini toutes les opérations, vous obtiendrez exactement les mêmes performances.

Ainsi, les listes de Haskell sont liées entre elles. À cause de la paresse, ils sont souvent utilisés comme iterators. sum [1..n] s’exécute dans un espace constant, car les préfixes inutilisés de cette liste sont récupérés à mesure que la sum progresse et que les queues ne sont pas générées tant qu’elles ne sont pas nécessaires.

Comme pour # 4: toutes les valeurs de Haskell sont mémorisées, à l’exception des fonctions qui ne contiennent pas de table de mémo pour leurs arguments. Donc, lorsque vous définissez fib comme vous l’avez fait, les résultats seront mis en cache et le nième numéro de fibonacci sera accessible en temps O (n). Cependant, si vous l’avez défini de cette manière apparemment équivalente:

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

(Prenez un moment pour noter la similitude avec votre définition)

Ensuite, les résultats ne sont pas partagés et le nième numéro de fibonacci sera accessible en temps O (fib n) (qui est exponentiel). Vous pouvez convaincre les fonctions à partager avec une bibliothèque de mémorisation comme les mémos de données .

Si oui, leurs valeurs sont-elles mises en cache de quelque manière que ce soit (par exemple, si j’appelle la longueur deux fois, devra-t-il effectuer une itération des deux fois)?

GHC n’effectue pas une élimination complète de la sous-expression commune . 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 appelle GHC.List.$wlen deux fois.

(En fait, parce que x doit être conservé dans aaaaaaaaa , il est plus de 2x plus lent que bbbbbbbbb .)

Pour autant que je sache (je ne sais pas à quel point cela est spécifique au GHC)

  1. length et (!!) DOIT parcourir la liste.

  2. Je ne pense pas qu’il existe des optimisations spéciales pour les listes, mais il existe 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) 

    alors la length xs sera calculée deux fois.

    Mais si au contraire vous avez

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

    alors il ne sera calculé qu’une fois.

  3. Oui.

  4. Oui, une fois qu’une partie d’une valeur nommée est calculée, elle est conservée jusqu’à ce que le nom soit hors de scope. (Le langage ne nécessite pas cela, mais c’est comme ça que je comprends les implémentations.)