# Contstuff

### From HaskellWiki

(Added a lot of stuff.) |
m (→Lifting: Adjusted to recent changes in the library.) |
||

(4 intermediate revisions by one user not shown) | |||

Line 1: | Line 1: | ||

− | |||

− | |||

The [http://hackage.haskell.org/package/contstuff contstuff library] implements a number of monad transformers and monads, which make heavy use of [[continuation passing style]] (CPS). This makes them both fast and flexible. Please note that this is neither a CPS tutorial nor a monad transformer tutorial. You should understand these concepts, before attempting to use ''contstuff''. | The [http://hackage.haskell.org/package/contstuff contstuff library] implements a number of monad transformers and monads, which make heavy use of [[continuation passing style]] (CPS). This makes them both fast and flexible. Please note that this is neither a CPS tutorial nor a monad transformer tutorial. You should understand these concepts, before attempting to use ''contstuff''. | ||

Line 6: | Line 4: | ||

=== ContT === | === ContT === | ||

− | The | + | The ''ContT'' monad transformer is the simplest of all CPS-based monads: |

+ | |||

+ | <haskell> | ||

+ | newtype ContT r m a | ||

+ | </haskell> | ||

+ | |||

+ | It essentially gives you access to the current continuation, which means that it lets you label certain points of execution and reuse these points later in interesting ways. With ''ContT'' you get an elegant encoding of computations, which support: | ||

* abortion (premature termination), | * abortion (premature termination), | ||

Line 14: | Line 18: | ||

* etc. | * etc. | ||

− | All these features are effects of | + | All these features are effects of ''ContT''. If you don't use them, then ''ContT'' behaves like the identity monad. A computation of type <hask>ContT r m a</hask> is a CPS computation with an intermediate result of type <hask>a</hask> and a final result of type <hask>r</hask>. The <hask>r</hask> type can be polymorphic most of the time. You only need to specify it, if you use some of the CPS effects like <hask>abort</hask>. |

− | To run a | + | To run a ''ContT'' computation you can use <hask>runContT</hask> or the convenience function <hask>evalContT</hask>: |

<haskell> | <haskell> | ||

Line 40: | Line 44: | ||

</haskell> | </haskell> | ||

− | This example demonstrates the most basic feature of | + | This example demonstrates the most basic feature of ''ContT''. First of all, ''ContT'' is a monad transformer, so you can for example lift ''IO'' actions to a CPS computation. The <hask>io</hask> function is a handy tool, which corresponds to <hask>liftIO</hask> from other transformer libraries and to <hask>inBase</hask> from [[monadLib]], but is restricted to the ''IO'' monad. You can also use the more generic <hask>base</hask> function, which promotes a base monad computation to ''ContT''. |

− | Each | + | Each ''ContT'' subcomputation receives a continuation, which is a function, to which the subcomputation is supposed to pass the result. However, the subcomputation may choose not to call the continuation at all, in which case the entire computation finishes with a final result. The <hask>abort</hask> function does that. |

=== Resumption and branches === | === Resumption and branches === | ||

Line 50: | Line 54: | ||

<haskell> | <haskell> | ||

labelCC :: a -> ContT r m (a, Label (ContT r m) a) | labelCC :: a -> ContT r m (a, Label (ContT r m) a) | ||

− | goto :: Label (ContT r m) a -> a -> ContT r m | + | goto :: Label (ContT r m) a -> a -> ContT r m () |

</haskell> | </haskell> | ||

Line 66: | Line 70: | ||

The <hask>labelCC</hask> function establishes a label to jump to by capturing its own continuation. It returns both its argument and a label. The <hask>goto</hask> function takes a label and a new argument. The effect is jumping to the corresponding label, but returning the new argument. So when <hask>labelCC</hask> is reached the <hask>i</hask> variable becomes 0. Later <hask>goto</hask> jumps back to the same point, but gives <hask>i</hask> a new value 1, as if <hask>labelCC</hask> were originally called with 1 as the argument. | The <hask>labelCC</hask> function establishes a label to jump to by capturing its own continuation. It returns both its argument and a label. The <hask>goto</hask> function takes a label and a new argument. The effect is jumping to the corresponding label, but returning the new argument. So when <hask>labelCC</hask> is reached the <hask>i</hask> variable becomes 0. Later <hask>goto</hask> jumps back to the same point, but gives <hask>i</hask> a new value 1, as if <hask>labelCC</hask> were originally called with 1 as the argument. | ||

− | Labels are first class values in contstuff. This means you can carry them around. They are only limited in that they can't be carried outside of a | + | Labels are first class values in ''contstuff''. This means you can carry them around. They are only limited in that they can't be carried outside of a ''ContT'' computation. |

=== Lifting === | === Lifting === | ||

Line 74: | Line 78: | ||

<haskell> | <haskell> | ||

lift :: (Transformer t, Monad m) => m a -> t m a | lift :: (Transformer t, Monad m) => m a -> t m a | ||

− | base :: | + | base :: LiftBase m => Base m a -> m a |

− | io :: (Base m | + | io :: (LiftBase m, Base m ~ IO) => Base m a -> m a |

</haskell> | </haskell> | ||

− | The <hask>lift</hask> function promotes a computation of the underlying monad. The <hask>base</hask> function promotes a computation of the base monad. It is a generalization of <hask>liftIO</hask> from other monad transformer libraries. Finally there is <hask>io</hask>, which is simply an alias for <hask>base</hask>, but restricted to | + | The <hask>lift</hask> function promotes a computation of the underlying monad. The <hask>base</hask> function promotes a computation of the base monad. It is a generalization of <hask>liftIO</hask> from other monad transformer libraries. Finally there is <hask>io</hask>, which is simply an alias for <hask>base</hask>, but restricted to ''IO''. |

=== Accumulating results === | === Accumulating results === | ||

− | + | ''ContT'' does not require the underlying functor to be a monad. Whenever the underlying functor is an <hask>Alternative</hask> functor, there is support for accumulating results using the <hask>(<|>)</hask> combinator. In other words, if <hask>m</hask> is an <hask>Alternative</hask>, then <hask>ContT r m</hask> is, too. Here is an example: | |

<haskell> | <haskell> | ||

Line 117: | Line 121: | ||

y <- listA [x+1, x-1] | y <- listA [x+1, x-1] | ||

return (x, y) | return (x, y) | ||

+ | </haskell> | ||

+ | |||

+ | == State == | ||

+ | |||

+ | The ''contstuff'' library also comes with a monad transformer for stateful computations. These computations carry state of a certain type and can access it at any time. It's called ''StateT'', just like in other transformer libraries, but this one has very different semantics and also takes an additional parameter: | ||

+ | |||

+ | <haskell> | ||

+ | newtype StateT r s m a | ||

+ | </haskell> | ||

+ | |||

+ | It is basically a generalization of ''ContT''. In fact you can use all the features of ''ContT'' in a ''StateT'' computation, too, including abortion, labels, accumulation, etc. | ||

+ | |||

+ | The <hask>r</hask> parameter is the type of the final result. In actual computations this parameter can be left polymorphic most of the time, unless you use abortion. | ||

+ | |||

+ | === Accessing the state === | ||

+ | |||

+ | There are many functions to access the implicit state. These don't belong to ''StateT'' directly, but instead to a type class called ''Stateful'', of which ''StateT'' is an instance. The associated type <hask>StateOf m</hask> is the type of the state of the monad <hask>m</hask>: | ||

+ | |||

+ | <haskell> | ||

+ | -- Where 'm' is a Stateful monad, 'StateOf m' is the type of its state. | ||

+ | get :: (Stateful m) => m (StateOf m) | ||

+ | put :: (Stateful m) => StateOf m -> m () | ||

+ | putLazy :: (Stateful m) => StateOf m -> m () | ||

+ | |||

+ | -- Convenience functions. | ||

+ | getField :: (Functor m, Stateful m) => (StateOf m -> a) -> m a | ||

+ | modify :: (Monad m, Stateful m) => (StateOf m -> StateOf m) -> m () | ||

+ | modifyLazy :: (Monad m, Stateful m) => (StateOf m -> StateOf m) -> m () | ||

+ | modifyField :: (Monad m, Stateful m) => | ||

+ | (StateOf m -> a) -> (a -> StateOf m) -> m () | ||

+ | modifyFieldLazy :: (Monad m, Stateful m) => | ||

+ | (StateOf m -> a) -> (a -> StateOf m) -> m () | ||

+ | </haskell> | ||

+ | |||

+ | As the names suggest ''StateT'' is strict by default. When setting a new state using <hask>put</hask>, the state is evaluated. If you want to avoid that use <hask>putLazy</hask> instead. | ||

+ | |||

+ | === Running === | ||

+ | |||

+ | To run a stateful computation you can use the <hask>runStateT</hask> function, which takes a final continuation, an initial state and a stateful computation as arguments. There are two convenience functions <hask>evalStateT</hask> | ||

+ | |||

+ | <haskell> | ||

+ | runStateT :: s -> (s -> a -> m r) -> StateT r s m a -> m r | ||

+ | evalStateT :: (Applicative m) => s -> StateT r s m r -> m r | ||

+ | execStateT :: (Applicative m) => s -> StateT s s m a -> m s | ||

+ | </haskell> | ||

+ | |||

+ | In most cases you will just use <hask>evalStateT</hask> or <hask>execStateT</hask>. | ||

+ | |||

+ | == Exceptions == | ||

+ | |||

+ | ''Contstuff'' provides an ''EitherT'' monad transformer: | ||

+ | |||

+ | <haskell> | ||

+ | newtype EitherT r e m a | ||

+ | </haskell> | ||

+ | |||

+ | This monad transformer is a generalization of ''ContT'' in that it supports two continuations. The second one can be accessed indirectly by the various exception handling functions. | ||

+ | |||

+ | === Raising and catching === | ||

+ | |||

+ | There are a number of functions to handle exceptions, which belong to a class <hask>HasExceptions</hask> with an associated type <hask>Exception m</hask>. ''EitherT'' is an instance of this class. | ||

+ | |||

+ | <haskell> | ||

+ | -- Where 'm' is a monad supporting exceptions, 'Exception m' is the | ||

+ | -- type of the exceptions. | ||

+ | raise :: (HasExceptions m) => Exception m -> m a | ||

+ | try :: (HasExceptions m) => m a -> m (Either (Exception m) a) | ||

+ | |||

+ | -- Convenience functions. | ||

+ | catch :: (HasExceptions m, Monad m) => m a -> (Exception m -> m a) -> m a | ||

+ | handle :: (HasExceptions m, Monad m) => (Exception m -> m a) -> m a -> m a | ||

+ | finally :: (HasExceptions m, Monad m) => m a -> m b -> m a | ||

+ | bracket :: (HasExceptions m, Monad m) => | ||

+ | m res -> (res -> m b) -> (res -> m a) -> m a | ||

+ | bracket_ :: (HasExceptions m, Monad m) => m a -> m b -> m c -> m c | ||

+ | </haskell> | ||

+ | |||

+ | Please note that <hask>bracket</hask> and <hask>bracket_</hask> have slightly different semantics than the corresponding functions from <hask>Control.Exception</hask>. If an exception is raised in both the middle computation and the final computation, then the middle one is significant. | ||

+ | |||

+ | === Running === | ||

+ | |||

+ | To run an ''EitherT'' computation you can use the <hask>runEitherT</hask> function, which expects the two final continuations and an ''EitherT'' computation. There is also a convenience function <hask>evalEitherT</hask>, which just returns an ''Either'' value: | ||

+ | |||

+ | <haskell> | ||

+ | runEitherT :: (a -> m r) -> (e -> m r) -> EitherT r e m a -> m r | ||

+ | evalEitherT :: (Applicative m) => | ||

+ | EitherT (Either e a) e m a -> m (Either e a) | ||

+ | </haskell> | ||

+ | |||

+ | == Choice/nondeterminism == | ||

+ | |||

+ | The ''ChoiceT'' monad transformer is basically a list monad transformer and a proper one at that. It is also very fast, because choice is implemented as a CPS-based left fold function: | ||

+ | |||

+ | <haskell> | ||

+ | newtype ChoiceT r i m a | ||

+ | </haskell> | ||

+ | |||

+ | The parameters <hask>r</hask> and <hask>i</hask> are the types of the final and the intermediate results respectively. In actual computations, unless you use abortion, these can be left polymorphic most of the time. Also practically they are almost always the same. Don't worry about them. | ||

+ | |||

+ | === Running === | ||

+ | |||

+ | You can run a ''ChoiceT'' computation by using the slightly scary <hask>runChoiceT</hask> function: | ||

+ | |||

+ | <haskell> | ||

+ | runChoiceT :: | ||

+ | (i -> a -> (i -> m r) -> m r) -> i -> (i -> m r) | ||

+ | -> ChoiceT r i m a -> m r | ||

+ | </haskell> | ||

+ | |||

+ | This function takes a folding function, a base element, a final continuation (the folding function uses CPS) and a ''ChoiceT'' computation. Of course in practice you mostly just want a list of results or the first result or something like that. Luckily there are two convenience functions to do just that: | ||

+ | |||

+ | <haskell> | ||

+ | findFirst :: (Alternative f, Applicative m) => | ||

+ | ChoiceT (f a) (f a) m a -> m (f a) | ||

+ | findAll :: (Alternative f, Applicative m) => | ||

+ | ChoiceT (f a) (f a) m a -> m (f a) | ||

+ | </haskell> | ||

+ | |||

+ | Even these look scary, but they really aren't. In most cases <hask>f</hask> is just <hask>[]</hask> or <hask>Maybe</hask>. But there are more convenience functions: | ||

+ | |||

+ | <haskell> | ||

+ | maybeChoiceT :: Applicative m => | ||

+ | ChoiceT (Maybe a) (Maybe a) m a -> m (Maybe a) | ||

+ | listChoiceT :: Applicative m => ChoiceT [a] [a] m a -> m [a] | ||

+ | </haskell> | ||

+ | |||

+ | The <hask>maybeChoiceT</hask> function is just a special case of <hask>findFirst</hask>. The <hask>listChoiceT</hask> in contrast does not behave like <hask>findAll</hask>. It returns the results in reversed order and is much faster than <hask>findAll</hask>. | ||

+ | |||

+ | === Convenience functions === | ||

+ | |||

+ | Often you just want to encode a list of choices. For this you can use the <hask>listA</hask> function discussed earlier: | ||

+ | |||

+ | <haskell> | ||

+ | listA :: (Alternative f) => [a] -> f a | ||

+ | </haskell> | ||

+ | |||

+ | There is an alternative function, which works only for ''ChoiceT'', but is much faster than <hask>listA</hask>, called just <hask>choice</hask>: | ||

+ | |||

+ | <haskell> | ||

+ | choice :: [a] -> ChoiceT r i m a | ||

</haskell> | </haskell> |

## Latest revision as of 02:50, 1 October 2010

The contstuff library implements a number of monad transformers and monads, which make heavy use of continuation passing style (CPS). This makes them both fast and flexible. Please note that this is neither a CPS tutorial nor a monad transformer tutorial. You should understand these concepts, before attempting to use *contstuff*.

## Contents |

## [edit] 1 Basics

### [edit] 1.1 ContT

The *ContT* monad transformer is the simplest of all CPS-based monads:

`newtype ContT r m a`

It essentially gives you access to the current continuation, which means that it lets you label certain points of execution and reuse these points later in interesting ways. With *ContT* you get an elegant encoding of computations, which support:

- abortion (premature termination),
- resumption (start a computation at a certain spot),
- branches (aka
*goto*), - result accumulation,
- etc.

*ContT*. If you don't use them, then

*ContT*behaves like the identity monad. A computation of type

*ContT*computation you can use

runContT :: (a -> m r) -> ContT r m a -> m r evalContT :: Applicative m => ContT r m r -> m r

### [edit] 1.2 Abortion

Let's have a look at a small example:

testComp1 :: ContT () IO () testComp1 = forever $ do txt <- io getLine case txt of "info" -> io $ putStrLn "This is a test computation." "quit" -> abort () _ -> return ()

*ContT*. First of all,

*ContT*is a monad transformer, so you can for example lift

*IO*actions to a CPS computation. The

*IO*monad. You can also use the more generic

*ContT*. Each

*ContT*subcomputation receives a continuation, which is a function, to which the subcomputation is supposed to pass the result. However, the subcomputation may choose not to call the continuation at all, in which case the entire computation finishes with a final result. The

### [edit] 1.3 Resumption and branches

You can capture the current continuation using the commonlabelCC :: a -> ContT r m (a, Label (ContT r m) a) goto :: Label (ContT r m) a -> a -> ContT r m ()

These slightly complicated looking functions are actually very simple to use:

testComp2 :: ContT r IO () testComp2 = do (i, again) <- labelCC 0 io (print i) when (i < 10) $ goto again (i+1) io (putStrLn $ "Final result: " ++ show i)

Labels are first class values in *contstuff*. This means you can carry them around. They are only limited in that they can't be carried outside of a *ContT* computation.

### [edit] 1.4 Lifting

As noted earlier there are three lifting functions, which you can use to access monads in lower layers of the transformer stack:

lift :: (Transformer t, Monad m) => m a -> t m a base :: LiftBase m => Base m a -> m a io :: (LiftBase m, Base m ~ IO) => Base m a -> m a

*IO*.

### [edit] 1.5 Accumulating results

*ContT*does not require the underlying functor to be a monad. Whenever the underlying functor is an

testComp3 :: Num a => ContT r [] (a, a) testComp3 = do x <- pure 10 <|> pure 20 y <- pure (x+1) <|> pure (x-1) return (x, y)

*contstuff*library implements a convenience function

listA :: (Alternative f) => [a] -> f a

testComp3' :: Num a => ContT r [] (a, a) testComp3' = do x <- listA [10, 20] y <- listA [x+1, x-1] return (x, y)

testComp4 :: Num a => ContT (a, a) [] (a, a) testComp4 = do x <- listA [10, 20] when (x == 10) (abort (10, 10)) y <- listA [x+1, x-1] return (x, y)

## [edit] 2 State

The *contstuff* library also comes with a monad transformer for stateful computations. These computations carry state of a certain type and can access it at any time. It's called *StateT*, just like in other transformer libraries, but this one has very different semantics and also takes an additional parameter:

`newtype StateT r s m a`

It is basically a generalization of *ContT*. In fact you can use all the features of *ContT* in a *StateT* computation, too, including abortion, labels, accumulation, etc.

### [edit] 2.1 Accessing the state

There are many functions to access the implicit state. These don't belong to*StateT*directly, but instead to a type class called

*Stateful*, of which

*StateT*is an instance. The associated type

-- Where 'm' is a Stateful monad, 'StateOf m' is the type of its state. get :: (Stateful m) => m (StateOf m) put :: (Stateful m) => StateOf m -> m () putLazy :: (Stateful m) => StateOf m -> m () -- Convenience functions. getField :: (Functor m, Stateful m) => (StateOf m -> a) -> m a modify :: (Monad m, Stateful m) => (StateOf m -> StateOf m) -> m () modifyLazy :: (Monad m, Stateful m) => (StateOf m -> StateOf m) -> m () modifyField :: (Monad m, Stateful m) => (StateOf m -> a) -> (a -> StateOf m) -> m () modifyFieldLazy :: (Monad m, Stateful m) => (StateOf m -> a) -> (a -> StateOf m) -> m ()

*StateT*is strict by default. When setting a new state using

### [edit] 2.2 Running

To run a stateful computation you can use therunStateT :: s -> (s -> a -> m r) -> StateT r s m a -> m r evalStateT :: (Applicative m) => s -> StateT r s m r -> m r execStateT :: (Applicative m) => s -> StateT s s m a -> m s

## [edit] 3 Exceptions

*Contstuff* provides an *EitherT* monad transformer:

`newtype EitherT r e m a`

This monad transformer is a generalization of *ContT* in that it supports two continuations. The second one can be accessed indirectly by the various exception handling functions.

### [edit] 3.1 Raising and catching

There are a number of functions to handle exceptions, which belong to a class*EitherT*is an instance of this class.

-- Where 'm' is a monad supporting exceptions, 'Exception m' is the -- type of the exceptions. raise :: (HasExceptions m) => Exception m -> m a try :: (HasExceptions m) => m a -> m (Either (Exception m) a) -- Convenience functions. catch :: (HasExceptions m, Monad m) => m a -> (Exception m -> m a) -> m a handle :: (HasExceptions m, Monad m) => (Exception m -> m a) -> m a -> m a finally :: (HasExceptions m, Monad m) => m a -> m b -> m a bracket :: (HasExceptions m, Monad m) => m res -> (res -> m b) -> (res -> m a) -> m a bracket_ :: (HasExceptions m, Monad m) => m a -> m b -> m c -> m c

### [edit] 3.2 Running

To run an*EitherT*computation you can use the

*EitherT*computation. There is also a convenience function

*Either*value:

runEitherT :: (a -> m r) -> (e -> m r) -> EitherT r e m a -> m r evalEitherT :: (Applicative m) => EitherT (Either e a) e m a -> m (Either e a)

## [edit] 4 Choice/nondeterminism

The *ChoiceT* monad transformer is basically a list monad transformer and a proper one at that. It is also very fast, because choice is implemented as a CPS-based left fold function:

`newtype ChoiceT r i m a`

### [edit] 4.1 Running

You can run a*ChoiceT*computation by using the slightly scary

runChoiceT :: (i -> a -> (i -> m r) -> m r) -> i -> (i -> m r) -> ChoiceT r i m a -> m r

This function takes a folding function, a base element, a final continuation (the folding function uses CPS) and a *ChoiceT* computation. Of course in practice you mostly just want a list of results or the first result or something like that. Luckily there are two convenience functions to do just that:

findFirst :: (Alternative f, Applicative m) => ChoiceT (f a) (f a) m a -> m (f a) findAll :: (Alternative f, Applicative m) => ChoiceT (f a) (f a) m a -> m (f a)

maybeChoiceT :: Applicative m => ChoiceT (Maybe a) (Maybe a) m a -> m (Maybe a) listChoiceT :: Applicative m => ChoiceT [a] [a] m a -> m [a]

### [edit] 4.2 Convenience functions

Often you just want to encode a list of choices. For this you can use thelistA :: (Alternative f) => [a] -> f a

*ChoiceT*, but is much faster than

choice :: [a] -> ChoiceT r i m a