Understanding Haskell's fibonacci

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开发者_如何学Go :, zip and tail, but I don't understand <-. What is it doing here?

---

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.

---

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.

---

One advantage of functional programming is that you can evaluate an expression by hand like it is a math problem:

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

Here the ?? is the part which has not yet been evaluated. We will fill it in as we proceed.

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

Note that I am eliding the evaluation of zip since its definition is not given here and the details are not really germane to the current question. This is the notation I will use to show each pair of numbers is created by zip and consumed by the list comprehension.

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

Now we know that the next element in the ?? is a 1:

     = 0 : 1 : 1 : [ a + b | (a, b) <- zip [1, 1, ??] [1, ??]]
     = 0 : 1 : 1 : [ a + b | (a, b) <- (1, 1) : zip [1, ??] [??]]
     = 0 : 1 : 1 : 1+1 : [ a + b | (a, b) <- zip [1, ??] [??]]
     = 0 : 1 : 1 : 2 : [ a + b | (a, b) <- zip [1, ??] [??]]

And the next element is a 2:

     = 0 : 1 : 1 : 2 : [ a + b | (a, b) <- zip [1, 2, ??] [2, ??]]

Rinse and repeat.

---

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.

---

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

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

---

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)

---

The key concept here is lazy evaluation which means that if the value is right there then take it without further computing say that i have got the value and the job is done, i don't need to compute future value temporary now. and if the value is not available then just compute it and of course it's lazy so it won't bother computing next needed value.

i write another implementation to illustrate this and use ?? to be a value placeholder which needs to be computed if needed.

fibs = 1:1:[ y!!1 + y!!0 | x<-[2..], y <- [[last (take x fibs), last (take (x-1) fibs)]] ]

i use x to indicate number of available values in fibs (which doesn't need to be computed again) and y to be a [[last fib values]] nested list. its inner list contains last two values of available values in fibs.

so here is the process of the computation:

1. x == 2, so y is [last (take 2 fibs), last (take 1 fibs)]. lazy evaluation lets us just take available values and don't bother worrying values in the future. it tells me to take first 2 and 1 values of fibs and the values are right there 1,1 and 1. y now is [last [1,1], last [1]] which is [1,1] and to get final value it need to compute y!!1 + y!!0. That's obvious and final value is 2. so now fibs is [1, 1, 2, ??].
2. x == 3, just the same as step 1. y is [last [take 3 fibs], last [take 2 fibs]] which is [last [1,1,2], last [1,1]], the value now is available so we can just take it and go on. Finally, we got the fourth value 3.
3. that's it, just repeat the above steps and you can get all values even it is infinite

Doesn't it seems familiar? just like using a recursive function to compute fibs. we now let compiler itself to do the stuff(referring). we use the lazy evaluation here.

the zip implementation is just another representation of [last fibs values] here. you just need a little modification to understand the zip version of fibs implementation.

1. haskell wiki: lazy evaluation

2. for <- symbol: List comprehension

---

I prefer the more general

fib = 1 : [ x + y | (x, y) <- zip fib (0 : fib) ]

This most closely models how one understands the Fibonacci sequence in terms of generating functions. If f(n) = 0 for n < 0, f(0) = 1, and f(n) = a*f(n-1) + b*f(n-2) for n > 0, then we'd like to be able to write the single line

f(n) = 1_0 + a*f(n-1) + b*f(n-2)

and have the reader know what we mean. Unfortunately, this requires some unstated conventions to make sense.

Using the generating function g(t) = f(0) + f(1)t + f(2)t^2 + ... we can write the equation

g(t) = 1 + a t g(t) + b t^2 g(t)

which easily solves for g(t) in closed form as

g(t) = 1 / (1 - a t - b t^2)

The Haskell code

g = 1 : [ a*x + b*y | (x, y) <- zip g (0 : g) ]

implements this same equation.

---

It defines this stream diagram,^(*)

             .---->>---->>----.
            /                  \ 
     <---- 0 <---- 1 ----<<--- (+) 
                    \          / 
                     *--->>---* 

that pulls new input from itself as it is produced, but always by one and two positions behind the production point, maintaining the two "back pointers" into the sequence as it were, one position apart.

This is reflected in the definition,

--         .------->>------>>---.
--        /                      \
fibs  =  0 : 1 : [ a + b | a <- fibs 
{-            \  -}      | b <- tail fibs]
--             \                 /
--              *-->>------>>---*

with parallel list comprehensions (:set -XParallelListComp etc.).

Since it only uses its last two elements, it is equivalent to

    map fst . iterate (\(a, b) -> (b, a+b)) $ (0,1)

---

^(*) The execution of this diagram proceeds as follows:

                 .---->>---->>----.
                /                  \     0
       ? <---- 0 <---- 1 ----<<--- (+) 
                        \          /     1
                         *--->>---* 

                 .---->>---->>----.
                /                  \     1
     0,? <---- 1 <---- 1 ----<<--- (+) 
                        \          /     1
                         *--->>---* 

                 .---->>---->>----.
                /                  \     1
   0,1,? <---- 1 <---- 2 ----<<--- (+) 
                        \          /     2
                         *--->>---* 

                  .--->>---->>----.
                 /                 \     2
   0,1,1,? <--- 2 <--- 3 ----<<--- (+) 
                        \          /     3
                         *--->>---* 

                    .--->>--->>---.
                   /               \     3
   0,1,1,2,? <--- 3 <-- 5 ---<<--- (+) 
                        \          /     5
                         *--->>---* 
 ......