CODEWITHSUNDEEP
listhaskelllazy-evaluationfibonacciinfinite
Сергей Кузминский
Сергей Кузминский

Reputation: 367

Create infinite list with Fibonacci numbers

I make my next homework =) My task is to create infinite list with fibonacci numbers [0,1,1,2,3,5,8..] I can use any function from Prelude.

My try:

fibs2 :: [Integer]
fibs2 = reverse $ foldr f [1,0] [0..]
  where 
        f _ (x:y:xs) = (x+y):x:y:xs

this function works only with finite lists like [0..100] with infinite list it gives:

*** Exception: stack overflow

what i do wrong? how to make "lazy" function?

UPDATE my second try:

fibs4 = 0:[ b | (a, b) <- scanl (\(x,y) _ -> (y,x + y)) (0,1) [0..] ]

it works right. :) it's normal or strange?

Upvotes: 2

Views: 2099

Answers (2)

Will Ness
Will Ness

Reputation: 71065

foldr (with a strict combining function) deconstructs an argument list to its very end, and then recombines it through the user-supplied combining function f:

foldr f z [a,b,c,...,y] = f a (f b (f c (.....(f y z).....)))

in your case, 

fibs2 = reverse $ foldr (\_ (x:y:xs) -> (x+y):x:y:xs) [1,0] [0..]

foldr here never produces any output. But it's not for the lack of trying: it works very hard recursing down the infinite list in search of its end, because its combining function is strict (it matches the rest of foldr's output with (x:y:xs) before constructing its own result).

Foldr with a strict combining function expresses recursion, and recursion must have its base case, to stop. What you had in mind is the following:

fibs2 = reverse $ snd $ until (null.fst) 
         (\(_t:ts, x:y:xs) -> (ts, (x+y):x:y:xs)) ([0..],[1,0])

which is manifestly non-terminating. ts just expresses the passing moments of time. We can try to see the whole history of its execution, re-writing it as

fibs2 = reverse $ snd $ last $ iterate
         (\(_t:ts, x:y:xs) -> (ts, (x+y):x:y:xs)) ([0..],[1,0])

Of course there's no last element in the infinite list. But we can at least see all the interim results now:

> mapM_ (print.reverse.snd) $ take 11 $ iterate 
          (\(_:ts, x:y:xs) -> (ts, (x+y):x:y:xs)) ([0..],[1,0])
[0,1]
[0,1,1]
[0,1,1,2]
[0,1,1,2,3]
[0,1,1,2,3,5]
[0,1,1,2,3,5,8]
[0,1,1,2,3,5,8,13]
[0,1,1,2,3,5,8,13,21]
[0,1,1,2,3,5,8,13,21,34]
[0,1,1,2,3,5,8,13,21,34,55]
[0,1,1,2,3,5,8,13,21,34,55,89]

So instead of waiting until the very last list is built (which will be never) and then reversing it, why not produce its elements as we go? It's all there already, anyway. And the last element of each interim result, reversed - isn't it just its first element?

> take 11 $ map (head.snd) $ iterate 
          (\(_:ts, x:y:xs) -> (ts, (x+y):x:y:xs)) ([0..],[1,0])
[1,1,2,3,5,8,13,21,34,55,89]

Neat, huh. So do we need our explicit time counter, really? Do we need to drag along the whole tail of the previous interim result, or do we just need its first two elements?

fibs = map (head.tail) $ iterate (\[x,y] -> [x+y,x]) [1,0]

Using tuples for constant length lists will be a bit cleaner. So you see that we've arrived here at one of the canonical definitions,

fibs = g (1,0)  where  g (a,b) = b : g (a+b,a)

(see also What's the difference between recursion and corecursion?).

your "second try",

fibs4 = 0:[ b | (a, b) <- scanl (\(x,y) _ -> (y,x + y)) (0,1) [0..] ]

is actually very close to the above as you can see. scanl over the time-counting list is just equivalent to iterate. So it's equivalent to

fibs4a = [a | (a,b) <- iterate (\(a,b) -> (b, a+b)) (0,1)]

which we've seen in the derivation above as a map variant, with tuples used instead of lists.

Upvotes: 7

rafalio
rafalio

Reputation: 3946

Yep, you can't reverse an infinite array.

Have a look at this:

0,1,1,2,3,5,8,13,21,...
  0,1,1,2,3,5,8, 13...   +
----------------------
0,1,2,3,5,8,13,21,...

As you can see from my attempt at showing the relationship how the Fibonacci sequence can be generated using itself, it is quite easy! You would zipWith fibonacci with its tails using the addition function!

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

For a little bit more detail, here is an expansion of the above.

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
fibs = 0 : 1 : zipWith (+) 0:1:? 1:?
fibs = 0 : 1 : (0+1) : zipWith (+) 1:? ?
fibs = 0 : 1 : 1 : zipWith (+) 1:1:? 1:?
fibs = 0 : 1 : 1 : 2 : zipWith (+) 1:2:? 2:?
fibs = 0 : 1 : 1 : 2 : 3 : zipWith (+) 2:3:? 3:?

ad infinitum... The ? represents a thunk, a yet unevaluated piece of Haskell computation.

Upvotes: 3

Related Questions