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

[Duncan Coutts]

On Thu, 2006-08-31 at 11:29 +0100, Malcolm Wallace wrote:
> 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.

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