How does Haskell's laziness work?

Consider this function that doubles all the elements in a list:

doubleMe [] = []
doubleMe (x:xs) = (2*x):(doubleMe xs)

Then consider the expression

doubleMe (doubleMe [a,b,c])

It seems obvious that, at runtime, this first expands to:

doubleMe ( (2*a):(doubleMe [b,c]) )

(It's obvious because no other possibilities exist as far as I can see).

But my question is this: Why exactly does this now expand to

2*(2*a) : doubleMe( doubleMe [b,c] )

instead of

doubleMe( (2*a):( (2*b) : doubleMe [c] ) )

Intuitively, I know the answer: Because Haskell is lazy. But can someone give me a more precise answer?

Is there something special about lists that causes this, or is the idea more general than that just lists?

Solution

doubleMe (doubleMe [a,b,c]) does not expand to doubleMe ( (2*a):(doubleMe [b,c]) ). It expands to:

case doubleMe [a,b,c] of
  [] -> []
  (x:xs) -> (2*x):(doubleMe xs)

That is the outer function call is expanded first. That's the main difference between a lazy language and a strict one: When expanding a function call, you don't first evaluate the argument - instead you replace the function call with its body and leave the argument as-is for now.

Now the doubleMe needs to be expanded because the pattern matching needs to know the structure of its operand before it can be evaluated, so we get:

case (2*a):(doubleMe [b,c]) of
  [] -> []
  (x:xs) -> (2*x):(doubleMe xs)

Now the pattern matching can be replaced with the body of the second branch because we now know that the second branch is the one that matches. So we substitute (2*a) for x and doubleMe [b, c] for xs, giving us:

(2*(2*a)):(doubleMe (doubleMe [b,c]))

So that's how we arrive at that result.