self-reference in Haskell functions

Question

I am learning Haskell and I the following expression on Haskell Wiki really puzzled me:

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

I can't quite figure out why this works.

If I apply standard Currying logic (zipWith (+)) returns a function takes list as an argument and, in turn, returns another function that takes another list as an argument, and returns a list (zipWith::(a -> b -> c) -> [a] -> [b] -> [c]). So, fibs is a reference to a list (that has not yet been evaluated) and (tail fibs) is the tail of the same (unevaluated) list. When we try to evaluate (take 10 fibs), the first two elements are bound to 0 and 1. In other words fibs==[0,1,?,?...] and (tail fibs)==[1,?,?,?]. After the first addition completes fibs becomes [0,1,0+1,?,..]. Similarly, after the second addition we get [0,1,0+1,1+(0+1),?,?..]

• Is my logic correct?
• Is there a simpler way to explain this? (any insights from people who know what Haskell complier does with this code?) (links and reference are welcome)
• It is true that this type of code only works because of lazy evaluation?
• What evaluations happen when I do fibs !! 4?
• Does this code assume that zipWith processes elements first to last? (I think it should not, but I don't understand why not)

EDIT2: I just found the above question asked and well answered here. I am sorry if I wasted anyone's time.

EDIT: here is a more difficult case to understand (source: Project Euler forums):

filterAbort :: (a -> Bool) -> [a] -> [a]
filterAbort p (x:xs) = if p x then x : filterAbort p xs else []

main :: Int
main = primelist !! 10000
         where primelist = 2 : 3 : 5 : [ x | x <- [7..], odd x, all (\y -> x `mod` y /= 0) (filterAbort (<= (ceiling (sqrt (fromIntegral x)))) primelist) ]

Note that all (\y -> x mod y /= 0)... How can referring to x here NOT cause infinite recursion?

Answer 1

I'll trace the evaluation for you:

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

With:

> zipWith f (a:as) (b:bs) = f a b : zipWith f as bs
> zipWith _ _      _      = []

> tail (_:xs)             =  xs
> tail []                 =  error "tail" 

So:

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

Etc. So if you index into this structure, it will force each step of fibs to be evaluated until the index is found.

Why is this efficient? One word: sharing.

As fibs is computed, it grows in the heap, recording values that have been computer. Later back references to fibs get to reuse all previously computed values for fibs. Free memoization!

What does that sharing look like in the heap?

As you ask for the object on the end of the list, Haskell computes the next value, records it, and moves that self-reference down a node.

The fact this terminates relies crucially on laziness.