Hi, Some kind of graph rewriting on the term is a promising idea, but I have no idea how that would look. I would like to hear more. I have an example where sharing is a barrier to shortcut fusion. In Stream fusion combinators like map, filter and so on are implemented as converting from list to streams, a stream transformer, then back to a list: map f = unstream . map_s f . stream Then the rewrite rule removes superfluous conversion: {-# RULES stream . unstream = id #-} So if you have map.map, this gets fused away: map f . map g = (inline map) unstream . map_s f . stream . unstream . map_s g . stream = (rewrite rule) unstream . map_s f . map_s g . stream However, this doesn't work once you introduce sharing: let ys = map f xs in (map g ys, map h ys) = (inline map) let ys = unstream (map_s f (stream xs)) in (unstream (map g (stream ys)), unstream (map h (stream ys))) here, we cannot inline substitute "ys" into both use sites as it would duplicate work, so the rewrite rules have no way of firing. GHC has another pragma called "CONLIKE", which declares a particular function to be "cheap enough" to duplicate if duplication would cause a rule to fire. Data.Vector doesn't seem to use this in its stream fusion implementation, and I'm not sure why. It may solve this case, but I'm not sure it solves all cases On Tue, 22 Dec 2015 at 07:44 Johannes Waldmann < johannes.waldmann@htwk-leipzig.de> wrote:

...

The syntactic representation of the program is the most natural to humans, but it is perhaps not the best for simplification.

Maybe so. Please give examples.

We use graphs (instead of trees) to express sharing. Do you see sharing (or the lack of expressibility for it) as a problem with GHC rules currently?

- J.W.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe