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

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

yes. On Fri, Aug 12, 2011 at 11:02 AM, Anton Kholomiov

wrote:

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

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

2011-08-13 05:40, Levent Erkok skrev:

On 8/12/2011 10:30 AM, Conal Elliott wrote:

...

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

data-reify-cse (http://hackage.haskell.org/package/data-reify-cse) by Sebastiaan Visser performs cse for graphs generated by Andy's data-reify.

-Levent.

I just wanted to point out that syntactic http://hackage.haskell.org/package/syntactic also has the functionality provided by data-reify and data-reify-cse. See Examples/NanoFeldspar/Test.hs for a demonstration. The reification part is more or less copied from data-reify, so it's conceptually doing the same thing. When it comes to graph reification, syntactic doesn't really offer anything more than what data-reify(-cse) does. But in the future, syntactic will also rebuild an expression with let binding from the graph. / Emil