Haskell · Konzepte · Auswertung

Lazy Evaluation in Haskell, erklärt

Die meisten Sprachen sind strikt: Ein Ausdruck wird ausgewertet, sobald er an einen Namen gebunden wird. Haskell ist anders — es ist standardmäßig lazy (genauer nicht-strikt): Ein Ausdruck wird nicht ausgewertet, solange sein Ergebnis nicht wirklich gebraucht wird. Diese eine Entwurfsentscheidung steckt hinter einigen der charakteristischsten Stärken von Haskell und hinter seiner berüchtigtsten Falle. Dieser Leitfaden erklärt, was Lazy Evaluation ist, wie Thunks funktionieren, was sie Ihnen bringt und wie man sie abschaltet, wenn es nötig ist.

Die Idee in einem Satz

Unter Lazy Evaluation berechnet das Binden eines Werts ihn nicht — Haskell speichert eine aufgeschobene Berechnung (einen Thunk) und erzwingt sie erst, wenn eine andere Berechnung das Ergebnis verlangt. Wird das Ergebnis nie verlangt, wird die Arbeit nie geleistet.

Thunks: die aufgeschobene Berechnung

Wenn Sie let x = expensive 42 schreiben, führt Haskell expensive nicht aus. Es erzeugt einen Thunk — ein unausgewertetes Versprechen von expensive 42. Der Thunk wird erst erzwungen, wenn etwas den tatsächlichen Wert von x braucht (etwa ihn auszugeben oder ein Pattern-Matching darauf zu machen). Erzwingen Sie ihn einmal, und das Ergebnis wird zwischengespeichert, um nicht neu berechnet zu werden.

let x = expensive 42   -- nothing runs yet; x is a thunk
let y = x + 1          -- still nothing; y is a thunk too
print y                -- NOW x and y are forced and evaluated

Was Lazyness Ihnen bringt

• Unendliche Datenstrukturen. [1..] ist die unendliche Liste der ganzen Zahlen. take 5 [1..] liefert [1,2,3,4,5], weil nur die ersten fünf je verlangt werden.
• Komposition ohne Verschwendung. Sie können filter und map über eine riesige Liste verketten, und Haskell verschmilzt die Arbeit und erzeugt nur das, was der Konsument abzieht — keine vollständigen Zwischenlisten, wenn sie nie ganz verlangt werden.
• Kostenlose Kurzschluss-Auswertung. False && undefined liefert False, ohne undefined je zu berühren, weil das zweite Argument nie erzwungen wird.
• Selbstbezug. Klassische Einzeiler wie fibs = 0 : 1 : zipWith (+) fibs (tail fibs) definieren den unendlichen Fibonacci-Strom — möglich nur, weil die Struktur lazy aufgebaut wird.

Die Falle: Speicherlecks

Lazyness hat einen Preis. Unausgewertete Thunks sammeln sich im Speicher an, und eine lange Kette aufgeschobener Berechnungen kann den Heap-Verbrauch still aufblähen — ein Speicherleck (space leak). Das Schulbeispiel ist ein lazy Left-Fold, der einen riesigen Turm von Thunks (((0 + 1) + 2) + 3) ... aufbaut, statt unterwegs zu addieren:

foldl (+) 0 [1..1000000]    -- builds a million thunks, may blow the stack
foldl' (+) 0 [1..1000000]   -- strict fold: adds as it goes, constant space

Die Lösung ist, die Auswertung zu erzwingen, wo es zählt. Greifen Sie für Akkumulationen zum strikten Left-Fold foldl' (aus Data.List).

Striktheit erzwingen: seq, $! und BangPatterns

Haskell gibt Ihnen präzise Werkzeuge, um die Auswertung zu verlangen:

• seq a b — erzwingt a in die schwache Kopf-Normalform, bevor b zurückgegeben wird.
• ($!) — strikte Anwendung: f $! x erzwingt x, bevor f angewendet wird.
• BangPatterns — die Erweiterung {-# LANGUAGE BangPatterns #-} lässt Sie let !x = ... schreiben, um eine Bindung zu erzwingen.

Eine wichtige Feinheit: Erzwingen erreicht typischerweise die schwache Kopf-Normalform (den äußersten Konstruktor), nicht die vollständige Auswertung. Um tief zu erzwingen, verwenden Sie force / deepseq aus dem Paket deepseq.

FAQ

Ist Haskell lazy oder nicht-strikt? Technisch nicht-strikt (eine semantische Garantie); GHC implementiert es über Lazy Evaluation mit Thunks und Sharing. In der Praxis sagt man „lazy“.

Warum verbraucht mein Haskell-Programm so viel Speicher? Oft ein Speicherleck durch angesammelte Thunks — häufig ein lazy foldl. Wechseln Sie zu foldl' oder fügen Sie Striktheit mit seq/BangPatterns hinzu.

Was ist ein Thunk? Eine unausgewertete, aufgeschobene Berechnung, die anstelle eines Werts gespeichert wird, erst erzwungen, wenn der Wert verlangt wird, und dann zwischengespeichert.

Macht Lazyness Haskell langsam? Nicht von Natur aus — sie kann unnötige Arbeit vermeiden und Fusion ermöglichen. Aber nachlässige Lazyness verursacht Speicherlecks; zu wissen, wann man erzwingt, gehört zum Schreiben von gutem Haskell.

Lazyness ist dieselbe Mechanik, die dafür sorgt, dass sich Haskells andere Abstraktionen sauber komponieren — sehen Sie, wie die Sequenzierung in unserem Leitfaden zu Monaden in Haskell funktioniert, und richten Sie die Toolchain ein, um diese Beispiele in GHCi mit dem GHC-Compiler-Leitfaden auszuprobieren.