Fibonacci-Folge in Haskell
Heute soll es um die bekannte Fibonacci-Folge gehen. Dabei werde ich, um mich wieder in funktionale Programmierung zu vertiefen, zwei in Haskell geschriebene Versionen der Fibonacci-Folge angeben und deren Äquivalenz zeigen.
Die naive Implementierung könnte folgendermaßen aussehen:
fib n
| n < 0 = error "n must be greater or equal zero"
| n == 0 = 0
| n == 1 = 1
| n >= 2 = fib (n-1) + fib (n-2)
Am Beispiel bei n = 6 kann man bereits erkennen, weshalb diese Implementierung langsam ist:
fib 6 = fib 5 + fib 4
~> { fib 5 einsetzen }
fib 6 = fib 4 + fib 4 + fib 3
~> { fib 4 einsetzen }
fib 6 = fib 3 + fib 3 + fib 3 + fib 2 + fib 2
~> { fib 3 einsetzen }
fib 6 = fib 2 + fib 2 + fib 2 + fib 2 + fib 2 + fib 1 + fib 1 + fib 1
~> { fib 2 einsetzen }
fib 6 = fib 1 + fib 1 + fib 1 + fib 1 + fib 1 + fib 1 + fib 1 + fib 1 + fib 0 + fib 0
~> { fib 1 einsetzen }
fib 6 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + fib 0 + fib 0
~> { fib 0 einsetzen }
fib 6 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
~> { + einsetzen }
fib 6 = 8
Es finden also mehrfache Berechnungen desselben Werts statt. Durch genaueres Hinsehen stellt man folgende Korrelation fest:
- fib 6 wird einmal (fib 1) berechnet.
- fib 5 wird einmal (fib 2) berechnet.
- fib 4 wird zweimal (fib 3) berechnet.
- fib 3 wird dreimal (fib 4) berechnet.
- fib 2 wird fünfmal (fib 5) berechnet.
- fib 1 wird achtmal (fib 6) berechnet.
D.h. das Ergebnis von fib n ist die Summe von fib n Einsen. Für n = 100 würde das bedeuten, dass man 354.224.848.179.261.915.075 Einsen summiert. Eine effizientere Variante, die Haskells lazy evaluation ausnutzt, stellt folgende Definition dar.
fib' = let fibs = [0,1] ++ zipWith (+) fibs (tail fibs) in (fibs !!)
Der Vorteil an dieser Variante ist, dass jedes Element genau einmal berechnet und anschließend weiterverwendet wird. Aber bevor ich die Äquivalenz zeige, möchte ich noch die wesentlichen verwendeten Funktionen einführen. Beginnen wir bei der Funktion (++), sprich der Verkettung von zwei Listen, d.h. für zwei beliebige Listen [x1, ..., xn] und [y1, ..., ym] gilt [x1, ..., xn] ++ [y1, ..., ym] = [x1, ..., xn, y1, ..., ym]. Mittels xs !! i kann man das i-te (beginnend bei Null) Element aus der Liste xs entnehmen. Die anderen beiden wesentlichen Funktionen tail und zipWith werde ich anhand von Haskell-Code definieren.
tail [] = error "empty list"
tail (_:xs) = xs
zipWith _ [] _ = []
zipWith _ _ [] = []
zipWith f (x:xs) (y:ys) = (x `f` y) : zipWith f xs ys
Satz. fib und fib' sind äquivalent.
Beweis. Da fib' n jeweils das n-te Element aus der Liste fibs entnimmt, genügt es zu zeigen, dass fibs die Fibonacci-Folge darstellt, d.h. fibs = [fib 0, fib 1, fib 2, ...]. Dass fibs !! 0 = 0 = fib 0 und fibs !! 1 = 1 = fib 1 gelten, ist offensichtlich. Da fibs die Verkettung von [fib 0, fib 1] und einer Liste, die mittels zipWith erstellt wird, darstellt, muss lediglich gezeigt werden, dass zipWith (+) fibs (tails fibs) und [fib 2, fib 3, ...] äquivalent sind. Nach Definition von zipWith entnimmt selbige jeweils das erste Element aus den beiden übergebenen Listen und berechnet anhand der übergebenen Funktion ein neues Element. D.h. ein i-maliges Anwenden der zipWith-Funktion erzeugt i Elemente, was wiederum bedeutet, dass man durch i-maliges Anwenden von zipWith den Wert von fib (1+i) berechnet. Diese Eigenschaft lässt sich induktiv beweisen.
Induktionsanfang. Sei i = 1, dann lässt sich fib (1+i) = fib 2 folgendermaßen berechnen:
fibs =[fib 0, fib 1] ++ zipWith (+) fibs (tail fibs)
~> { Def. von fibs }
= [fib 0, fib 1] ++ zipWith (+) [fib 0, fib 1, ...] (tail [fib 0, fib 1, ...])
~> { Def. von tail }
= [fib 0, fib 1] ++ zipWith (+) [fib 0, fib 1, ...] [fib 1, ...]
~> { Def. von zipWith }
= [fib 0, fib 1] ++ (fib 0 + fib 1) : zipWith (+) [fib 1, ...] [...]
~> { Def. von Fibonacci-Folge }
= [fib 0, fib 1] ++ (fib 2) : zipWith (+) [fib 1, ...] [...]
~> { Verkettung }
= [fib 0, fib 1, fib 2] : zipWith (+) [fib 1, ...] [...]
Induktionsschritt. Sei zipWith bereits i-mal angewendet worden, d.h. es sind bereits die ersten i+2 Werte von fibs bekannt, d.h. take (i+2) fibs = [fib 0, fib 1, ..., fib (i+1)]. Es ist zu zeigen, dass durch eine weitere Anwendung der Wert von fib (1+i+1) = fib (2+i) berechnet wird. Folgender Code illustriert dann die Berechnung für fib (2+i):
fibs = [fib 0, fib 1] ++ zipWith (+) fibs (tail fibs)
~> { i-maliges Anwenden von zipWith auf fibs }
= [fib 0, fib 1, ..., fib (1+i)] ++ zipWith (+) [fib i, fib (1+i), ...] (tail [fib i, fib (1+i), ...])
~> { Def. von tail }
= [fib 0, fib 1, ..., fib (1+i)] ++ zipWith (+) [fib i, fib (1+i), ...] [fib (1+i), ...]
~> { Def. von zipWith }
= [fib 0, fib 1, ..., fib (1+i)] ++ ((fib i) + fib (1+i)) : zipWith (+) [fib (1+i), ...] [...]
~> { Def. von Fibonacci-Folge }
= [fib 0, fib 1, ..., fib (1+i)] ++ (fib (2+i)) : zipWith (+) [fib (1+i), ...] [...]
~> { Verkettung }
= [fib 0, fib 1, ..., fib (1+i), fib (2+i)] ++ zipWith (+) [fib (1+i), ...] [...]
Der letzte Fall, der noch gezeigt werden muss, besteht im Fehlerfall. Denn, wenn eine Funktion einen Fehler liefert, soll die andere Funktion mit derselben Eingabe auch einen Fehler liefern. Die Funktion (!!) liefert einen Fehler, wenn entweder der Index zu groß ist oder wenn er negativ ist. Zu groß kann er nicht werden, da es sich bei fibs um eine unendlich lange Liste handelt. D.h. fib' n liefert genau dann einen Fehler, wenn n negativ ist. Da fib n auch nur bei negativen n einen Fehler liefert, sind fib' n und fib n auch für ungültige Eingaben äquivalent.