endrekursives Fibonacci in Haskell

[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))])

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

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

[Leonidas]

Die ersten zwei Zeilen sollen eine Fallunterscheidung darstellen... zumindest nach meinem lückenhaften Haskellverständnis.

Code: Alles auswählen

fib 1000 _ = []
fib _ [] = []

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.

[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