[Haskell] fibonacci definition verstehen...

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

knivil

zum Beispiel schrieb:

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

Rechtschreibfehler, Formulierungen, Ergaenzungen, ... die Arbeit macht man sich manchmal, wenn man eine qualifiziert Antwort geben will. Manchmal beschraenke ich mich aber auch auf ein einfaches Bullshit. Sieh es also so: Ich hatte einen guten Tag.