Haskell Fibonacci

O

Ook!

0
Hallo!

Ich fummel ein wenig mit Haskell herum und habe gerade ein Beispiel für die Fibonacci-Folge im Netz gefunden und wollte diese einfach mal testen, um zu sehen, was passiert...

Leider kriege ich immer einen "parser Error, possibly incorrect indentation" Error.
Dabei habe ich die Einrückung mehrmals korrigiert und eine unterschiedliche Anzahl an Spaces benutzt...
Vielleicht könnt Ihr mir weiterhelfen!

Code: 
fib :: Int -> Int
fib n
    | n == 0 = 0
    | n == 1 = 1
    | n > 1 = fib (n-1) + fib (n-2)

print fib 17

Gruß
Felix
 
Meine Zeit mit Haskell ist zwar schon ne Weile her, aber was soll
Code: 
    | n > fib (n-1) + fib (n-2)
sein? Mit was vergleichst du da?
 
Aloha lightsaver,

Habe mich vertippt, es sollte eigentlich so aussehen:
Code: 
n > 1 = fib (n-1) + fib(n-2)
Ich werds editieren!
 
Also lass mal die print-Zeile weg und speicher den Rest mal als fib.hs oder so.
Dann kannst du die Datei in dem Haskell-Interpreter laden und dann mit fib 17 z.B. aufrufen. Alternativ kannst du dann auch print (fib 17) verwenden, die Klammerung ist dabei aber dann wichtig
 
Sehr schön... Danke!
Eine weitere Möglichkeit, die auch funktioniert:
Code: 
main = print (fib 17)


Wie kann ich nun die Liste mit einem Komma und einem Space joinen, wie es in Python möglich ist?
Code: 
fibs :: [Int]
fibs = 0 : 1 : [ a + b | (a, b) <- zip fibs (tail fibs) ]
-- mit dem Aufruf
print (take 7 fibs)

", ".join([ 0, 1, 1, 2, 3, 5, 8 ])
>> "0, 1, 1, 2, 3, 5, 8"
Gruß
Felix
 
Mir ist grad nicht so ganz klar, was du genau möchtest, gib mal nochmal ein konkretes Beispiel, wie es vorher und nachher aussehen soll
 
Kleine Verbesserung für deine Variante(man braucht bei dem Beispiel keine guards, pattern matching auf die Argumente reicht):
Code: 
fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
Das ist meines Erachtens ein bisschen lesbarer.

Eine weitere schöne Möglichkeit ist:
Code: 
fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
Dadurch hast du eine unendlich lange Liste aller Fibonacci-Zahlen, die bei Zugriff berechnet werden(da haskell lazy/non-strict ist, geht sowas). Das ganze läuft in O(n) und Listenzugriffe werden gespeichert, d.h. beim zweiten Zugriff auf ein Element muss nicht alles neuberechnet werden.

Mit fibs !! 17 bekommst du z.B. die 17.te Fibonacci-Zahl, take 10 fibs liefert eine Liste mit den ersten 10.
(Oh, Ich habe übersehen, dass du fast die selbe Variante oben schon erwähnt hattest)

Für deine join-Geschichte könntest du das verwenden:
Code: 
import Data.List

join :: Show a => String -> [a] -> String
join delim xs = concat . intersperse delim $ map show xs
(Das sieht ein bisschen komplizierter aus, weil intersperse ein wenig allgemeiner ist als pythons join und für alle Listen funktioniert, wie etwa intersperse 42 [1,2,3] == [1,42,2,42,3])

Das liefert dann:
Code: 
> join ", " [1,2,3]
"1, 2, 3"
 
Sehr schön - Danke, Daniel!

Kannst du mir die zwei Zeilen erklären, bitte?
Code: 
(1.) join :: Show a => String -> [a] -> String
(2.) join delim xs = concat . intersperse delim $ map show xs
Die Import-Anweisung wird benötigt, weil die Funktion "interperse" in Data.List liegt (denk ich mal).

Ich habe ein Problem damit, den Punkt 2 zu verstehen!
Was ich bisher weiss ist, dass interperse in etwa so definiert ist "interperse <zeichen> <list>".
Was soll jedoch der . bei concat, das $ vor map oder das "show xs"?
Das sind so die Stolpersteine, an denen ich knabbere :)

Gruß
Felix
 
Zu (1): Das ist die Typsignatur von join, die man eigentlich auch weglassen könnte, es aber zur Klarheit des Codes beiträgt(Haskell kann den Typ einer Funktion meistens selbst ableiten(Stichwort: type inference)). Show ist eine sog. type class, teilweise vergleichbar mit Interfaces aus Java; Concepts in C++ sind genau dieses Feature direkt aus Haskell übernommen. Jeder Datentyp dieser Typklasse stellt u.a. die Funktion show zu Verfügung, die aus dem Datentyp einen String macht, z.B. show 1 == "1". Durch Show a => .. sagt man aus, dass diese Funktion für jeden Typ a definiert ist, der eine Instanz von Show ist. Der erste Parameter ist ein String, der zweite vom Typ a und das Ergebnis wieder vom Typ String(Genau genommen hat jede Funktion in Haskell nur 1 Parameter und gibt dann quasi eine weitere Funktion zurück(Stichwort: currying)).

Zu (2): intersperse hat den Typ a -> [a] -> [a]. Das heißt, es nimmt ein Element eines beliebigen Typs a, eine Liste aus as und gibt eine Liste aus as zurück. In diesem Fall fügt es zwischen die Elemente der Liste jeweils den ersten Parameter ein. Der '.'-Operator ist im Grunde das selbe wie der Punkt-Operator zur Verkettung von Funktionen aus der Mathematik. Der '$'-Operator wendet die Funktion links von ihm auf das Argument rechts an und wird hier nur von mir verwendet um Klammern zu vermeiden, was möglich ist, da der Operator eine besonders niedrige Präzedenz hat(Man kann in Haskell Operatoren und ihre "Bindungsstärke" selbst definieren). Ebenso gültig wäre:
Code: 
concat (intersperse delim (map show xs))
Aber für einen Nicht-LISPer wird sowas schnell weniger lesbar als die erste Variante. "concat . intersperse delim" verkettet also concat und intersperse delim(Interessant ist hier auch die teilweise Anwendung von intersperse, die dann wieder eine Funktion zurückgibt) und liefert somit eine Funktion die zuerst intersperse delim auf das Argument und dann concat auf das Ergebnis dessen anwendet. Beispiel:
concat . intersperse ", " $ ["1","2"]
==
concat (intersperse ", " ["1","2"])
==
concat ["1",", ","2"]
==
"1, 2"

show wandelt seinen Parameter in einen String um, wenn der Typ des Parameters Instanz der Typklasse Show ist, ersichtlich am Typ von show: Show s => s -> String.
Das "=>" kann man damit als so eine Art Implikation wie aus der Mathematik verstehen. Aus der Zugehörigkeit des Typs s zu Show folgt eine Funktion mit Typ s -> String. Durch map show xs macht man also aus der übergebenen Liste aus as eine Liste aus Strings, was nötig ist, da man bei intersperse einen String in diese einfügen will und Listen in Haskell immer aus Elementen eines Typs bestehen.
Neben zahlreichen Texten, gibt es auch einen Vortrag in dem diese Sachen sehr gut erläutert werden:
http://blip.tv/file/324976 und http://blip.tv/file/325646
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben