[Haskell-cafe] ANN: data-fix-cse -- Common subexpression elimination for EDSLs

[Emil Axelsson]

This should be possible using higher-order terms, as in

http://hackage.haskell.org/packages/archive/compdata/latest/doc/html/Data-Comp-Multi-Term.html

The only complication I see is that the Dag nodes would get 
heterogeneous types requiring existential quantification with a 
`Typeable` constraint. A better representation might be typed ASGs [1]

Syntactic has typed ASTs and it has a module that does something similar 
to data-fix-cse (uses a combination of stable names and hashing), but it 
needs some fixing up.

/ Emil

[1]: http://dl.acm.org/citation.cfm?id=2426909


2013-02-20 01:58, Conal Elliott skrev:
> Do you think the approach can be extended for non-regular (nested)
> algebraic types (where the recursive data type is sometimes at a
> different type instance)? For instance, it's very handy to use GADTs to
> capture embedded language types in host language (Haskell) types, which
> leads to non-regularity.