[Haskell-cafe] Flattening tail recursion?

[Ben Rudiak-Gould]

Georg Martius wrote:

> It was allready posted before, that you need to enforce the evaluation 
> of the + in order to get the function run in constant space. The thing 
> is, that it is harder to achieve than I expected it to be.
>
> countLines' ls = foldl (\x y -> let x' = x + 1 in x' `seq` y `seq` x' 
> ) 0 ls
>
> will run in constant space, but just if compiled with -O (ghc-6.2.1). 
> The seq function forces the evaluation of its first argument (at least 
> to Head Normal Form). The second one is just passed through.


This isn't quite right. It's more accurate to say that seq ties together 
the evaluation of its arguments, so that the left argument is evaluated 
whenever (and just before) the right argument is. In particular, (x 
`seq` x) is the same as x. Your expression

    let x' = x + 1 in x' `seq` y `seq` x'

evaluates x' redundantly; it's (almost) semantically equivalent to

    let x' = x + 1 in y `seq` x'

which is equivalent to

    y `seq` (x + 1)

which, in this instance, might as well just be

    x + 1

since the strictness problem is unrelated to the list elements passed in 
y. In fact there's nothing you can do inside either argument to foldl to 
make the accumulation strict, because the arguments aren't used until 
the whole list has already been processed and the huge intermediate 
thunk has already been built. You need a separate "strict foldl" 
function, usually called foldl', which was unaccountably omitted from 
the prelude. If GHC does manage to compile a use of foldl into strict 
code, it's because of its internal strictness analyzer, not because of 
any explicit calls to seq.

Because I'm a cautious guy, I actually tried compiling both versions 
with ghc -O to check that I was right -- and I'm wrong! GHC does treat 
them differently. It even treats

    countLines' ls = foldl (\x y -> let x' = x + 1 in x' `seq` y `seq` 
x' ) 0 ls

differently from

    countLines' ls = foldl (\x y -> let x' = x + 1 in y `seq` x' ) 0 ls

The latter overflows the stack, the former doesn't. I have no idea 
what's going on here. Simon PJ? Simon M?

-- Ben