G'day all. On Wed, 1 Jan 2003, Andrew J Bromage wrote:
> > It has quite different performance characteristics, though. In > > particular, this uses O(n) stack space whereas the accumulator one > > uses O(1) stack space. On Wed, Jan 01, 2003 at 12:17:10PM +0200, Shlomi Fish wrote: > This is assuming Haskell is properly tail-recursive. However, as far as I > was told due to the lazy evaluation that is not the case for such > functions. There are two issues here: 1. Haskell 98 does not explicitly mandate tail recursion optimisation. (In particular, Hugs doesn't support it fully, as we have seen recently.) 2. Due to lazy evaluation, your accumulator may end up as a "thunk" and thus require stack/heap space to evaluate when you eventually get to the end. There's not a lot you can do about the first issue. The next version of Haskell should make tail recursion optimisation a language requirement, IMO. As to the second point, there are several possible solutions. Strictness analysis can help, but relying on this is a bad idea. Consider this code: rec1 [] acc = acc rec1 (x:xs) acc = rec1 xs (x `op` acc) If `op` is known to be strict in both its arguments, any decent strictness analyser will be able to strictly evaluate the accumulator here. On the other hand, modifying it slightly: rec2 [] acc = acc rec2 (x:xs) acc | sanityCheck x = rec2 xs (x `op` acc) | otherwise = error "sanity check failed" Now the strictness analyser will not be able to evaluate the accumulator eagerly, because in general it would be incorrect to do so. Another option is to use seq, ($!), foldl' or some other method to guarantee evaluation order. Cheers, Andrew Bromage _______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell