Control.Monad.Amb

Overview

A nondeterministic computation makes a series of choices which it can then backtrack to. As an example, here is a program which computes Pythagorean triples of a certain size.

import Control.Monad
import Control.Monad.Amb

pyTriple :: (Num t, Ord t) => t -> Amb r (t, t, t)
pyTriple n = do a <- anIntegerBetween 1 n
                b <- anIntegerBetween (a + 1) n
                c <- anIntegerBetween (b + 1) n
                when (a*a + b*b /= c*c) fail'
                return (a,b,c)

You can run this computation and ask for one or more of its possible values.

>>> oneValue $ pyTriple 20
(3,4,5)

>>> allValues $ pyTriple 20
[(3,4,5),(5,12,13),(6,8,10),(8,15,17),(9,12,15),(12,16,20)]

Creating computations

amb :: Monad m => [b] -> AmbT r m b

Just for fun. This is McCarthy's amb operator and is a synonym for aMemberOf.

aPartitionOfSize :: (Eq a, Monad m) => Int -> [a] -> AmbT r m [[a]]

Generate all partitions of a given size of this list.

aPartitionOf :: (Eq t, Monad m) => [t] -> AmbT r m [[t]]

Generate all partitions of this list.

aPermutationOf :: Monad m => [a] -> AmbT r m [a]

Generate all permutations of a list.

aSplitOf :: Monad m => [a] -> AmbT r m ([a], [a])

Generate all splits of a list.

anIntegerBetween :: (Monad m, Num b, Ord b) => b -> b -> AmbT r m b

Generate all numbers between the given bounds, inclusive.

aSubsetOf :: Monad m => [AmbT r m a] -> AmbT r m [a]

Generate each subset of any size from the given list.

aMemberOf :: Monad m => [b] -> AmbT r m b

Generate each element of the given list.

aBoolean :: Monad m => AmbT r m Bool

The most basic primitive that everything else is built out of. Generates True and False.

fail' :: Monad m => AmbT r m b

Terminate this branch of the computation.

either' :: Monad m => AmbT r m b -> AmbT r m b -> AmbT r m b

Nondeterministically choose either of the two computations

Running computations

isPossible :: Amb Bool Bool -> Bool

Run a nondeterministic computation and return True if any result is True, False otherwise.

isPossibleT :: Monad m => AmbT Bool m Bool -> m Bool

Run a nondeterministic computation and return True if any result is True, False otherwise.

isNecessary :: Amb Bool Bool -> Bool

Run a nondeterministic computation and return True if all possible results are True, False otherwise.

isNecessaryT :: Monad m => AmbT Bool m Bool -> m Bool

Run a nondeterministic computation and return True if all possible results are True, False otherwise.

allValues :: Amb t t -> [t]

Run a nondeterministic computation and return a list of all results that the computation can produce. Note that this function is not lazy its result.

allValuesT :: Monad m => AmbT t m t -> m [t]

Run a nondeterministic computation and return a list of all results that the computation can produce. Note that this function is not lazy its result.

oneValue :: Amb a a -> a

Run a nondeterministic computation and return a result of that computation.

oneValueT :: Monad m => AmbT b m b -> m b

Run a nondeterministic computation and return a result of that computation.

Low-level internals

tell' :: Monad m => [r] -> AmbT r m ()

A helper to inject state into the backtracking stack

tellState :: (Monoid s, MonadState s m) => s -> m ()

A helper to inject state into the backtracking stack

uponFailure :: Monad m => AmbT r m a -> AmbT r m ()

When the nondeterministic computation backtracks past this state, execute this nondeterministic computation. Generally used to undo side effects.

runAmbT :: Monad m => AmbT t m t -> m (t, [t])

Run the nondeterministic computation. This is internal.

runAmbTI :: Monad m => AmbT a m a -> AmbT a m a -> m (a, [a])

Run the nondeterministic computation. This is internal.

ambCC :: ((a -> AmbT r m a1) -> AmbT r m a) -> AmbT r m a

call/cc lifted into the nondeterministic monad. This implements the backtracking behaviour which allows Amb to try different code paths and return multiple results.

forEffects :: Monad m => ((t, [t]) -> r) -> (t1 -> AmbT t m t) -> AmbT t m t1 -> m r

A low-level internal function which executes a nondeterministic computation for its nondeterministic side-effects, such as its ability to produce different results.

Types

data AmbT r m a

AmbT r m a is a computation whose current value is of type a and which will ultimately return a value of type r. The same as ContT.

Constructors

AmbT

Fields

unAmbT :: StateT (AmbT r m r) (ContT r (StateT [r] m)) a

From left to right:

• the computation to run on failure
• the continuation captured when making nondeterministic choices
• record keeping of solutions found so far

Instances

MonadTrans (AmbT r)

Monad m => Monad (AmbT r m)

type AmbT' m a = forall r. AmbT r m a

type Amb r = AmbT r Identity

type Amb' a = AmbT' Identity a