Wie werden Listen in Haskell (GHC) implementiert?

Question

Ich war nur neugierig auf einige genaue Implementierungsdetails von Listen in Haskell (GHC-spezifische Antworten sind in Ordnung) - sind sie naiv verknüpfte Listen oder haben sie spezielle Optimierungen? Insbesondere:

1. Sie length und (!!) (zum Beispiel) haben durch die Liste zu durchlaufen?
2. Wenn ja, sind ihre Werte in irgendeiner Weise zwischengespeichert (d. H., Wenn ich zweimal length rufe, muss es beide Male iterieren)?
3. Bewirkt der Zugriff auf die Rückseite der Liste das Durchlaufen der gesamten Liste?
4. Sind unendliche Listen und Listenkompressen notiert? (Das heißt, für fib = 1:1:zipWith (+) fib (tail fib), wird jeder Wert rekursiv berechnet werden, oder wird es auf dem vorherigen berechneten Wert verlassen?)

weitere interessante Details der Implementierung wären sehr willkommen. Danke im Voraus!

Answer 1

Listen keine spezielle operative Behandlung in Haskell haben. Sie sind definiert wie:

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

Nur mit einigen speziellen Schreibweise: [a] für List a, [] für Nil und (:) für Cons. Wenn Sie das Gleiche definieren und alle Operationen neu definieren, erhalten Sie genau die gleiche Leistung.

Daher sind Haskell-Listen einfach verknüpft. Wegen der Faulheit werden sie oft als Iteratoren verwendet. sum [1..n] wird im konstanten Speicherbereich ausgeführt, da die unbenutzten Präfixe dieser Liste im Verlauf der Gesamtsumme als Garbage Collection erfasst werden und die Tails erst generiert werden, wenn sie benötigt werden.

Wie für # 4: alle Werte in Haskell Memo sind, mit der Ausnahme, dass Funktionen eine Memotabelle für ihre Argumente nicht beibehalten. Wenn Sie also fib wie Sie definieren, werden die Ergebnisse zwischengespeichert und die n-te Fibonacci-Nummer wird in O (n) -Zeit aufgerufen. wenn man es in dieser scheinbar gleichwertigen Art und Weise jedoch definiert:

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

(Nehmen Sie einen Moment, um die Ähnlichkeit zu Ihrer Definition beachten)

Dann werden die Ergebnisse nicht mit anderen geteilt und die n-te Fibonacci-Zahl wird in zugegriffen werden O (fib n) (die exponentielle) Zeit. Sie können Funktionen zur gemeinsamen Nutzung mit einer Memo-Bibliothek wie data-memocombinators überzeugen.

Answer 2

Soweit ich weiß (ich weiß nicht, wie viel von dieser GHC-spezifisch ist)

1. length und (!!) DO durch die Liste zu durchlaufen haben.

2. Ich glaube nicht, dass es spezielle Optimierungen für Listen gibt, aber es gibt eine Technik, die für alle Datentypen gilt.

   Wenn Sie so etwas wie

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

   dann wird length xs zweimal berechnet werden.

   Aber wenn Sie stattdessen

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

   haben, dann wird es nur einmal berechnet werden.

3. Ja.

4. Ja, sobald ein Teil eines benannten Werts berechnet wird, wird er beibehalten, bis der Name den Gültigkeitsbereich verlässt. (Die Sprache bedarf es nicht, aber das ist, wie ich verstehe die Implementierungen verhalten.)

Answer 3

Wenn ja, sind ihre Werte in irgendeiner Weise zwischengespeichert (d. H., Wenn ich die Länge zweimal anrufe, muss sie beide Male iterieren)?

GHC does not perform full Common Subexpression Elimination. Zum Beispiel:

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

Gewährt auf -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) 
    } 

Beachten Sie, dass aaaaaaaaa Anrufe GHC.List.$wlen zweimal.

(In der Tat, weil x Bedürfnisse in aaaaaaaaa zurückgehalten werden, ist es mehr als 2x langsamer als bbbbbbbbb ist.)