Question About lists

[Andrew J Bromage]

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