Data.Diagram

This module contains a Free monad with shared subterms. Unfortunately it is not a true monad in Hask category. If the classical Free monad generalises a tree, here we generalise directed acylic graphs. The Diagram is the true monadic context in which all operations are run.

For most operations to work the functor must be of class Eq1, Hashable1 and Traversable.

Diagrams

data Diagram f a s m r

The diagram records overlapping terms:

• f is the functor from which the Free terms are build.
• a is the type of leaves or terminals.
• s is a phantom type labelling the diagram and preventing leaking.

Instances

MonadTrans (Diagram f a s)

Defined in Data.Diagram

Methods

lift :: Monad m => m a0 -> Diagram f a s m a0

Monad m => Monad (Diagram f a s m)

Defined in Data.Diagram

Methods

(>>=) :: Diagram f a s m a0 -> (a0 -> Diagram f a s m b) -> Diagram f a s m b

(>>) :: Diagram f a s m a0 -> Diagram f a s m b -> Diagram f a s m b

return :: a0 -> Diagram f a s m a0

Functor m => Functor (Diagram f a s m)

Defined in Data.Diagram

Methods

fmap :: (a0 -> b) -> Diagram f a s m a0 -> Diagram f a s m b

(<$) :: a0 -> Diagram f a s m b -> Diagram f a s m a0

Monad m => Applicative (Diagram f a s m)

Defined in Data.Diagram

Methods

pure :: a0 -> Diagram f a s m a0

(<*>) :: Diagram f a s m (a0 -> b) -> Diagram f a s m a0 -> Diagram f a s m b

liftA2 :: (a0 -> b -> c) -> Diagram f a s m a0 -> Diagram f a s m b -> Diagram f a s m c

(*>) :: Diagram f a s m a0 -> Diagram f a s m b -> Diagram f a s m b

(<*) :: Diagram f a s m a0 -> Diagram f a s m b -> Diagram f a s m a0

runDiagram :: Monad m => (forall s. Diagram f a s m b) -> m b

Extract non-diagrammatic information

compress :: Monad m => Diagram f a s m b -> Diagram f a s Identity (m b)

Remove diagrmmatic information from the underlying monad. This could have problematic side-effects and should be used with caution

Nodes

data Free (f :: * -> *) a s

The Free monad parameterised by it's diagram. Approximately it corresponds to a non-terminal or sub-diagram

Constructors

Pure a

Instances

Eq a => Eq (Free f a s)

Defined in Data.Diagram

Methods

(==) :: Free f a s -> Free f a s -> Bool

(/=) :: Free f a s -> Free f a s -> Bool

Ord a => Ord (Free f a s)

Defined in Data.Diagram

Methods

compare :: Free f a s -> Free f a s -> Ordering

(<) :: Free f a s -> Free f a s -> Bool

(<=) :: Free f a s -> Free f a s -> Bool

(>) :: Free f a s -> Free f a s -> Bool

(>=) :: Free f a s -> Free f a s -> Bool

max :: Free f a s -> Free f a s -> Free f a s

min :: Free f a s -> Free f a s -> Free f a s

Generic (Free f a s)

Defined in Data.Diagram

Associated Types

type Rep (Free f a s) :: Type -> Type

Methods

from :: Free f a s -> Rep (Free f a s) x

to :: Rep (Free f a s) x -> Free f a s

Hashable a => Hashable (Free f a s)

Defined in Data.Diagram

Methods

hashWithSalt :: Int -> Free f a s -> Int

hash :: Free f a s -> Int

type Rep (Free f a s)

Defined in Data.Diagram

type Rep (Free f a s) = D1 ('MetaData "Free" "Data.Diagram" "zsdd-0.2.0.0-inplace" 'False) (C1 ('MetaCons "Pure" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a)) :+: C1 ('MetaCons "ID" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 Int)))

free :: (Monad m, Hashable1 f, Hashable a, Eq1 f, Eq a) => f (Free f a s) -> Diagram f a s m (Free f a s)

Analogous to the Free constructor, this fuction wraps another functorial layer. In a graph setting, this corresponds to creating a node from it's offspring structure

fromFree :: Monad m => Free f a s -> (f (Free f a s) -> Diagram f a s m b) -> (a -> Diagram f a s m b) -> Diagram f a s m b

Case analysis for Free, the first argument is the free continuation, and the second is the Pure case.

retract :: (Monad f, Traversable f) => Free f a s -> Diagram f a s f a

When f is monadic itself, retract will collapse the recursive structure

Combinators

map :: (Hashable1 f, Hashable a, Eq1 f, Eq a, Monad m, Traversable f) => (a -> Diagram f a s m a) -> Free f a s -> Diagram f a s m (Free f a s)

Apply a function to all terminals in a Free sub-diagram

bind :: (Hashable1 f, Hashable a, Eq1 f, Eq a, Monad m, Traversable f) => Free f a s -> (a -> Diagram f a s m (Free f a s)) -> Diagram f a s m (Free f a s)

Replace a terminal with a non-terminal in a Free sub-diagram

fold :: (Monad m, Traversable f) => (f b -> Diagram f a s m b) -> (a -> Diagram f a s m b) -> Free f a s -> Diagram f a s m b

Collapses a Free sub-diagram by instianting the terminals and offpsring structure