Why is this evaluated like this?

Question

I have the function

doubleMe :: Num a => [a] -> [a]
doubleMe [] = []
doubleMe (x:xs) = (2*x):(doubleMe xs)

Consider this:

doubleMe(doubleMe([1,2,3]))

The first step is obviously

doubleMe(doubleMe([1,2,3])) = doubleMe(2:doubleMe[2,3])

because there are no other possibilities.

It's the next step that I'm wondering about. Why exactly is

doubleMe(2:doubleMe[2,3]) = 4:(doubleMe(doubleMe([2,3])))

instead of

doubleMe(2:doubleMe[2,3]) = doubleMe(2:4:doubleMe([3]))

?

The only answer I've been able to come up with so far is

Because it makes sense. Otherwise Haskell wouldn't act lazily on lists.

But this is not an answer but a copout. What's the real answer?

Answer 1

The first step is obviously doubleMe(doubleMe([1,2,3])) = doubleMe(2:doubleMe[2,3])

Well actually not obviously!

For sake of distinguishability,

doubleMe' = doubleMe

and consider

doubleMe' $ doubleMe [1,2,3]

The only reason that the first step goes as you said, namely

≡ doubleMe' $ 2 : doubleMe [2,3]

is because doubleMe' needs to be able to match its argument to either [] or _:_. To do that, the runtime starts evaluating doubleMe [1,2,3] a bit, namely one recursion step. That yields 2 : doubleMe [2,3], enough for doubleMe' to work with:

≡ 4 : doubleMe' (doubleMe [2,3])

---

Note that actually this evaluation order is not required by the language: the compiler would be allowed to reorder it (e.g. for performance reasons), so actually the inner list is processed completely right away – if it can prove that this does not change the semantics, i.e. for an infinite list, doubleMe [1..] must not get stuck in an eternal loop if you only ask for the first few results.

GHC does not do such reordering.

Answer 2

The important thing to realise is that case and only case causes evaluation in Haskell[1]. Therefore when you say "Consider this:"

doubleMe(doubleMe([1,2,3]))

it's vitally important to say what about it we are considering. Evaluation does not happen a side effect of function application in Haskell[1]. The only thing that that can cause (part of) it to be evaluated is a case statement which pattern matches on it. So how does case work here?

Well

case doubleMe (doubleMe [1,2,3]) of
    []     -> ...
    x : xs -> ... x ... xs ...

proceeds as follows. We have to pattern match on the return value of a function call, so we replace the function call with its body (desugaring function argument pattern matching to case)

case (case doubleMe [1,2,3] of
          []   -> []
          x:xs -> (2*x) : doubleMe xs)
     ) of
    []     -> ...
    x : xs -> ... x ... xs ...

and we've introduced a second case, so that causes an evaluation

case (case (case [1,2,3] of
                 []   -> []
                 x:xs -> (2*x) : doubleMe xs
           ) of
          []   -> []
          x:xs -> (2*x) : doubleMe xs)
     ) of
    []     -> ...
    x : xs -> ... x ... xs ...

Now we have a third case. This one is directly matching on a datastructure so it returns immediately and chooses the appropriate branch to follow (which is the :) binding x to 1 and xs to [2,3].

case (case ((2*1) : doubleMe [2,3]
           ) of
          []   -> []
          x:xs -> (2*x) : doubleMe xs)
     ) of
    []     -> ...
    x : xs -> ... x ... xs ...

Now the scrutinee of the second case has been evaluated so it can proceed to choose the appropriate branch (again the :) binding x to (2*1) and xs to doubleMe [2,3].

case ((2*(2*1)) : doubleMe (doubleMe [2,3]))
     ) of
    []     -> ...
    x : xs -> ... x ... xs ...

and finally the original case can choose its branch

... (2*(2*1)) ... doubleMe (doubleMe [2,3])) ...

The next question is how evaluation of the (2*(2*1)) and doubleMe (doubleMe [2,3])) terms happens. The answer is that they can be forced only as a consequence of a higher level case that scrutinises the expression that they are part of.

---

[1] Or rather in implementations of Haskell. In principle Haskell could be implemented in a different way, but all the versions I know of do it like this.