[Haskell] fibonacci definition verstehen...

[zum Beispiel]

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.

[zum Beispiel]

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.

[knivil]

otze schrieb:

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.

Und wie effizient ist diese Implementation? Ausserdem wirkt hier list comprehension eher unschoen. Das Problem: Deine Anschauung kommt aus der imperativen Welt ohne laziness. Das verwirrt nur unnoetig. Mein Rat: vergiss alles (wirklich alles) aus anderen Sprachen und starte bei Null.

[otze]

knivil schrieb:

Das Problem: Deine Anschauung kommt aus der imperativen Welt ohne laziness.

Es ist eigentlich 1:1 die mathematische Definition der Fibonacci Reihe.

a_0=0
a_1=1
a_n=a_{n-1}+a_{n-2} für alle n>=2

hat also nichts mit imperativer Programmierung zu tun.Weiß auch nicht, wo du die witterst. Aber seis drum. Das sagst du schon seit deinem ersten Post - ausgeführt hast du dieses Argument aber noch nicht. So bleibt das ein ewiges "du programmierst imperativ" - "nö, das ist die mathematische Definition" - "doch" - "nö" -"doch"...

Ein anderer Punkt: momentan ließt sich dein Post wie "macht man so". Daran habe ich aber nie gezweifelt. Ich habe nie die Effizienzfrage oder ähnliches gestellt. Deswegen wundert mich die Schärfe deines Posts etwas. Alles was ich wissen wollte war ein Gedankenmodell, mit dem man solche Ausdrücke hinreichend analysieren kann. Leider hat mir dabei deine durchaus imperative Erklärmethode mit den Listenzeigern nicht weitergeholfen. Ich würde gerne dieses Sprachfeature auf Basis seiner eigenen Abstraktionsebene verstehen.

mngbds Posts waren da wesentlich zielführender, als dass er ausgedrückt hat, dass man diesen Ausdruck nicht auf Elementbasis sondern auf Listenbasis interpretieren muss (danke dafür). Und da muss ich sagen, dass diese Definition auf einmal wesentlich mehr Sinn macht. Am Ende bleiben beide Sichtweisen Elementweise und Listenweise rein funktional. Hier ist nichts imperatives in keinem der Ansätze. Nur, dass die Liste halt die öhere Abstraktionsebene ist. Und vielleicht auch effizienter, aber das interessiert mich grad weniger.

[mngbd]

knivil schrieb:

otze schrieb:

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

Das verwirrt nur unnoetig.

Finde ich auch. Vergleichen wir das noch einmal mit der kanonischen Formulierung, und zählen wir die Tokens:

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

Das sind 15, alle Klammern mitgezählt.

In deinem Beispiel sind es dann 30. Das deutet darauf hin, dass die syntaktische Struktur deiner Formulierung ca. doppelt so schwer zu erfassen ist (wobei man darüber streiten kann, ob es richtig ist, jede Klammer als einen ganzen Token zu zählen). Als nächstes müssen wir uns fragen, ob die kürzere Formulierung nur deshalb kürzer ist, weil sie vielleicht einen dreckigen Hack verwendet. Das tut sie aber nicht, weil die Laziness (Bedarfsauswertung) eine der erklärten Annehmlichkeiten solcher Sprachen ist.

Dann bleibt noch die Abstraktion zipWith . Dass sie nützlich ist, sieht man schon daran, dass man sie in der kanonischen fibs-Definition verwendet. Versuch mal, zur Übung, zipWith zu schreiben, oder auch nur eine konkretere Variante davon, die zwei Folgen addiert (dann aber, ohne auf auf zipWith zurückzugreifen).

otze schrieb:

Es ist eigentlich 1:1 die mathematische Definition der Fibonacci Reihe.

Nun ist aber die Mathematik auch nur eine Sprache. Zumindest von unserem momentanen Standpunkt aus gesehen. Wenn Mathe einen allgemein bekannten Operator für das Verschieben von Folgen hätte, würde man vielleicht lieber diesen verwenden.

knivil und ich haben das scheinbar aus dem SICP-Kapitel über "Streams" gelernt (so werden Folgen, die lazy sind, in Scheme genannt):
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.html

Weil SICP ein gutes Buch ist, hat uns das gereicht, um die grundlegende Haskell-Semantik zu verstehen. Vielleicht hilft es auch dir, einen Interpreter zu schreiben, der lazy ist. Es gibt aber sicher auch gute Bücher über Haskell, in denen das verständlich rüberkommt. Wenn du sowas suchst, steig am besten auf Englisch um und frag im Usenet oder auf reddit nach.

[mngbd]

otze schrieb:

mngbds Posts waren da wesentlich zielführender, als dass er ausgedrückt hat, dass man diesen Ausdruck nicht auf Elementbasis sondern auf Listenbasis interpretieren muss (danke dafür).

Es gibt eigentlich zwei grundlegend verschiedene Strategien, wie man solche Dinge erklären kann. Die eine versucht, aufzuzeigen, wie man einen Interpreter für solche Ausdrücke schreiben kann; die andere versucht, sie auf die natürliche Sprache und das damit verknüpfte "eingebaute" Denken zurückzuführen.

Weil es mir Spass macht, mit zu knivil diskutieren, habe ich die beiden Strategien vielleicht nicht sorgsam genug getrennt.

Edit: Grammatik