2013-02-19 12:10, Anton Kholomiov skrev:
I'm glad to announce the package for Commonsubexpression elimination [1].
It's an implementation of the hashconsig algorithm as described in the
paper
'Implementing Explicit and Finding Implicit Sharing in EDSLs' by Oleg
Kiselyov.
Main point of the library is to define this algorithm in the most
generic way.
You can define the AST for your DSL as fixpoint type[2]. And then all
you need
to use the library is to define the instance for type class `Traversable`.
One way to make the library even more useful would have been to base it
on compdata instead of data-fix. Compdata has support for composable
types and lots of extra functionality. On the other hand, it's easy
enough to translate from compdata terms to your `Fix`...
One side-note form my experience: Fixpoint types can be very flexible.
It's easy to compose them. If suddenly we need to add some extra data
to all cases from the example above we can easily do it with just another
Functor:
Imagine that we want to use a SampleRate value with all signals.
Then we can do it like this:
type E = Fix SampledExp
data SampledExp a = SampledExp SampleRate (Exp a)
then we should define an instance of the type class Traversable
for our new type SampleRate. The Exp doesn't change.
Very useful indeed! A more principled way to extend data types in this
way is Data Types à la Carte:
http://dx.doi.org/10.1017/S0956796808006758
(Implemented in compdata.)
/ Emil
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
