Fibonacci sequence in haskell returning all the values

Question

I need help for my assignment using haskell which return a list up to the nth number in the Fibonacci sequence.

like

Main> fib 5
[0,1,1,2,3,5]
Main> fib 15
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610]

I understand this

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

but I don't know how to produce list that containing all the value up to the nth number.

Thank you

The very simple, but performance-wise idiotic way would be to simply [`map`](http://hackage.haskell.org/packages/archive/base/latest/doc/html/Prelude.html#v:map) `fib` over `[1..n]`. For example: `fibs n = map fib [1..n]`. — gspr, Apr 15 '13 at 10:52
@SenthilPrabhu How would I do it? I'm a very beginner, it would be very helpful if you can give me an example — , Apr 15 '13 at 10:56
@gspr thank you it works, but is there a way to include that(fibs n= map fib[1..n]) into fib function? — , Apr 15 '13 at 10:58
@SahyunKim: http://stackoverflow.com/questions/2803920/fibonacci-numbers-in-haskell — SenthilPrabhu, Apr 15 '13 at 11:00
You can find some nice examples in [fibonacci](http://www.haskell.org/haskellwiki/The_Fibonacci_sequence). Personally I fell in love with the `unfoldr` method. — Bryan Olivier, Apr 15 '13 at 11:10

daniel gratzer · Accepted Answer · 2013-04-15T21:03:19.943

There are a few cool ways to do it, first the simplest

fib::Int->Int
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
fibList n = map fib [1..n]

or we can merge this into one

fib::Int->[Int]
fib 0 = [0]
fib 1 = [1, 0]
fib n = (head (fib (n-1)) + head (fib (n-2))) : fib (n-1)

So here we're just combining the list building with the recursion. Now we take a step towards the crazy

fib n = take n fiblist
  where fiblist = 0:1:(zipWith (+) fiblist (tail fiblist))

Here fiblist is an infinite list of Fibonacci numbers. All we're doing is grabbing the appropriate amount. This is possible because Haskell is "lazy". If you're new to Haskell, just smile and nod.

Lastly, for kicks and giggles

fib = flip take . fix $ \f -> 0 : 1 : (zipWith (+) f (tail f))

This is the same of above except point-free and with a fixed point instead of recursion.

Again if you're new to haskell, the first 2 are a little easier to grok, come back to the last 2 in a few weeks :)

Fibonacci sequence in haskell returning all the values

1 Answers1