-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Common subexpression elimination for the fixploint types.
--   
@package data-fix-cse
@version 0.0.2


-- | 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 <a>Traversable</a> for your
--   datatype.
module Data.Fix.Cse
type VarName = Int

-- | Directed acyclic graphs.
type Dag f = IntMap (f VarName)

-- | If plain lists are enough for your case.
fromDag :: Dag f -> [(VarName, f VarName)]

-- | Performs common subexpression elimination with implicit sharing.
cse :: (Eq (f Int), Ord (f Int), Traversable f) => Fix f -> Dag f

-- | Performs common subexpression elimination with explicit sharing. To
--   make sharing explicit you can use the datatype <a>Let</a>.
letCse :: (Eq (f Int), Ord (f Int), Traversable f) => Fix (Let f) -> Dag f

-- | With explicit sharing you provide user with the special function that
--   encodes let-bindings for your EDSL (<a>LetBind</a>). You should not
--   use <a>LetLift</a> case. It's reserverd for the CSE algorithm.
data Let f a
LetExp :: (f a) -> Let f a
LetBind :: a -> (a -> a) -> Let f a
LetLift :: VarName -> Let f a

-- | Catamorphism for fixpoint types wrapped in the type <a>Let</a>.
letCata :: (Functor f, Traversable f) => (f a -> a) -> Fix (Let f) -> a

-- | Monadic catamorphism for fixpoint types wrapped in the type
--   <a>Let</a>.
letCataM :: (Applicative m, Monad m, Traversable f) => (f a -> m a) -> Fix (Let f) -> m a

-- | Helper function to make explicit let-bindings. For exampe:
--   
--   <pre>
--   newtype T = T { unT :: Fix (Let f) }
--   
--   let_ :: T -&gt; (T -&gt; T) -&gt; T
--   let_ = letWrapper T unT
--   </pre>
letWrapper :: (Fix (Let f) -> a) -> (a -> Fix (Let f)) -> a -> (a -> a) -> a

-- | Marker type for creation frames of variables. Start new frame when
--   if-block starts, create next frame when you go into the next branch of
--   the same block (with else ir elif), stop frame when leaving the
--   if-then-else block. Use no frame for all other expressions.
data FrameInfo
NoFrame :: FrameInfo
StartFrame :: FrameInfo
StopFrame :: FrameInfo
NextFrame :: FrameInfo

-- | Performs common subexpression elimination with implicit sharing using
--   information of frames. It doesn't share the variables in different
--   branches of imperative if-then-else block.
cseFramed :: (Eq (f Int), Ord (f Int), Traversable f) => (f Int -> FrameInfo) -> Fix f -> Dag f
instance Show FrameInfo
instance Eq FrameInfo
instance Ord FrameInfo