Seite 1 von 1
endrekursives Fibonacci in Haskell
Verfasst: Samstag 3. August 2013, 22:59
von Blade Runner
Ich find irgendwie kein Haskellforum, aber da hier auch einige Haskell können kann mir vielleicht jemand sagen warum das nur die leere Liste zurückgibt:
Code: Alles auswählen
fib 1000 _ = []
fib _ [] = []
fib n l = fib (n + 1) (l ++ [(last l + last (init l))])
Re: endrekursives Fibonacci in Haskell
Verfasst: Samstag 3. August 2013, 23:45
von BlackJack
@Blade Runner: Erklär mal bitte den ersten Fall. Vielleicht löst das ja schon das Problem. (Den Rest habe ich mir gar nicht erst angeschaut.)
Edit: Okay, ich habe mir den Rest angeschaut, und äh, Häh? Erkläre mal mehr als den ersten Fall. Vielleicht mal alle drei, und dann an einem Beispiel durchgerechnet wie man meinetwegen die 5. Fibonacci-Zahl damit ausrechne. Also den Ausgangsfall und dann wie man durch wiederholtes ersetzen und ausrechnen dann zu dem Ergebnis kommt.
Re: endrekursives Fibonacci in Haskell
Verfasst: Samstag 3. August 2013, 23:57
von Blade Runner
Meine Idee ist dass ich eine Liste erzeuge mit einer gewissen Anzahl an fibonaccizahlen. Also übergebe ich die Liste in der die Anfangszahlen enthalten sind, nehm das letzte und vor letzte Element, häng die Summe an die Liste an und übergeb das ganze dann wieder an die Funktion, sodass die Liste pro Durchlauf länger wird. Im nächsten Funktionsaufruf sollte dann eben die Liste um ein Element angewachsen sein.
Die ersten zwei Zeilen sollen eine Fallunterscheidung darstellen... zumindest nach meinem lückenhaften Haskellverständnis.
Edith: Verdammt, ich glaub ich weiß warum die leere Liste zurückgegeben wird... der Zähler erreicht n und die Rückgabe wird dann einfach auf [] gesetzt. Prinzipiell müsste ja die ganze Liste zurückgegeben werden.
TL;DR: Berechnung stimmt, falsches "if".
Edith 2: Du hattest Recht, ich hab mich in der ersten Zeile verschrieben...
Re: endrekursives Fibonacci in Haskell
Verfasst: Sonntag 4. August 2013, 20:50
von Leonidas
Blade Runner hat geschrieben:Die ersten zwei Zeilen sollen eine Fallunterscheidung darstellen... zumindest nach meinem lückenhaften Haskellverständnis.
Das macht irgendwie nicht wirklich viel Sinn, denn das heißt ja, dass wenn du als n für fib 1000 übergibst, dann ist das Ergebnis die leere Liste. Und für jedes n gilt wenn du als Akkumulator [] verwendest dann ist das Ergebnis [], was auch nicht unbedingt stimmen muss.
Re: endrekursives Fibonacci in Haskell
Verfasst: Sonntag 4. August 2013, 21:03
von Leonidas
Hier mal als Tipp eine Lösung in OCaml:
Code: Alles auswählen
let rec fibs n acc = match n with
| 0 -> acc
| l -> let (fst,snd) = acc in
fibs (l-1) (snd, fst+snd)
let fib n =
let (r, _) = fibs n (0, 1) in
r