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

[Malcolm Wallace]

Bulat Ziganshin <bulat.ziganshin at gmail.com> 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.

Regards,
    Malcolm