Control.Monad.Operational

Contents

Description

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 docs/Documentation.html, also available at http://projects.haskell.org/operational/Documentation.html .

This API reference includes only basic example code. More intricate examples are available in the docs/examples directory, also available at http://projects.haskell.org/operational/examples.html.

Synopsis

Basic usage

type Program instr a = ProgramT instr Identity aSource

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 aSource

Program made from a single primitive instruction.

type ProgramView instr a = ProgramViewT instr Identity aSource

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 aSource

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 Source

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 whereSource

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

View function for inspecting the first instruction.

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

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.