Menu
I am quite new to Haskell and I'm trying to wrap my head around how the lazy expression of Fibonacci sequences work.
I know this has been asked before, but none of the answers have addressed an issue I'm having with visualising the result.
The code is the canonical one using zipWith
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
I understand the following:
zipWith literally zips two lists togethertail grabs all but the first element of a listthunks.From my understanding, it first adds [0,1,<thunk>] and [1,<thunk>] using zipWith (+) to give [1,<thunk>]. So now you have
fibs = 0 : 1 : 1 : zipWith (+) fibs (tail fibs)
A lot of references I've Googled have then proceeded to "visualise" the line above as
fibs = 0 : 1 : 1 : zipWith (+) [1,1,<thunk>] ([1,<thunk>]).
My question is this:
Why is the fibs component in the line above only corresponding to [1,1,<thunk>] instead of [0,1,1,<thunk>]?
Shouldn't fibs contain the entire list plus <thunk>?
685
@Zelphir: that would require readers to also be familiar with the golden ratio. Preciseness isn't critical to this argument There are a number of different Haskell algorithms for the Fibonacci sequence here. The "naive" implementation looks like what you're after. fibs : [1, 1, ? tail fibs : [1, ? zipWith (+) fibs (tail fibs): [2, ?
Here's a different and simpler function that calculates the n'th Fibonacci number: fib :: Integer -> Integer fib 0 = 0 fib 1 = 1 fib n = fib (n-1) + fib (n-2)
Fibonacci Sequence (Definition, Formulas and Examples) Fibonacci sequence is defined as the sequence of numbers and each number equal to the sum of two previous numbers. Visit BYJU’S to learn definition, formulas and examples.
There is an alternative Haskell definition for the Fibonacci serie, which would be easier to analyze I think: | fibSerie a b = a : (fibSerie b (a+b)) and then: fibs = fibSerie 1 1. ω = 2 + min ω (ω - 1). zipWith produces an (infinite) list of integers here, not just one integer, so it's not 2 + 1 overall elements, but 2 + ω. which is ω.
This intermediate step is wrong because zipWith has already processed the first pair of items:
fibs = 0 : 1 : 1 : zipWith (+) fibs (tail fibs)
Recall what zipWith does in the general case:
zipWith f (x:xs) (y:ys) = (f x y) : zipWith f xs ys
If you apply the definition directly you get this expansion:
fibs = 0 : 1 : zipWith (+) fibs (tail fibs) # fibs=[0,1,...]
= 0 : 1 : zipWith (+) [0,1,...] (tail [0,1,...]) # tail fibs=[1,...]
= 0 : 1 : zipWith (+) [0,1,...] [1,...] # apply zipWith
= 0 : 1 : (0+1 : zipWith (+) [1,0+1,...] [0+1,...])
= 0 : 1 : 1 : zipWith (+) [1,1,...] [1,...] # apply zipWith
= 0 : 1 : 1 : (1+1 : zipWith (+) [1,1+1,...] [1+1,...])
= 0 : 1 : 1 : 2 : zipWith (+) [1,2,...] [2,...] # apply zipWith
= 0 : 1 : 1 : 2 : (1+2 : zipWith (+) [2,1+2,...] [1+2,...])
= 0 : 1 : 1 : 2 : 3 : zipWith (+) [2,3...] [3,...] # apply zipWith
:
How to visualize what's going on.
1 1 2 3 5 8 13 21 ... <----fibs
1 2 3 5 8 13 21 ... <----The tail of fibs
+_________________________ <----zipWith (+) function
2 3 5 8 13 21 34 ...
Finally, add [1, 1] to the beginning
1, 1, 2, 3, 5, 8, 13, 21, 34, ...
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
