[Haskell] fibonacci definition verstehen...

otze

Ich lerne ja momentan etwas haskell in meiner Freizeit und ich muss zugeben, dass manches durchaus interessant ist...anderes widerum will mir so gar nicht in den Kopf.

Würde man mich fragen, wie ich die fibonacci Zahlen in Haskell als unendliche Reihe definiere, hätte ich das wohl so gemacht:

fibs= 0:1:[fibs!!(n-1) + fibs!!(n-2)|n<-[2..]]

Das entspricht irgendwie der üblichen Logik: erstelle das n-te element indem du das n-1te auf das n-2te addierst. Könnte man sogar noch schöner schreiben, wenn man n bei 1 beginnen lassen würde. Aber seis drum.

Nun war in dem Thread über fibonacci Zahlen im C++ Unterforum folgende Definition genannt worden:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Und das scheint irgendwie die standard definition zu sein, die man im Netz findet. Und nach ein wenig hin und her habe ich eine Vermutung wie das funktionieren könnte. Nur: was genau macht das?

Vielleicht kann mir ein haskellgott helfen

Nexus

Ich bin zwar nicht gerade der Haskell-Experte, aber will trotzdem versuchen, den Code zu erklären.

Wichtig sind die Funktionen zipWith und tail . tail gibt von einer Liste alle Elemente ausser dem ersten zurück. zipWith fügt zwei Listen mit einer spezifizierten Funktion zusammen. Das erste Argument von zipWith ist diese Funktion: In deinem Fall (+) , also der Plus-Operator. Das zweite Argument ist fibs und das dritte (tail fibs) , also die beiden zusammenzuführenden Listen.

Die rekursiv aufgerufenen Funktionen stellen ihrerseits bereits Fibonacci-Folgen dar. Zur Visualisierung:

0 1                 <- 0 : 1 :
    0 1 1 2 3 ..    <- fibs
    1 1 2 3 5 ..    <- tail fibs
    1 2 3 5 8 ..    <- zipWidth (+) fibs (tail fibs)
0 1 1 2 3 5 8 ..    <- 0 : 1 : zipWith (+) fibs (tail fibs)

Die zweitletzte Zeile entspricht dabei der elementweisen Summe der beiden vorherigen Zeilen. Diese wird an die Anfangswerte 0 und 1 angehängt, somit erhältst du die letzte Zeile.

otze

Hallo,

Danke für die Antwort. Mir war bereits klar, was die einzelnen Teile machen. Was ich nicht verstehe ist:

"Die rekursiv aufgerufenen Funktionen stellen ihrerseits bereits Fibonacci-Folgen dar".

Irgendwie will mir nicht in den Kopf, dass das so ist - oder warum das so ist. Ich finde dazu keinen logischen Zugang mit dem ich mir das vorstellen könnte was da passiert.

die Folgen werden natürlich nicht als unendliche Folgen gespeichert (=> Probleme bei der Beschaffung geeigneter RAMs), sondern es wird lediglich diese rekursive BAUANLEITUNG für fibs vermerkt. Sobald nun an einer Stelle im Programm ein Element von fibs benötigt wird, wird gerade so viel von fibs berechnet wie notwendig, und dies gemäß der rekursiven Bauanleitung.

Diese Eigenschaft nennt man "lazy evaluation".

otze

danke, aber das war mir auch bekannt. Habe ich ja ganz am Anfang selbst verwendet das Feature

Was mir halt nicht in den Kopf will ist, wie und warum fibs/tail fibs als Parameter von ZipWith so aussehen, wie sie aussehen. Das ist auch mathematisch gesehen eine ziemlich komische Definition. Wenn ich nen Parameter in ne Funkion gebe erwarte ich nicht, dass ihre eigene Ausgabe den Paramter verändert. Irgendwie setzt da bei mir die Logik aus.

lies mein Posting nochmal sorgfältig.

Bauplan => es gibt keinen zeitlichen Aspekt der Art "erst Eingabe, dann Ausgabe", wie man das von prozeduralen Sprachen gewohnt ist.

knivil

Ich rate dir, nicht Haskell als erstes zu lernen. Besser ist z.B. erst Scheme zu lernen und dann durch Lazy Evaluation als default gedanklich zu erweitern. Fuer Scheme gibt es SICP und die entsprechenden Video lectures. Dein Problem scheint schon bei Listen zu beginnen und wie sie repraesentiert werden. Nur zu empfehlen! Es gibt im Buch auch Beschreibungen, wie man solche Streams in Scheme mittels promise und force (wobei man diese Sprachelemente nicht wirklich braucht).

zipWith kann wie folgt implementiert werden (normalerweise wird ene Variante von fold verwendet):

-- Abbruchbedingungen/Sonderfaelle fuer leere Listen weggelassen
zipWith op (x:xs) (y:ys) = (x `op` y) : zipWith op xs ys

Gut, setzen wir das in fibs ein und fragen nach dem dritten Element.

fibs !! 2 -- beginnt bei 0 zu zaehlen

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
fibs = 0 : 1 : zipWith (+) (0:xs) (1,ys) -- xs und ys brauchen noch nicht zu evaluieren
fibs = 0 : 1 : (0 + 1) : zipWith (+) xs ys
fibs = 0 : 1 : 1 : zipWith (+) xs ys
               ^-- hier beginnt jetzt ys
           ^-- hier beginnt jetzt xs

Damit man einen Anfang hat, muessen die ersten beiden Element (0 und 1) explizit angegeben werden. Willst du das 4te, setze einfach mit den richtigen xs und ys fort.

Wenn ich nen Parameter in ne Funkion gebe erwarte ich nicht, dass ihre eigene Ausgabe den Paramter verändert.

Mache dir klar, was pure functional, referenzielle Transparenz oder frei von Seiteneffekten bedeutet. Die genannten Begriffe sind aequivalent. Beispiel:

f(x) = 2 * x

Nun betrachten wir a = f(5). Es ist egal ob ich den Wert berechne und an eine Variable binde oder einen Chunk mit der Funktion + Parameter 5 erzeuge und an den die Variable binde. Wird der Chunk evaluiert muss natuerlich der Wert 10 berechnet werden. Ist er einmal berechnet kann der Chunk durch den Wert 10 ersetzt werden. Warum darf man das: weil f ohne Seiteneffekte ist, so dass immer der Wert 10 ausgegeben wird. Der Chunk f(5) ist aequivalent zu 10. Bei Lazy Evaluation wird immer der Chunk erzeugt und die tatsaechliche Berechnung auf spaeter verschoben.

Angewandt auf fibs:

fibs = 0 : 1 : rest
                ^-- Chunk in dem die Berechnung zipWith .. drinsteht

zipWith op (x:xs) (y:ys) = (x `op` y) : zipWith op xs ys
                                         ^-- neuer Chunk

mngbd

knivil schrieb:

Es gibt im Buch auch Beschreibungen, wie man solche Streams in Scheme mittels promise und force (wobei man diese Sprachelemente nicht wirklich braucht).

Das Ding heisst delay .

knivil

Ok. Habe bin etwas durcheinander gekommen. Es ist aber ein promise (zumindestens in guile):

guile> (delay (+ 4 5))
#<promise #<procedure #f ()>>

(define a (delay (+ 1 2)))
(promise? a)
#t

otze

@knivil ne, fast überall leider daneben. Listen habe ich verstanden, und die ganzen Standard Begriffe wie Lazy-Evaluation und Seiteneffektfreiheit sagen mir auch was.

Inzwischen hats mir jemand ganz gut erklärt, bzw mir ein Denkmodell dafür gegeben.

Ich habe den Fehler gemacht,

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Als Ausdruck zu interpretieren, wie ichs gewohnt bin. Also links steht das Ergebnis von Rechts(wie zum Beispiel mein erster Code oben). Funktioniert natürlich so nicht.

Das nette Denkmodell was ich bekam war, dies nicht als Ausdruck, sondern als Gleichung zu verstehen: gesucht wird eine Liste fibs, die die Gleichung erfüllt. Natürlich funktioniert das nur, wenn fibs die unendliche fibonacci folge ist.

Bin mir zwar nicht sicher, ob ich sowas on-the-fly selbst funktionierend hinrkeige, aber ich bin erstmal zufrieden.

Bashar

Das Denkmodell ist aber leider falsch, Haskell ist doch kein Gleichungslöser.

knivil

Also links steht das Ergebnis von Rechts(wie zum Beispiel mein erster Code oben). Funktioniert natürlich so nicht.

Bei mir schon.

Bin mir zwar nicht sicher, ob ich sowas on-the-fly selbst funktionierend hinrkeige, aber ich bin erstmal zufrieden.

Wahrscheinlich nicht, weil dein Denkmodell ungeeignet dafuer ist.

Ein etwas einfacheres Beispiel:

next n = n : next (n+1)
nat = next 0

*Main> nat
[1,2,3,4,5,6,7,8,9,10,11, ..]

Wie soll denn Haskell wissen, dass nat die Liste aller natuerlichen Zahlen ist? Dann koennte er auch fuer nat == [0..] den Wert True liefern, tut er aber nicht.

mngbd

knivil schrieb:

Ok. Habe bin etwas durcheinander gekommen. Es ist aber ein promise (zumindestens in guile):
...

Ja, so heissen die Dinger, die delay macht. Das Typ-Prädikat heisst afaik überall promise?, wo diese Dinger von Prozeduren unterscheidbar sind, steht aber nicht im Standard:
http://www.r6rs.org/final/html/r6rs-lib/r6rs-lib-Z-H-20.html#node_idx_1296

otze schrieb:

Das nette Denkmodell was ich bekam war, dies nicht als Ausdruck, sondern als Gleichung zu verstehen: gesucht wird eine Liste fibs, die die Gleichung erfüllt. Natürlich funktioniert das nur, wenn fibs die unendliche fibonacci folge ist.

Das mag sein, gibt dir aber keine Möglichkeit zur Hand, den Ausdruck auszuwerten. Versuch mal, den Ausdruck in natürliche Sprache zu übersetzen, etwa so: die ersten beiden Elemente der Folge sind 0 und 1, den Rest der Folge erhält man, indem man jeweils das aktuelle Element und das nächste addiert.

mngbd

mngbd schrieb:

die ersten beiden Elemente der Folge sind 0 und 1, den Rest der Folge erhält man, indem man jeweils das aktuelle Element und das nächste addiert.

Hmm, damit hab ich den Punkt nicht berührt, der dich wahrscheinlich verwirrt. Vielleicht besser: den Rest der Folge erhält man, indem man die Elemente der Folge mit den Elementen der gleichen Folge addiert, die man um eins nach links verschiebt.

So trifft man besser den Punkt, dass die Sprache mit Funktionen wie zipWith Folgen als ganzes behandeln kann und nicht ihre einzelnen Werte betrachten muss.

Nachtrag:
Formal läuft die Evaluierung so ab: am Anfang kennen wir nur die ersten beiden Elemente, und eine Anweisung, wie weitere Elemente berechnet werden können:

--> wir beginnen mit
fibs =  0 1 ...
tail fibs = 1 ...
zipWith (+) fibs (tail fibs) = 0 1 ...
                               1 ...
                               -------- (+)
                               1 ...
--> weil die letzte Folge der Rest von "fibs" ist, kennen wir jetzt das dritte Element:
fibs = 0 1 1 ...
tail fibs = 1 1 ...
zipWith (+) fibs (tail fibs) = 0 1 1 ...
                               1 1 ...
                               ---------- (+)
                               1 2 ...
--> jetzt kennen wir das vierte Element
fibs = 0 1 1 2 ...
--> usw.

Das machen wir einfach so lange, bis wir genug von der Folge herausgefunden haben.

knivil

@mngbd: Dein Beispiel beinhaltet nicht, dass zipWith intern den "Pointer" der beiden Listen um eins weiter setzt. Das Beispiel wird dadurch falsch. fibs und tail fibs in zipWith sind nicht die gleichen, wie sie beim angegeben sind (drittes Element).

otze

Ich bemerke grad: man braucht keine Pointer oder irgendein Wissen über die Interna, wie Listen aufgebaut sind. Die Gleichung funktioniert rein durch das Substitutionsprinzip. Ist aber zu unübersichtlich um das mal durchzuexerzieren. Und bringt mich grad im Verständnis nicht weiter.

Aber hätte ich nicht gedacht, dass das erfüllt wird. Wow.

Nebenbei: eine Abstraktion deren Interna man verstehen muss um sie zu verstehen ist ziemlich schlecht.

(es geht btw nicht darum mir die Interna zu erklären. Ich glaube, das war das erste was ich verstanden hatte. Vielleicht habe ich das nur schlecht kommuniziert. Es geht eher darum, dass mich das Wissen über die Interna so gar nicht in die Lage versetzt, ähnlichen Code zu schreiben. Ich würde wohl immer in der Situation auf einen Code kommen wie ich ihn ime rsten Post benutzt habe)

mngbd

knivil schrieb:

@mngbd: Dein Beispiel beinhaltet nicht, dass zipWith intern den "Pointer" der beiden Listen um eins weiter setzt. Das Beispiel wird dadurch falsch. fibs und tail fibs in zipWith sind nicht die gleichen, wie sie beim angegeben sind (drittes Element).

Ja, klar. Darüber wollte ich mit dem "formal" hinwegtäuschen. Es ist natürlich eine blöde Idee, jedes Mal alle die Addition wieder vom Anfang an zu machen. Aber es ist nicht falsch.

Ich bin kein Haskell-Experte, aber ich behaupte trotzdem einfach einmal, dass mein Interpretations-Verfahren mit der Haskell-Semantik vereinbar ist. Wenn du nämlich einen Pointer verschiebst, sprichst du auf einer Ebene, auf der es keine referenzielle Transparenz mehr gibt, du alter Compilerbauer.

mngbd

otze schrieb:

Die Gleichung funktioniert rein durch das Substitutionsprinzip. Ist aber zu unübersichtlich um das mal durchzuexerzieren. Und bringt mich grad im Verständnis nicht weiter.

Das sieht nur aus wie ein Substitutionsprinzip, wenn man die Werte einzeln betrachtet, um das durchzuexerzieren. Aus Sicht der Sprache werden da einfach zwei Folgen addiert, ganz egal wie, die Hauptsache ist, dass es machbar ist.

otze schrieb:

Nebenbei: eine Abstraktion deren Interna man verstehen muss um sie zu verstehen ist ziemlich schlecht.

Nur keine Sorge, darüber muss man nur nachdenken, wenn man eine effiziente Implementation auf einem handelsüblichen Computer bauen will. Auf einer FFP-Maschine sieht die Sache schon wieder ganz anders aus. Der Sprache ist das natürlich ganz egal.

Nachtrag:

otze schrieb:

Es geht eher darum, dass mich das Wissen über die Interna so gar nicht in die Lage versetzt, ähnlichen Code zu schreiben. Ich würde wohl immer in der Situation auf einen Code kommen wie ich ihn ime rsten Post benutzt habe

Versuch mal, deinen ersten Ansatz in natürliche Sprache zu übersetzen. Dann können wir die beiden Ansätze auf dieser Ebene vergleichen.

otze

Ich versuchs mal. Erstmal als Anschauungsmaterial nochmal die Codezeile:

fibs= 0:1:[fibs!!(n-1) + fibs!!(n-2)|n<-[2..]]

Die ersten beiden Elemente sind 0 und 1. Elemente 2 bis unendlich erhält man, indem man das Vorgängerelement des neuen Elements mit seinem Vorvorgänger addiert.

mngbd

otze schrieb:

Die ersten beiden Elemente sind 0 und 1. Elemente 2 bis unendlich erhält man, indem man das Vorgängerelement des neuen Elements mit seinem Vorvorgänger addiert.

Dabei beschreibst du den Rest der Folge dadurch, dass du das Wort "Element" benutzt, und zwar eigentlich dreimal, einmal für das n-te, einmal für das n-minus-1-te und einmal für das n-minus-2-te. Nun ist eine der Annehmlichkeiten von Sprachen, die lazy sind, dass man unendliche Folgen beschreiben kann, ohne befürchten zu müssen, dass der Speicher voll wird (wie auch 2.. ). Das ermöglicht die bequemere Formulierung mit der Addition der nach links verschobenen Folge.

Dafür muss man aber die Funktion zipWith kennen, die zwei Folgen verknüpft, oder selbst einen vergleichbaren Ersatz definieren. Auf diese Weise ist das ganze offenbar abstrakter formuliert.

man kann sich die Folge als Funktion f:{0,1,2,...} --> {0,1,2,...} (das ist bekanntlich die allgemeine math. Def. von "ZahlenFolge") vorstllen - wir reden ja schließlich über funktionale Programmierung :D)

0:1:f(0)+f(1):f(1)+f(2):...

dann entspricht "tail fib" einer Indexverschiebung g(n) := f(n+1)

wird im Programm etwa f(2) gebraucht, sieht der Compiler aus der Definition "... zipWith (+) fibs (tail fibs)", daß die Fkt f+g an der Stelle 0 evaluiert werden muß, also f(0)+g(0) = f(0)+f(1) = 0 + 1 berechnet werden muß.

Wird f(3) gebraucht, muß f+g an der Stelle 1 berechnet werden, also f(1)+g(1) = f(1)+f(2), und wie er f(2) berechnet, erkennt er abermals an der rekursiven Def. von fibs.

usw. letztendlich ist es die "lazy evaluation", die solche nur scheinbar zirkulären Def. erlaubt.