Understanding concatMap recursion

Question

I am overall confused, and looking for a very detailed and explanatory answer, of how this code works:

let xs = [1] ++ concatMap (\x -> [x+1,x*10]) xs in xs

How does concatMap know what to map and concat over?

I understand more basic examples:

let x = [1] ++ x

Here it gets evaluated like [1] ++ [1] ++ [1] ..

But I don't seem to understand the first example with concatMap. It just doesn't make sense to me. I can work with recursion frequently without problems. However, that one piece of code is very confusing.

Answer 1

Let's try a much simpler example:

let xs = 1 : xs in xs

OK, so xs points to a (:) node. The head-pointer from here points to 1, and the tail-pointer points to xs (i.e., back to itself). So this is either a circular list, or an infinite list. (Haskell regards the two as the same thing.) So far, so good.

Now, let's try a harder example:

let xs = 1 : map (+1) xs in xs

Do you know what this will do?

So xs points to a (:) node. The head-pointer points to 1. The tail-pointer points to the expression map (+1) xs, with xs pointing back to the top again.

If you try to "look at" the contents of this list, it will cause the map expression to start executing. The definition of map is

map f js =
  case js of
    k:ks -> (f k) : (map f ks)
    []   -> []

So map looks at xs to see if it's [] or (:). As we know, it's (:). So the first pattern applies.

What this means is that the entire map (+1) xs expression gets overwritten with (:), with its head-pointer pointing to (+1) 1 and its tail-pointer pointing to map (+1) xs2 (with xs2 denoting a pointer to the tail of xs).

At this point, inspecting (+1) 1 turns it into 2. So now we basically have

xs = 1 : 2 : map (+1) xs2
           ^           |
           |___________|

This cycle repeats as you examine the list. Critically, at every moment map is pointing to a node just before itself. If it ever caught up to itself, you would have a problem. But map only ever looks at nodes we've already calculated, so it's fine.

The net result, then, is xs = 1 : 2 : 3 : 4 : ...

If you can understand that, you ought to be able to understand your own more complicated example.

If you want to make your head hurt, try:

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

This is a standard Haskell incantation for spitting out the Fibonacci numbers in O(N) time (rather than O(N*N) as the more obvious recursion would give you).