Control.Monad.Operational

Implement monads by specifying primitive instructions and their operational semantics.

This package is based on the "The Operational Monad Tutorial", published in Issue 15 of The Monad.Reader http://themonadreader.wordpress.com/.

You are reading the API reference. For more thorough documentation including design and implementation notes as well as a correctness proof, please consult the included documentation in doc/Documentation.md, also available at http://heinrichapfelmus.github.com/operational/Documentation.html .

This API reference includes only basic example code. More intricate examples are available in the doc/examples directory, also available at https://github.com/HeinrichApfelmus/operational/tree/master/doc/examples#readme.

Basic usage

type Program instr = ProgramT instr Identity

The abstract data type 'Program instr a' represents programs.

• The type constructor instr :: * -> * indexes the primitive instructions.
• a is the return type of a program.

Program instr is always a monad and automatically obeys the monad laws.

singleton :: instr a -> ProgramT instr m a

Program made from a single primitive instruction.

type ProgramView instr = ProgramViewT instr Identity

View type for inspecting the first instruction. It has two constructors Return and :>>=. (For technical reasons, they are documented at ProgramViewT.)

view :: Program instr a -> ProgramView instr a

View function for inspecting the first instruction.

Example usage

Stack machine from "The Operational Monad Tutorial".

    data StackInstruction a where
        Push :: Int -> StackInstruction ()
        Pop  :: StackInstruction Int

    type StackProgram a = Program StackInstruction a

    interpret :: StackProgram a -> (Stack Int -> a)
    interpret = eval . view
        where
        eval :: ProgramView StackInstruction a -> (Stack Int -> a)
        eval (Push a :>>= is) stack     = interpret (is ()) (a:stack)
        eval (Pop    :>>= is) (a:stack) = interpret (is a ) stack
        eval (Return a)       stack     = a

Note that since ProgramView is a GADT, the type annotation for eval is mandatory.

Monad transformer

data ProgramT instr m a

The abstract data type ProgramT instr m a represents programs.

• The type constructor instr :: * -> * indexes the primitive instructions.
• m is the base monad, embedded with lift.
• a is the return type of a program.

ProgramT instr m is a monad transformer and automatically obeys both the monad and the lifting laws.

Instances

MonadState s m => MonadState s (ProgramT instr m)

MonadTrans (ProgramT instr)

Monad m => Monad (ProgramT instr m)

Monad m => Functor (ProgramT instr m)

Monad m => Applicative (ProgramT instr m)

MonadIO m => MonadIO (ProgramT instr m)

data ProgramViewT instr m a where

View type for inspecting the first instruction.

Constructors

Return :: a -> ProgramViewT instr m a

:>>= :: instr b -> (b -> ProgramT instr m a) -> ProgramViewT instr m a

viewT :: Monad m => ProgramT instr m a -> m (ProgramViewT instr m a)

View function for inspecting the first instruction.

liftProgram :: Monad m => Program instr a -> ProgramT instr m a

Lift a plain sequence of instructions to a sequence of instructions over a monad m. This is the counterpart of the lift function from MonadTrans.

It can be defined as follows:

    liftProgram = eval . view
        where
        eval :: ProgramView instr a -> ProgramT instr m a
        eval (Return a) = return a
        eval (i :>>= k) = singleton i >>= liftProgram . k

Example usage

List monad transformer.

    data PlusI m a where
        Zero :: PlusI m a
        Plus :: ListT m a -> ListT m a -> PlusI m a

   
    type ListT m a = ProgramT (PlusI m) m a

   
    runList :: Monad m => ListT m a -> m [a]
    runList = eval <=< viewT
        where
        eval :: Monad m => ProgramViewT (PlusI m) m a -> m [a]
        eval (Return x)        = return [x]
        eval (Zero     :>>= k) = return []
        eval (Plus m n :>>= k) =
            liftM2 (++) (runList (m >>= k)) (runList (n >>= k))

Note that since ProgramView is a GADT, the type annotation for eval is mandatory.