Wie arbeitet Haskell mit Rekursion und Faulheit?
In Haskell ersetzt Rekursion die Schleife: Eine Funktion ruft sich auf dem kleineren Rest einer Liste selbst auf. Mit der verzögerten Auswertung (lazy evaluation) darf eine Liste sogar unendlich lang sein, solange nur ein Teil davon gebraucht wird.
Das zeigt, wie ein Programm Werte erst berechnet, wenn jemand sie wirklich braucht.
Am Ende dieser Lektion
Notiz
Ich kann eine rekursive Funktion schreiben und erklären, warum eine unendliche Liste benutzbar ist.
Schlüsselwörter
| Begriff | Was er bedeutet | Beispiel |
|---|---|---|
| Rekursion | eine Funktion ruft sich selbst auf einem kleineren Rest auf | |
| Basisfall | der einfachste Fall, in dem sie sich nicht mehr aufruft | mySum [] = 0 |
| Musterabgleich | Haskell wählt die Zeile, deren Muster zur Eingabe passt | |
| Verzögerte Auswertung | ein Wert wird erst berechnet, wenn er gebraucht wird | |
| Unendliche Liste | eine Liste ohne Ende, von der nur ein Stück berechnet wird | [1 ..] |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Eine rekursive Funktion hat zwei Zeilen
Die Summe einer Liste lässt sich mit zwei Zeilen beschreiben. Erste Zeile, der Basisfall: Die Summe der leeren Liste ist 0. Zweite Zeile: Die Summe einer Liste ist ihr erstes Element plus die Summe des Rests.
Haskell wählt die Zeile durch Musterabgleich: [] passt auf die leere Liste, (x : rest) auf eine Liste mit erstem Element x.
Ein Produkt rekursiv berechnen
-- Beispiel: das Produkt einer Liste ganzer Zahlen.
produkt :: [Int] -> Int
produkt [] = 1
produkt (x : rest) = x * produkt restBeispiel: mySum [1, 2, 3] entfaltet
| Schritt | Ausdruck |
|---|---|
| 1 | mySum [1, 2, 3] |
| 2 | 1 + mySum [2, 3] |
| 3 | 1 + (2 + mySum [3]) |
| 4 | 1 + (2 + (3 + mySum [])) |
| 5 | 1 + (2 + (3 + 0)) und damit 6 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Die Datei Fold.hs ansehen
docker exec haskell cat Fold.hsHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Die rekursive Summe aufrufen
docker exec haskell ghc -e "mySum [1, 2, 3]" Fold.hsHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Haskell rechnet nur, was gebraucht wird
Bei der verzögerten Auswertung berechnet Haskell einen Wert erst, wenn ihn jemand braucht. Ein Ausdruck, den niemand liest, wird nie ausgerechnet.
Der Wert undefined löst beim Berechnen einen Fehler aus. Steckt er in einem Paar, aus dem nur der erste Teil gelesen wird, geschieht trotzdem nichts.
Ein Wert, der nie gebraucht wird
docker exec haskell ghc -e "fst (3, undefined)"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Eine unendliche Liste ist benutzbar
[1 ..] ist die Liste aller Zahlen ab 1, ohne Ende. Sie steht nicht im Speicher: Haskell erzeugt ein Element erst, wenn es verlangt wird.
take 5 [1 ..] verlangt genau fünf Elemente. Auch map und filter auf einer unendlichen Liste arbeiten nur so weit, wie der Aufrufer liest.
Fünf Elemente einer unendlichen Liste
docker exec haskell ghc -e "take 5 [1 ..]"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
map auf einer unendlichen Liste
docker exec haskell ghc -e "take 5 (map (* 2) [1 ..])"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Quadratzahlen, gerade, unter 40
docker exec haskell ghc -e "takeWhile (< 40) (filter even (map (^ 2) [1 ..]))"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Immer wieder verdoppeln
docker exec haskell ghc -e "take 6 (iterate (* 2) 1)"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Ein häufiger Fehler
Warnung
Viele glauben, eine unendliche Liste brauche unendlich viel Speicher oder lasse das Programm hängen. Das stimmt nur, wenn Sie die ganze Liste verlangen, etwa mit length [1 ..]: Das endet nie. Verlangen Sie ein Stück, arbeitet Haskell nur so weit.
Einen faulen Strom in Python bauen
Python kennt Generatoren: Eine Funktion mit yield liefert einen Wert, hält an und macht erst weiter, wenn jemand den nächsten verlangt. Das ist verzögerte Auswertung.
Sie schreiben einen unendlichen Strom natuerliche_zahlen, dazu nimm, bilde_strom und filtere_strom. Sie entsprechen [0 ..], take, map und filter.