Understanding Haskell's fibonacci

Question

fibs :: [Int]
fibs = 0 : 1 : [ a + b | (a, b) <- zip fibs (tail fibs)]

This generates the Fibonacci sequence.

I understand the behaviour of the guards, of :, zip and tail, but I don't understand <-. What is it doing here?

Answer 1

How would the parser know what goes into (a,b) otherwise?

EDIT: Thanks to ViralShah, I will make this a little less gnomic. The "<-" tells the parser to assign the list of pairs from the right side "zip fibs (tail fibs)" to the left side "(a,b)".

Answer 2

The list comprehension in the brackets:

[ a + b | (a, b) <- zip fibs (tail fibs)]

returns a list containing the output (a + b) where the variables a and b come from the result of

zip fibs (tail fibs)

Answer 3

Due to the upvotes I made my comment into an answer.

What you see is not a guard but it is list comprehension. For starters think of it as a way to express a mathematical set notation like A = { x | x element N } which means something along the lines of: The set A is the set of all natural numbers. In list comprehension that would be [x | x <- [1..] ].

You can also use constraints on your numbers: [x | x <- [1..], x `mod` 2 == 0 ] and many other things.

There are alot of good haskell turorials out there that cover list comprehension and even a StackOverflow question regarding haskell resources.

Answer 4

The only tricky thing is the zip fibs (tail fibs). zip just makes a pairwise list from each of its arguments. So if you have two lists like this:

[ 1, 2, 3, 4 ]
[ "a", "b", "c", "d" ]

Zipping them will make:

[ (1,"a"), (2,"b"), (3,"c"), (4,"d") ]

The left arrow (assignment into a destructuring pattern) just extracts the paired elements so they can be added together. The two lists being zipped are fibs and (tail fibs) -- in other words, the Fibonacci sequence, and the Fibonacci sequence offset by 1 element. Haskell is lazily-evaluated, so it can calculate the list to however many elements are required. This applies to zip as well.

Answer 5

Let's expand it out.

zip creates pairs out of the contents of two lists. So the first pair zip fibs (tail fibs) gives us is (0, 1), which adds up to 1. So now the list is [0,1,1]. We now know three elements in the list, so the list comprehension can continue, grabbing the next item from the list and the next item from the tail, which gives (1,1) — added together, making 2. Then we get the next pair, which is (1,2), making the next number in the sequence 3. This can continue infinitely, since the comprehension will always provide enough items.

Answer 6

For what it's worth, I find the following version easier to understand:

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