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

[Malcolm Wallace]

Duncan Coutts <duncan.coutts at worc.ox.ac.uk> wrote:

> 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.

Well, there is a fairly straightforward RULE for (++) which essentially
discovers the listy-ness of both arguments simultaneously, and deforests
them together.

  xs ++ ys = foldr (:) ys xs
  RULES
    foldr f z (foldr (:) (foldr (:) [] s0) s1)
  = foldr f (foldr f z s0) s1

However this is not ideal, since it only deals well with a single (++),
not a chain of them.  But there is a separate set of RULES for
deforesting concat/concatMap, especially as used in list comprehensions.
It is relatively easy to convert a chain of (++)s to a single
application of concat.  I am still working on the details of the
formulation of concatMap as a hylo-like structure, so no performance
results yet.  I hope to get it all finished and written up within a few
weeks.

Regards,
    Malcolm