Duncan Coutts <[EMAIL PROTECTED]> 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
_______________________________________________
Glasgow-haskell-users mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
