Safe Haskell	Safe-Inferred

Data.Fix.Cse

Contents

Implicit sharing
Explicit sharing

Description

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.

Synopsis

Documentation

type VarName = Int Source

type Dag f = IntMap (f VarName)Source

Directed acyclic graphs.

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

If plain lists are enough for your case.

Implicit sharing

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

Performs common subexpression elimination with implicit sharing.

Explicit sharing

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

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

data Let f a Source

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) -> aSource

Catamorphism for fixpoint types wrapped in the type Let.

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

Monadic catamorphism for fixpoint types wrapped in the type Let.

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

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