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
_______________________________________________ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
