[Haskell-cafe] Flattening tail recursion?
Benjamin.Rudiak-Gould at cl.cam.ac.uk
Fri Dec 10 16:36:34 EST 2004
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
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?
More information about the Haskell-Cafe