Duncan Coutts
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