[Haskell] fibonacci definition verstehen...

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.

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

knivil

Die Gleichung funktioniert rein durch das Substitutionsprinzip. Ist aber zu unübersichtlich um das mal durchzuexerzieren.

Ich habe es doch fuer dich gemacht.

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

Wenn man mit dem Unendlichen spielt, sollte man wissen, ob eine Funktion lazy ist oder nicht.

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

Die Fibonacci's kann man auf unterschiedliche Weise definieren. Wenn fuer dich Effizienz keine Rolle spielt, ist das ok, aber fuer andere. Deswegen haben sie die Folge mit zipWith definiert, anstatt diese mathematische Definition zu benutzen (deswegen "macht man so"). Hier sind weitere Beispiele (auch ohne Selbstreferenz): http://www.haskell.org/haskellwiki/The_Fibonacci_sequence

Ich würde gerne dieses Sprachfeature auf Basis seiner eigenen Abstraktionsebene verstehen .. Alles was ich wissen wollte war ein Gedankenmodell, mit dem man solche Ausdrücke hinreichend analysieren kann.

Substitutionsprinzip. Ich habe gezeigt wie. "Pointer" waren nur eine Randbemerkung und nicht zentraler Gegenstand.

nicht auf Elementbasis sondern auf Listenbasis interpretieren muss

Ja, Listen bestehen aus Elementen. Der eine sagt: Alles ganz einfach, stelle es dir als Erdbeere vor. Fuer den anderen ist es aber leichter es als Bananen zu sehen. Das weiss ich nicht, deswegen erklaere ich es als Erdbeere.

Als Abschluss kann ich dir Introduction to Functional Programming using Haskell empfehlen. Es gibt auch eine deutsche Variante, dort sind aber die Funktionen wie zip auch uebersetzt (Reissverschluss). Das finde ich sehr schlecht (wobei es einige gute (billigere) Alternativen gibt). Magst du eher was visuelles, sei auf C9 Lectures: Dr. Erik Meijer verwiesen. Einfach mal suchen.

otze

mngbd schrieb:

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).

knivil hatte ja schon eine gebracht, meinte aber, es gäbe eine bessere. Ich hab jetzt noch nicht so große Ahnung mit Haskell, aber ist es eventuell sowas?

zipWith f xs ys=foldr (\(x,y) l-> (f x y):l) $ zip xs ys

zumindest tut sie in meinem Beispiel, was sie tun sollte. Auch wenn ich knivils Version übersichtlicher fand.

@knivil Danke für die Buchvorlage. Und auch nochmal generell danke für deine Zeit die du geopfert hast! Wollte dich jetzt nicht anfahren oder so. Das Buch schaue ich mir definitiv mal an(englische Literatur bereitet mir keine Probleme mehr), bislang hab ich leider nur dieses Tutorial verwenden können:
http://learnyouahaskell.com/
Finde aber, dass es nicht allzu schlecht gemacht ist.

mngbd

otze schrieb:

Ich würde gerne dieses Sprachfeature auf Basis seiner eigenen Abstraktionsebene verstehen.

Noch ein Versuch:

Der Kernpunkt bei der Interpretation ist, dass die fibs-Folge im Speicher immer länger wird, wenn man immer höhere n als Indizes nimmt. Das macht die Sprache automatisch. Man kann deine Variante in einer imperativen Sprache etwa so nachbauen (hoffentlich verstehst du ein wenig Python):

# eine Liste mit dem nullten und dem ersten Element                                                                                               
fibs_list = [0, 1]

def fibs(n):
    # wenn das n-te Element noch nicht in der Liste ist                                                                                           
    if n >= len(fibs_list):

        # alle Elemente bis zum n-ten in die Liste eintragen                                                                                      
        i = len(fibs_list)
        while i <= n:
            fibs_list.append(fibs_list[i - 1] + fibs_list[i - 2])
            i = i + 1

    # jetzt geht die Liste genau bis zum n-ten Element                                                                                            
    return fibs_list[n]

Wie kann man die kanonische Formulierung am besten auf eine imperative Sprache übertragen?

knivil

Das verlinkte Tutorial ist gut. Kann jetzt auch nicht sagen, ob das Buch von Richard Bird darueber hinausgeht, hat aber mehr Beispiele.

mngbd schrieb:

Wie kann man die kanonische Formulierung am besten auf eine imperative Sprache übertragen?

Schwierig. Wahrscheinlich wuerde man es einfach anders machen. Es gab mal 'nen Thread in dem das fuer Scheme/Lisp diskutiert wurde. Finde ihn aber nicht wieder.

Wollte dich jetzt nicht anfahren oder so.

Ich habe manchmal schlechte Tage. Ist schon ok, ich war vielleicht etwas zu direkt.

mngbd

otze schrieb:

Ich hab jetzt noch nicht so große Ahnung mit Haskell, aber ist es eventuell sowas?
zipWith f xs ys=foldr (\(x,y) l-> (f x y):l) $ zip xs ys

Ich hab auch nicht viel Ahnung von Haskell. Aber wenn's läuft, dann läuft's, dafür sind Abstraktionen ja da. Wie gut das geworden ist, kann ich dir leider nicht sagen.

knivil schrieb:

Es gab mal 'nen Thread in dem das fuer Scheme/Lisp diskutiert wurde. Finde ihn aber nicht wieder.

Meinst du den?
http://www.c-plusplus.net/forum/viewtopic-var-t-is-259054.html

knivil schrieb:

Schwierig. Wahrscheinlich wuerde man es einfach anders machen.

Ja, schwierig. Ich muss jetzt weg, aber vielleicht fällt mir später noch was ein, womit man den Unterschied verdeutlichen kann.

Edit: phpBB-Syntax

Ich habe manchmal schlechte Tage. Ist schon ok, ich war vielleicht etwas zu direkt.

ach mach' dir nichts draus. Der Preis für die am sorgfältigsten ausgefeilten Beiträge ist Dir sicher:

Beitrag knivil Mitglied 10:45:33 16.04.2010
[...]
Zuletzt bearbeitet von knivil am 11:09:44 16.04.2010, insgesamt 11-mal bearbeitet

wow, 11-mal bearbeitet in 24:11 Minuten - das ist Rekord