Control.Monad.Watson

Watson works in a near-identical way to Holmes, but with one distinction: its base type is ST rather than IO, so the API calculates the results with "observably pure" functions. There are downsides: for example, Watson can't perform random restart with operations like shuffle. However, this is often an acceptable compromise to avoid IO entirely!

Documentation

data Watson (h :: Type) (x :: Type)

A monad capable of solving constraint problems using ST as the evaluation type. Cells are represented using STRef references, and provenance is tracked to optimise backtracking search across multiple branches.

Instances

Monad (Watson h)

Defined in Control.Monad.Watson

Methods

(>>=) :: Watson h a -> (a -> Watson h b) -> Watson h b

(>>) :: Watson h a -> Watson h b -> Watson h b

return :: a -> Watson h a

fail :: String -> Watson h a

Functor (Watson h)

Defined in Control.Monad.Watson

Methods

fmap :: (a -> b) -> Watson h a -> Watson h b

(<$) :: a -> Watson h b -> Watson h a

Applicative (Watson h)

Defined in Control.Monad.Watson

Methods

pure :: a -> Watson h a

(<*>) :: Watson h (a -> b) -> Watson h a -> Watson h b

liftA2 :: (a -> b -> c) -> Watson h a -> Watson h b -> Watson h c

(*>) :: Watson h a -> Watson h b -> Watson h b

(<*) :: Watson h a -> Watson h b -> Watson h a

MonadCell (Watson h)

Defined in Control.Monad.Watson

Associated Types

data Cell (Watson h) a :: Type

Methods

discard :: Watson h x

fill :: x -> Watson h (Cell (Watson h) x)

watch :: Cell (Watson h) x -> (x -> Watson h ()) -> Watson h ()

with :: Cell (Watson h) x -> (x -> Watson h ()) -> Watson h ()

write :: Merge x => Cell (Watson h) x -> x -> Watson h ()

newtype Cell (Watson h) x

Defined in Control.Monad.Watson

newtype Cell (Watson h) x = Cell {

• unwrap :: Cell (MoriarT (ST h)) x

}

class Monad m => MonadCell (m :: Type -> Type) where

The DSL for network construction primitives. The following interface provides the building blocks upon which the rest of the library is constructed.

If you are looking to implement the class yourself, you should note the lack of functionality for ambiguity/searching. This is deliberate: for backtracking search (as opposed to truth maintenance-based approaches), the ability to create computation branches dynamically makes it much harder to establish a reliable mechanism for tracking the effects of these choices.

For example: the approach used in the MoriarT implementation is to separate the introduction of ambiguity into one definite, explicit step, and all parameters must be declared ahead of time so that they can be assigned indices. Other implementations should feel free to take other approaches, but these will be implementation-specific.

Associated Types

data Cell m :: Type -> Type

The type of cells for this particular implementation. Typically, it's some sort of mutable reference (STRef, IORef, or similar), but the implementation may attach further metadata to the individual cells.

Methods

discard :: m x

Mark the current computation as failed. For more advanced implementations that utilise backtracking and branching, this is an indication that we should begin a different branch of the search. Otherwise, the computation should simply fail without a result.

fill :: x -> m (Cell m x)

Create a new cell with the given value. Although this value's type has no constraints, it will be immutable unless it also implements Merge, which exists to enforce monotonic updates.

watch :: Cell m x -> (x -> m ()) -> m ()

Create a callback that is fired whenever the value in a given cell is updated. Typically, this callback will involve potential writes to other cells based on the current value of the given cell. If such a write occurs, we say that we have propagated information from the first cell to the next.

with :: Cell m x -> (x -> m ()) -> m ()

Execute a callback with the current value of a cell. Unlike watch, this will only fire once, and subsequent changes to the cell should not re-trigger this callback. This callback should therefore not be "registered" on any cell.

write :: Merge x => Cell m x -> x -> m ()

Write an update to a cell. This update should be merged into the current value using the '(Data.JoinSemilattice.Merge.<<-)' operation, which should behave the same way as '(<>)' for commutative and idempotent monoids. This therefore preserves the monotonic behaviour: updates can only refine a value. The result of a write must be more refined than the value before, with no exception.

Instances

MonadCell Holmes

Defined in Control.Monad.Holmes

Associated Types

data Cell Holmes a :: Type

Methods

discard :: Holmes x

fill :: x -> Holmes (Cell Holmes x)

watch :: Cell Holmes x -> (x -> Holmes ()) -> Holmes ()

with :: Cell Holmes x -> (x -> Holmes ()) -> Holmes ()

write :: Merge x => Cell Holmes x -> x -> Holmes ()

MonadCell (Watson h)

Defined in Control.Monad.Watson

Associated Types

data Cell (Watson h) a :: Type

Methods

discard :: Watson h x

fill :: x -> Watson h (Cell (Watson h) x)

watch :: Cell (Watson h) x -> (x -> Watson h ()) -> Watson h ()

with :: Cell (Watson h) x -> (x -> Watson h ()) -> Watson h ()

write :: Merge x => Cell (Watson h) x -> x -> Watson h ()

unsafeRead :: Cell (Watson h) x -> Watson h x

Unsafely read from a cell. This operation is unsafe because it doesn't factor this cell into the provenance of any subsequent writes. If this value ends up causing a contradiction, we may end up removing branches of the search tree that are totally valid! This operation is safe as long as it is the very last thing you do in a computation, and its value is never used to influence any writes in any way.

backward :: (Typeable x, Merge x, Merge y) => (forall m. MonadCell m => Prop m x -> Prop m y) -> y -> Maybe x

Run a function between propagators "backwards", writing the given value as the output and then trying to push information backwards to the input cell.

forward :: (Typeable x, Merge x, Merge y) => (forall m. MonadCell m => Prop m x -> Prop m y) -> x -> Maybe y

Run a function between propagators with a raw value, writing the given value to the "input" cell and reading the result from the "output" cell.

runAll :: (forall h. Watson h x) -> [x]

Interpret a Watson program, returning a list of all successful branches' outputs. It's unlikely that you want to call this directly, though; typically, satisfying or whenever are more likely the things you want.

runOne :: (forall h. Watson h x) -> Maybe x

Interpret a Watson program, returning the first successful branch's result if any branch succeeds. It's unlikely that you want to call this directly, though; typically, satisfying or whenever are more likely the things you want.

satisfying :: (EqR x b, Typeable x) => (forall h. Config (Watson h) x) -> (forall m. MonadCell m => [Prop m x] -> Prop m b) -> Maybe [x]

Given an input configuration, and a predicate on those input variables, return the first configuration that satisfies the predicate.

whenever :: (EqR x b, Typeable x) => (forall h. Config (Watson h) x) -> (forall m. MonadCell m => [Prop m x] -> Prop m b) -> [[x]]

Given an input configuration, and a predicate on those input variables, return all configurations that satisfy the predicate. It should be noted that there's nothing lazy about this; if your problem has a lot of solutions, or your search space is very big, you'll be waiting a long time!