Re: [Haskell-cafe] library on common sub-expression elimination?

Do you mean that x and y in x = a + 1 y = a + 1 are different from data-reify point of view? 2011/8/12 Conal Elliott

Note that data-reify will only find *some* common/equal sub-expressions, namely the pointer-equal ones. In all of my code-generating ("deep") DSLs, it's been very important for efficiency to also pull out equal-but-pointer-unequal expressions.

- Conal

On Thu, Aug 11, 2011 at 4:41 AM, Vo Minh Thu wrote:

...

I guess you refer to data-reify: http://hackage.haskell.org/package/data-reify

2011/8/11 Stephen Tetley :

...

Strafunski and its successors (Uniplate, SYB, KURE) are really for working on trees. If you want to work on graphs you would probably be better of with something else.

I think I overlooked that you want common sub-expression _elimination_, rather than expression simplification. There are libraries for observable sharing (Andy Gill's recent one is the state-of-the-art, its on Hackage but I've forgotten its name) - that are pertinent where you have built the expressions as an embedded DSL in Haskell and you want sharing in code you generate from the Haskell DSL.

On 11 August 2011 08:57, Anton Kholomiov wrote:

...

Thank you for the reference to Strafunski libraries, I read HaskellWiki, but I don't have a permission to visit their site. All links are forbidden.

Can it be a function:

fun :: Eq a => Tree a -> [(Int, (a, [Int]))]

where tuple codes nodes, and Int's code edges.

2011/8/11 Stephen Tetley

...

Wouldn't this be dependent upon your AST and thus not readily "package-able" as a library?

Expression simplification has been a prime example for Strafunski style traversal libraries. You might be able to find examples that you can adapt to your own AST written with Uniplate or similar library.

On 11 August 2011 05:00, Anton Kholomiov wrote:

...

Is there a library on common sub-expression elimination?

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

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

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

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

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