icancode.de

Lazy Evaluation in Haskell

Einleitung

Jonas

Jonas


Neuste Artikel

Haskell

Lazy Evaluation in Haskell

Veröffentlicht am .

haskell-logo-with-name
In diesem Snippet wollen wir an einem Beispiel etwas über ein besonderes Feature in Haskell, „Lazy Evaluation“, lernen.

Was ist Laziness?

Laziness bedeutet, dass ein Wert erst dann berechnet wird, wenn er tatsächlich gebraucht wird und nicht schon beim ersten Mal, wenn er im Programm auftaucht. Ziel davon sind effizientere Programme und mehr Platz im Hirn der Person, die in Haskell codet. Wir werden gleich sehen, warum.

Lazy Evaluation ist sozusagen das Gegenstück zu Garbage Collection (GC). Während GC bedeutet, dass ein Programmierer sich keine Gedanken um das Ende der Lebenszeit einer Variable machen muss, bedeutet Laziness passenderweise, dass er sich ebenfalls keine Gedanken an den Anfang dieser Lebenszeit verschwenden muss.

Was bringt Lazy Evaluation?

Das erlaubt uns verschiedenste coole Dinge, wie zum Beispiel „unendliche“ Listen (sie sind zwar begrenzt, aber nur durch Mangel an Speicher im Computer oder Geduld im Menschen).
Wir geben einmal die Definition an und Haskell berechnet erst dann, wenn wir die Elemente wirklich brauchen.

Hier sind zum Beispiel die natürlichen Zahlen:

> nats :: [Integer]
> nats = [0..]

Die []-Notation steht in Haskell für Listen. Hier ist also eine Liste aller natürlichen Zahlen (Typ Integer), beginnend mit 0, gemeint.

Einen Schritt komplizierter. Hier sind die Fibbonacci-Zahlen, definiert als „unendliche“, lazy Liste in Haskell:

> fibbs :: [Integer]
> fibbs = 1:1: zipWith (+) fibbs (tail fibbs)

Kurze Erklärung der verwendeten Funktionen, jeweils mit Typsignatur:

(:: liest sich im Haskell-Kontext als „hat den Typ“. Im Folgenden sind außerdem a,b und c polymorphe Typen, es ist also egal welchen Typen wir am Ende einsetzen, die Funktionen funktionieren auf allen. Diese Typen können gleich sein (z.B. a = c = String), müssen aber nicht.)

(+) :: Num a => a -> a -> a
-- Die ganz normale Addition auf Zahlen, in unserem Fall Integern.
-- Beispiel ~ 1 + 41 = 42
(:) :: a -> [a] -> [a]
-- Gesprochen: "Cons". Hängt ein Element vom Typ a vor eine Liste des gleichen Typs a. In diesem Fall ein Integer an eine [Integer].
-- Beispiel (infix) ~ 2 : [3,4,5] = [2,3,4,5]
tail :: [a] -> [a]
-- Gibt den "Schwanz" einer Liste zurück, also alles außer dem ersten Element.
-- Beispiel ~ tail [1,2,3,4,5] = [2,3,4,5]
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
-- Nimmt eine Funktion, die aus einem a und einem b ein c macht (das macht zipWith zu einer so genannten "Higher Order Function", weil es einen Funktionsparameter hat), eine Liste von as und eine Liste von bs. Zurück gegeben wird eine Liste von cs. 
-- Was passiert ist eigentlich offensichtlich. Es wird je das erste a und b aus den entsprechenden Listen genommen und damit wird das erste c der Ergebnisliste produziert usw.
-- Beispiel ~ zitWith (==) [1..] [1..] = [True, True, True, ...]

Was passiert also hier genau?

Wir geben die ersten beiden Elemente der Liste (1 und 1) direkt an, und den Rest der Liste definieren wir als einerseits die Liste selbst und andererseits den Tail der List verknüpft mit (+). Wenn also das dritte Element berechnet werden soll, wird das erste Element der Liste (1) zum ersten Element des Tails der Liste (die zweite 1) addiert. Das ergibt 2. Bei der Berechnung des dritten Elements wird das zweite Element der Liste selbst (1) zum zweiten Element des Tails (die eben berechnete 2) addiert, was 3 ergibt. Und so weiter.

Wegen Laziness und Garbage Collection werden immer nur maximal drei Zahlen im Speicher gehalten, auch wenn wir das millionste Element der Liste haben wollen.
Lazy Evaluation erlaubt uns also, intuitive Definitionen zu schreiben, und trotzdem speichereffizient zu bleiben.
In imperativen / strikten Sprachen (strikt bedeutet ohne lazy evaluation, also z.B. Java) müssten wir deutlich mehr „hacky“ schreiben, um den gleichen Effekt zu erzielen.

Titelbild: haskell.org

Jonas

Jonas

Navigation