[Haskell-cafe] Re: Definition of "tail recursive" wrt Folds

[Bertram Felgenhauer]

Ben Franksen wrote:
> Mark Spezzano wrote:
> > Just looking at the definitions for foldr and foldl I see that foldl is
> > (apparently) tail recursive while foldr is not.
> > 
> > Why?
> > 
> > Is it because foldl defers calling itself until last whereas foldr
> > evaluates itself as it runs?
> > 
> > What, strictly speaking, is the definition of ”tail recursive” as opposed
> > to just “recursive”?
> 
> An application of some function f inside another function g is in 'tail
> position' (or a 'tail call') if the result of applying f is the result of
> g. Operationally speaking, calling f is the very last thing g does. Tail
> calls can be optimized by a compiler (or interpreter) so that the call does
> not use additional stack; that is, the call can be replaced by a jump.
> 
> A function is called ”tail recursive” (as opposed to just “recursive”) if
> the recursive call to itself is in tail position. If the compiler performs
> tail call optimization, tail recursive functions can work with constant
> stack space, similar to a (imperative) loop.
> 
> Looking at a definition of foldl, e.g.
> 
> foldl f z0 xs0 = lgo z0 xs0 where
>   lgo z []     =  z
>   lgo z (x:xs) = lgo (f z x) xs
> 
> you see that lgo calls itself in tail position, thus is tail recursive. In
> contrast, foldr can be defined as
> 
> foldr k z xs = go xs where
>   go []     = z
>   go (y:ys) = y `k` go ys
> 
> where you see that the result of go is not the recursive call to go.
> Instead, the result is  y `k` go ys . Thus, foldr is not tail recursive.
> 
> So, if you are saying that "foldl defers calling itself until last whereas
> foldr evaluates itself as it runs" then you got the right idea, I think.
> The point is that foldr still needs to do something (namely to apply  (y
> `k`)) to the result of applying itself. It needs to remember to do so, and
> thus the stack grows linearly with the size of the list.

Sorry, but that's wrong. It would be right in a strict language. In Haskell,
the 'go ys' term is not evaluated straight away; it is instead turned into
a suspended evaluation (a "thunk") that is typically stored on the heap.

The following discussion is implementation specific, with ghc in mind.
Haskell itself has no notion of a stack.

In fact both using foldl and using foldr can produce stack overflows:

  Prelude> foldl (+) 0 [1..10^7]
  *** Exception: stack overflow
  Prelude> foldr (+) 0 [1..10^7]
  *** Exception: stack overflow

Let's examine why. First, consider the foldl case. For simplicity, I'll
ignore the evaluation of [1..10^7]. The first few evaluation steps are

     foldl (+) 0 [1,2,3..1000000]
  -> lgo 0 [1,2,3..1000000]
  -> lgo (0+1) [2,3,4..1000000]
  -> lgo ((0+1)+2) [3,4,5..100000]

None of these steps uses the stack - foldl is indeed tail recursive. However,
the ((0+1)+2) is a thunk on the heap. Continuing,

  -> lgo ((...(0+1)+...)+9999999) [10000000]
  -> lgo ((...(0+1)+...)+10000000) []
  -> ((...(0+1)+...)+10000000)

Now we have to evaluate that huge thunk. This turns out to cause trouble
because + (for Integers) is strict. So in order to find x+10000000, the
code needs the value of x first. And that's where the stack gets
involved: the information of the pending addition, (?+10000000) is pushed
onto the stack, and evaluation proceeds with the first term.

Denoting the stack by [[item1, item2, ...]], evaluation continues like
this:

  -> [[(?+10000000)]] ((...(0+1)+...)+9999999)
  -> [[(?+10000000),(?+9999999)]]

The stack will keep growing, until the (0+1) is reached, or the stack
overflows.

To make things more confusing, ghc has a strictness analyzer that
sometimes manages to avoid such a thunk being built up. For an
example how strictness helps see foldl' (below).


Now for the foldr case. Evaluation in that case looks a bit different:

     foldr (+) 0 [1,2,3..10000000]
  -> go [1,2,3..10000000]
  -> 1 + go [2,3,4..10000000]

No stack was used so far; the go [2,3,4..1000000] is a thunk. Now, as
above, we need to add two numbers. And that's where the stack gets
involved again:

  -> [[(1+?)]] go [2,3,4..10000000]
  -> [[(1+?)]] 2 + go [3,4,5..10000000]
  -> [[(1+?),(2+?)]] go [3,4,5..10000000]
  -> [[(1+?),(2+?),(3+?)]] go [4,5,6..10000000]

and so on, until we reach  go []  or the stack overflows. Note that
there is no reference to 'go' on the stack at all.

If instead of (+), we had a lazy function like (:), the stack would
not get involved in this way:

     foldr (:) [] [1,2,3..10000000]
  -> go [1,2,3..10000000]
  -> 1 : go [2,3,4..10000000]

Which is in weak head normal form, so evaluation stops here. Later,
when other code examines the list, the 'go [2,3,4..10000000]' thunk
will get evaluated.


As a final note, the stack overflow with  foldl  above is cured by using
foldl', which is _strict_ in the accumulator.

For reference,
    foldl' f z0 xs0 = lgo z0 xs0
        where lgo z []     = z
              lgo z (x:xs) = let z' = f z x in z' `seq` lgo z' xs

     foldl' (+) 0 [1,2,3..1000000]
  -> lgo 0 [1,2,3..1000000]
  -> let z' = 0+1 in z' `seq` lgo z' [2,3,4..1000000]

Now the `seq` forces z' to be evaluated:

  -> let z' = 1 in lgo z' [2,3,4..10000000]
  -> lgo 1 [2,3,4..10000000]
  -> let z' = 1+2 in z' `seq` lgo z' [3,4,5..10000000]
  -> lgo 3 [3,4,5..10000000]
  -> lgo 6 [4,5,6..10000000]
  ...
  -> lgo 50000005000000 []
  -> 50000005000000

HTH,

Bertram