Data.Fix.Cse

Implements common subexpression elimination (CSE) with hashconsig algorithm as described in the paper 'Implementing Explicit and Finding Implicit Sharing in EDSLs' by Oleg Kiselyov. You can define your datatype as a fixpoint type. Then the only thing you need to perform CSE is to define an instance of the class Traversable for your datatype.

Documentation

type VarName = Int

type Dag f = IntMap (f VarName)

Directed acyclic graphs.

fromDag :: Dag f -> [(VarName, f VarName)]

If plain lists are enough for your case.

Implicit sharing

cse :: (Eq (f Int), Ord (f Int), Traversable f) => Fix f -> Dag f

Performs common subexpression elimination with implicit sharing.

Explicit sharing

letCse :: (Eq (f Int), Ord (f Int), Traversable f) => Fix (Let f) -> Dag f

Performs common subexpression elimination with explicit sharing. To make sharing explicit you can use the datatype Let.

data Let f a

With explicit sharing you provide user with the special function that encodes let-bindings for your EDSL (LetBind). You should not use LetLift case. It's reserverd for the CSE algorithm.

Constructors

LetExp (f a)

LetBind a (a -> a)

LetLift VarName

letCata :: (Functor f, Traversable f) => (f a -> a) -> Fix (Let f) -> a

Catamorphism for fixpoint types wrapped in the type Let.

letCataM :: (Applicative m, Monad m, Traversable f) => (f a -> m a) -> Fix (Let f) -> m a

Monadic catamorphism for fixpoint types wrapped in the type Let.

letWrapper :: (Fix (Let f) -> a) -> (a -> Fix (Let f)) -> a -> (a -> a) -> a

Helper function to make explicit let-bindings. For exampe:

 newtype T = T { unT :: Fix (Let f) }
 
 let_ :: T -> (T -> T) -> T
 let_ = letWrapper T unT