Re: Re[2]: [GHC] #876: stack overflow on 'length . filter odd $ [0 .. 999999999]'

On Thu, 2006-08-31 at 11:29 +0100, Malcolm Wallace wrote:

Bulat Ziganshin wrote:

...

...

It makes sense to me that the above behaviour is seen: length is now a good consumer, but it generates 1+(1+(1+(1+... as it is consuming, and this causes a stack overflow. I don't think we can fix this while staying with fold/build fusion, so it looks to me like the patch should be reverted and the whole problem looked at post-6.6.

in general, for any function we can either implement 1) good consumer based on using foldr 2) tail-recursion

are you agree?

I'd like to point out that, if you are prepared to abandon foldr/build fusion in favour of hylo fusion, you can code good consumers using either foldr or foldl. (Length is a foldl, because it uses an accumulator.) Foldl is tail-recursive, but this does not prevent it being a good consumer, provided your framework of fusion laws is sufficiently flexible.

We have a reformulation of hylo fusion which we use for the Data.ByteString library. That would cover lists too (and would make it easy to fuse conversions String<->ByteString). I forget, does hylo fusion cover (++) efficiently? For our system it works but is slower than we'd like. Duncan