Data.Holmes

This module includes almost everything you'd need to build a constraint-solving computation. The module uses the Holmes solver, but you may want to use the functions in the Control.Monad.Watson module to avoid executing your code in IO.

Documentation

data Holmes (x :: Type)

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

Instances

Monad Holmes

Defined in Control.Monad.Holmes

Methods

(>>=) :: Holmes a -> (a -> Holmes b) -> Holmes b

(>>) :: Holmes a -> Holmes b -> Holmes b

return :: a -> Holmes a

Functor Holmes

Defined in Control.Monad.Holmes

Methods

fmap :: (a -> b) -> Holmes a -> Holmes b

(<$) :: a -> Holmes b -> Holmes a

MonadFail Holmes

Defined in Control.Monad.Holmes

Methods

fail :: String -> Holmes a

Applicative Holmes

Defined in Control.Monad.Holmes

Methods

pure :: a -> Holmes a

(<*>) :: Holmes (a -> b) -> Holmes a -> Holmes b

liftA2 :: (a -> b -> c) -> Holmes a -> Holmes b -> Holmes c

(*>) :: Holmes a -> Holmes b -> Holmes b

(<*) :: Holmes a -> Holmes b -> Holmes a

MonadCell Holmes

Defined in Control.Monad.Holmes

Associated Types

data Cell Holmes :: Type -> 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 ()

newtype Cell Holmes x

Defined in Control.Monad.Holmes

newtype Cell Holmes x = Cell {

• unwrap :: Cell (MoriarT IO) x

}

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

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.

Minimal complete definition

discard, fill, watch, with, write

Instances

MonadCell Holmes

Defined in Control.Monad.Holmes

Associated Types

data Cell Holmes :: Type -> 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 ()

PrimMonad m => MonadCell (MoriarT m)

Defined in Control.Monad.MoriarT

Associated Types

data Cell (MoriarT m) :: Type -> Type

Methods

discard :: MoriarT m x

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

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

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

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

MonadCell (Watson h)

Defined in Control.Monad.Watson

Associated Types

data Cell (Watson h) :: Type -> 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 ()

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.

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.

satisfying :: (EqC f x, EqR f, Typeable x) => Config Holmes (f x) -> (forall m. MonadCell m => [Prop m (f x)] -> Prop m (f Bool)) -> IO (Maybe [f x])

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

shuffle :: Config Holmes x -> Config Holmes x

Shuffle the refinements in a configuration. If we make a configuration like 100 from [1 .. 10], the first configuration will be one hundred 1 values. Sometimes, we might find we get to a first solution faster by randomising the order in which refinements are given. This is similar to the "random restart" strategy in hill-climbing problems.

Another nice use for this function is procedural generation: often, your results will look more "natural" if you introduce an element of randomness.

whenever :: (EqC f x, EqR f, Typeable x) => Config Holmes (f x) -> (forall m. MonadCell m => [Prop m (f x)] -> Prop m (f Bool)) -> IO [[f 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!

data Config (m :: Type -> Type) (x :: Type)

An input configuration.

This stores both an initial configuration of input parameters, as well as a function that can look for ways to refine an input. In other words, if the initial value is an Data.JoinSemilattice.Intersect of [1 .. 5], the refinements might be singleton values of every remaining possibility.

Constructors

Config

Fields

• initial :: [x]
• refine :: x -> m [x]

class Input (x :: Type) where

The simplest way of generating an input configuration is to say that a problem has m variables that will all be one of n possible values. For example, a sudoku board is 81 variables of 9 possible values. This class allows us to generate these simple input configurations like a game of countdown: "81 from 1 .. 9, please, Carol!"

Associated Types

type Raw x :: Type

Different parameter types will have different representations for their values. The Raw type means that I can say 81 from [1 .. 9], and have the parameter type determine how it will represent 1, for example. It's a little bit of syntactic sugar for the benefit of the user, so they don't need to know as much about how the parameter types work to use the library.

Methods

from :: Applicative m => Int -> [Raw x] -> Config m x

Generate m variables who are one of n values. 81 from [1 .. 9], 5 from [ True, False ], and so on.

Instances

Input (Defined content)

Defined in Data.JoinSemilattice.Defined

Associated Types

type Raw (Defined content)

Methods

from :: forall (m :: Type -> Type). Applicative m => Int -> [Raw (Defined content)] -> Config m (Defined content)

Intersectable x => Input (Intersect x)

Defined in Data.JoinSemilattice.Intersect

Associated Types

type Raw (Intersect x)

Methods

from :: forall (m :: Type -> Type). Applicative m => Int -> [Raw (Intersect x)] -> Config m (Intersect x)

permute :: (Applicative m, Eq x, Hashable x) => Config m x -> m (HashSet [x])

For debugging purposes, produce a HashSet of all possible refinements that a Config might produce for a given problem. This set could potentially be very large!

class Merge x => AbsR (x :: Type) where

Unlike the abs we know, which is a function from a value to its absolute value, absR is a relationship between a value and its absolute.

For some types, while we can't truly reverse the abs function, we can say that there are two possible inputs to consider, and so we can push some information in the reverse direction.

Minimal complete definition

Nothing

Methods

absR :: (x, x) -> (x, x)

Given a value and its absolute, try to learn something in either direction.

default absR :: Num x => (x, x) -> (x, x)

Instances

(Eq x, Num x) => AbsR (Defined x)

Defined in Data.JoinSemilattice.Class.Abs

Methods

absR :: (Defined x, Defined x) -> (Defined x, Defined x)

(Bounded x, Enum x, Ord x, Hashable x, Num x) => AbsR (Intersect x)

Defined in Data.JoinSemilattice.Class.Abs

Methods

absR :: (Intersect x, Intersect x) -> (Intersect x, Intersect x)

class Merge (f Bool) => BooleanR (f :: Type -> Type) where

Rather than the not, and, and or functions we know and love, the BooleanR class presents relationships that are analogous to these. The main difference is that relationships are not one-way. For example, if I tell you that the output of x && y is True, you can tell me what the inputs are, even if your computer can't. The implementations of BooleanR should be such that all directions of inference are considered.

Methods

falseR :: f Bool

An overloaded False value.

trueR :: f Bool

An overloaded True value.

notR :: (f Bool, f Bool) -> (f Bool, f Bool)

A relationship between a boolean value and its opposite.

andR :: (f Bool, f Bool, f Bool) -> (f Bool, f Bool, f Bool)

A relationship between two boolean values and their conjunction.

orR :: (f Bool, f Bool, f Bool) -> (f Bool, f Bool, f Bool)

A relationship between two boolean values and their disjunction.

Instances

BooleanR Defined

Defined in Data.JoinSemilattice.Class.Boolean

Methods

falseR :: Defined Bool

trueR :: Defined Bool

notR :: (Defined Bool, Defined Bool) -> (Defined Bool, Defined Bool)

andR :: (Defined Bool, Defined Bool, Defined Bool) -> (Defined Bool, Defined Bool, Defined Bool)

orR :: (Defined Bool, Defined Bool, Defined Bool) -> (Defined Bool, Defined Bool, Defined Bool)

BooleanR Intersect

Defined in Data.JoinSemilattice.Class.Boolean

Methods

falseR :: Intersect Bool

trueR :: Intersect Bool

notR :: (Intersect Bool, Intersect Bool) -> (Intersect Bool, Intersect Bool)

andR :: (Intersect Bool, Intersect Bool, Intersect Bool) -> (Intersect Bool, Intersect Bool, Intersect Bool)

orR :: (Intersect Bool, Intersect Bool, Intersect Bool) -> (Intersect Bool, Intersect Bool, Intersect Bool)

class (forall x. EqC' f x => Merge (f x), BooleanR f) => EqR (f :: Type -> Type) where

Equality between two variables as a relationship between them and their result. The hope here is that, if we learn the output before the inputs, we can often "work backwards" to learn something about them. If we know the result is exactly true, for example, we can effectively then unify the two input cells, as we know that their values will always be the same.

The class constraints are a bit ugly here, and it's something I'm hoping I can tidy up down the line. The idea is that, previously, our class was defined as:

  class EqR (x :: Type) (b :: Type) | x -> b where
    eqR :: (x -> x -> b) -> (x -> x -> b)

The problem here was that, if we said x .== x :: Prop m (Defined Bool), we couldn't even infer that the type of x was Defined-wrapped, which made the overloaded literals, for example, largely pointless.

To fix it, the class was rewritten to parameterise the wrapper type, which means we can always make this inference. However, the constraints got a bit grizzly when I hacked it together.

Associated Types

type EqC f :: Type -> Constraint

Methods

eqR :: EqC' f x => (f x, f x, f Bool) -> (f x, f x, f Bool)

Instances

EqR Defined

Defined in Data.JoinSemilattice.Class.Eq

Associated Types

type EqC Defined :: Type -> Constraint

Methods

eqR :: EqC' Defined x => (Defined x, Defined x, Defined Bool) -> (Defined x, Defined x, Defined Bool)

EqR Intersect

Defined in Data.JoinSemilattice.Class.Eq

Associated Types

type EqC Intersect :: Type -> Constraint

Methods

eqR :: EqC' Intersect x => (Intersect x, Intersect x, Intersect Bool) -> (Intersect x, Intersect x, Intersect Bool)

neR :: (EqR f, EqC' f x) => (f x, f x, f Bool) -> (f x, f x, f Bool)

A relationship between two variables and the result of a not-equals comparison between them.

class Zipping f c => FlatMapping (f :: Type -> Type) (c :: Type -> Constraint) | f -> c where

Some types, such as Intersect, contain multiple "candidate values". This function allows us to take each candidate, apply a function, and then union all the results. Perhaps fanOut would have been a better name for this function, but we use (>>=) to lend an intuition when we lift this into Prop via (.>>=).

There's not normally much reverse-flow information here, sadly, as it typically requires us to have a way to generate an "empty candidate" a la mempty. It's quite hard to articulate this in a succinct way, but try implementing the reverse flow for Defined or Intersect, and see what happens.

Methods

flatMapR :: (c x, c y) => (Maybe (x -> f y), Maybe (f y -> x)) -> (f x, f y) -> (f x, f y)

Instances

FlatMapping Defined Eq

Defined in Data.JoinSemilattice.Class.FlatMapping

Methods

flatMapR :: (Eq x, Eq y) => (Maybe (x -> Defined y), Maybe (Defined y -> x)) -> (Defined x, Defined y) -> (Defined x, Defined y)

FlatMapping Intersect Intersectable

Defined in Data.JoinSemilattice.Class.FlatMapping

Methods

flatMapR :: (Intersectable x, Intersectable y) => (Maybe (x -> Intersect y), Maybe (Intersect y -> x)) -> (Intersect x, Intersect y) -> (Intersect x, Intersect y)

class SumR x => FractionalR (x :: Type) where

Reversible (fractional or floating-point) multiplication as a three-value relationship between two values and their product.

Minimal complete definition

Nothing

Methods

multiplyR :: (x, x, x) -> (x, x, x)

default multiplyR :: Fractional x => (x, x, x) -> (x, x, x)

Instances

(Eq x, Fractional x) => FractionalR (Defined x)

Defined in Data.JoinSemilattice.Class.Fractional

Methods

multiplyR :: (Defined x, Defined x, Defined x) -> (Defined x, Defined x, Defined x)

(Bounded x, Enum x, Ord x, Fractional x, Hashable x) => FractionalR (Intersect x)

Defined in Data.JoinSemilattice.Class.Fractional

Methods

multiplyR :: (Intersect x, Intersect x, Intersect x) -> (Intersect x, Intersect x, Intersect x)

class SumR x => IntegralR (x :: Type) where

A four-way divMod relationship between two values, the result of integral division, and the result of the first modulo the second.

Methods

divModR :: (x, x, x, x) -> (x, x, x, x)

Instances

(Eq x, Integral x) => IntegralR (Defined x)

Defined in Data.JoinSemilattice.Class.Integral

Methods

divModR :: (Defined x, Defined x, Defined x, Defined x) -> (Defined x, Defined x, Defined x, Defined x)

(Bounded x, Enum x, Ord x, Hashable x, Integral x) => IntegralR (Intersect x)

Defined in Data.JoinSemilattice.Class.Integral

Methods

divModR :: (Intersect x, Intersect x, Intersect x, Intersect x) -> (Intersect x, Intersect x, Intersect x, Intersect x)

class Lifting (f :: Type -> Type) (c :: Type -> Constraint) | f -> c where

Embed a regular value inside a parameter type.

Methods

lift' :: c x => x -> f x

Instances

Lifting Defined Eq

Defined in Data.JoinSemilattice.Class.Lifting

Methods

lift' :: Eq x => x -> Defined x

Lifting Intersect Intersectable

Defined in Data.JoinSemilattice.Class.Lifting

Methods

lift' :: Intersectable x => x -> Intersect x

class (forall x. c x => Merge (f x)) => Mapping (f :: Type -> Type) (c :: Type -> Constraint) | f -> c where

Lift a relationship between two values over some type constructor. Typically, this type constructor will be the parameter type.

Methods

mapR :: (c x, c y) => (Maybe (x -> y), Maybe (y -> x)) -> (f x, f y) -> (f x, f y)

Instances

Mapping Defined Eq

Defined in Data.JoinSemilattice.Class.Mapping

Methods

mapR :: (Eq x, Eq y) => (Maybe (x -> y), Maybe (y -> x)) -> (Defined x, Defined y) -> (Defined x, Defined y)

Mapping Intersect Intersectable

Defined in Data.JoinSemilattice.Class.Mapping

Methods

mapR :: (Intersectable x, Intersectable y) => (Maybe (x -> y), Maybe (y -> x)) -> (Intersect x, Intersect y) -> (Intersect x, Intersect y)

class (EqR f, forall x. OrdC f x => EqC' f x) => OrdR (f :: Type -> Type) where

Comparison relationships between two values and their comparison result. See EqR for more information on the design of this class, and a full apology for the constraints involved.

Associated Types

type OrdC f :: Type -> Constraint

type OrdC f = EqC f

Methods

lteR :: OrdC f x => (f x, f x, f Bool) -> (f x, f x, f Bool)

A relationship between two values and whether the left is less than or equal to the right.

Instances

OrdR Defined

Defined in Data.JoinSemilattice.Class.Ord

Associated Types

type OrdC Defined :: Type -> Constraint

Methods

lteR :: OrdC Defined x => (Defined x, Defined x, Defined Bool) -> (Defined x, Defined x, Defined Bool)

OrdR Intersect

Defined in Data.JoinSemilattice.Class.Ord

Associated Types

type OrdC Intersect :: Type -> Constraint

Methods

lteR :: OrdC Intersect x => (Intersect x, Intersect x, Intersect Bool) -> (Intersect x, Intersect x, Intersect Bool)

ltR :: (OrdR f, OrdC f x) => (f x, f x, f Bool) -> (f x, f x, f Bool)

Comparison between two values and their (<) result.

gtR :: (OrdR f, OrdC f x) => (f x, f x, f Bool) -> (f x, f x, f Bool)

Comparison between two values and their (>) result.

gteR :: (OrdR f, OrdC f x) => (f x, f x, f Bool) -> (f x, f x, f Bool)

Comparison between two values and their (>=) result.

class Merge x => SumR (x :: Type) where

A relationship between two values and their sum.

Minimal complete definition

Nothing

Methods

addR :: (x, x, x) -> (x, x, x)

default addR :: Num x => (x, x, x) -> (x, x, x)

Instances

(Eq x, Num x) => SumR (Defined x)

Defined in Data.JoinSemilattice.Class.Sum

Methods

addR :: (Defined x, Defined x, Defined x) -> (Defined x, Defined x, Defined x)

(Intersectable x, Num x) => SumR (Intersect x)

Defined in Data.JoinSemilattice.Class.Sum

Methods

addR :: (Intersect x, Intersect x, Intersect x) -> (Intersect x, Intersect x, Intersect x)

negateR :: (Num x, SumR x) => (x, x) -> (x, x)

A relationship between a value and its negation.

subR :: SumR x => (x, x, x) -> (x, x, x)

A relationship between two values and their difference.

class Mapping f c => Zipping (f :: Type -> Type) (c :: Type -> Constraint) | f -> c where

Lift a relationship between three values over some f (usually a parameter type).

Methods

zipWithR :: (c x, c y, c z) => (Maybe ((x, y) -> z), Maybe ((x, z) -> y), Maybe ((y, z) -> x)) -> (f x, f y, f z) -> (f x, f y, f z)

Instances

Zipping Defined Eq

Defined in Data.JoinSemilattice.Class.Zipping

Methods

zipWithR :: (Eq x, Eq y, Eq z) => (Maybe ((x, y) -> z), Maybe ((x, z) -> y), Maybe ((y, z) -> x)) -> (Defined x, Defined y, Defined z) -> (Defined x, Defined y, Defined z)

Zipping Intersect Intersectable

Defined in Data.JoinSemilattice.Class.Zipping

Methods

zipWithR :: (Intersectable x, Intersectable y, Intersectable z) => (Maybe ((x, y) -> z), Maybe ((x, z) -> y), Maybe ((y, z) -> x)) -> (Intersect x, Intersect y, Intersect z) -> (Intersect x, Intersect y, Intersect z)

class Monoid x => Merge (x :: Type) where

Join semilattice (<>) specialised for propagator network needs. Allows types to implement the notion of "knowledge combination".

Methods

(<<-) :: x -> x -> Result x

Merge the news (right) into the current value (left), returning an instruction on how to update the network.

Instances

Eq content => Merge (Defined content)

Defined in Data.JoinSemilattice.Class.Merge

Methods

(<<-) :: Defined content -> Defined content -> Result (Defined content)

(Bounded x, Enum x, Ord x, Hashable x) => Merge (Intersect x)

Defined in Data.JoinSemilattice.Class.Merge

Methods

(<<-) :: Intersect x -> Intersect x -> Result (Intersect x)

data Result (x :: Type)

The result of merging some news into a cell's current knowledge.

Constructors

Unchanged

We've learnt nothing; no updates elsewhere are needed.

Changed x

We've learnt something; fire the propagators!

Failure

We've hit a failure state; discard the computation.

Instances

Functor Result

Defined in Data.JoinSemilattice.Class.Merge

Methods

fmap :: (a -> b) -> Result a -> Result b

(<$) :: a -> Result b -> Result a

Applicative Result

Defined in Data.JoinSemilattice.Class.Merge

Methods

pure :: a -> Result a

(<*>) :: Result (a -> b) -> Result a -> Result b

liftA2 :: (a -> b -> c) -> Result a -> Result b -> Result c

(*>) :: Result a -> Result b -> Result b

(<*) :: Result a -> Result b -> Result a

Eq x => Eq (Result x)

Defined in Data.JoinSemilattice.Class.Merge

Methods

(==) :: Result x -> Result x -> Bool

(/=) :: Result x -> Result x -> Bool

Ord x => Ord (Result x)

Defined in Data.JoinSemilattice.Class.Merge

Methods

compare :: Result x -> Result x -> Ordering

(<) :: Result x -> Result x -> Bool

(<=) :: Result x -> Result x -> Bool

(>) :: Result x -> Result x -> Bool

(>=) :: Result x -> Result x -> Bool

max :: Result x -> Result x -> Result x

min :: Result x -> Result x -> Result x

Show x => Show (Result x)

Defined in Data.JoinSemilattice.Class.Merge

Methods

showsPrec :: Int -> Result x -> ShowS

show :: Result x -> String

showList :: [Result x] -> ShowS

Semigroup x => Semigroup (Result x)

Defined in Data.JoinSemilattice.Class.Merge

Methods

(<>) :: Result x -> Result x -> Result x

sconcat :: NonEmpty (Result x) -> Result x

stimes :: Integral b => b -> Result x -> Result x

Semigroup x => Monoid (Result x)

Defined in Data.JoinSemilattice.Class.Merge

Methods

mempty :: Result x

mappend :: Result x -> Result x -> Result x

mconcat :: [Result x] -> Result x

data Defined (x :: Type)

Defines simple "levels of knowledge" about a value.

Constructors

Unknown

Nothing has told me what this value is.

Exactly x

Everyone who has told me this value agrees.

Conflict

Two sources disagree on what this value should be.

Instances

Functor Defined

Defined in Data.JoinSemilattice.Defined

Methods

fmap :: (a -> b) -> Defined a -> Defined b

(<$) :: a -> Defined b -> Defined a

Applicative Defined

Defined in Data.JoinSemilattice.Defined

Methods

pure :: a -> Defined a

(<*>) :: Defined (a -> b) -> Defined a -> Defined b

liftA2 :: (a -> b -> c) -> Defined a -> Defined b -> Defined c

(*>) :: Defined a -> Defined b -> Defined b

(<*) :: Defined a -> Defined b -> Defined a

BooleanR Defined

Defined in Data.JoinSemilattice.Class.Boolean

Methods

falseR :: Defined Bool

trueR :: Defined Bool

notR :: (Defined Bool, Defined Bool) -> (Defined Bool, Defined Bool)

andR :: (Defined Bool, Defined Bool, Defined Bool) -> (Defined Bool, Defined Bool, Defined Bool)

orR :: (Defined Bool, Defined Bool, Defined Bool) -> (Defined Bool, Defined Bool, Defined Bool)

EqR Defined

Defined in Data.JoinSemilattice.Class.Eq

Associated Types

type EqC Defined :: Type -> Constraint

Methods

eqR :: EqC' Defined x => (Defined x, Defined x, Defined Bool) -> (Defined x, Defined x, Defined Bool)

OrdR Defined

Defined in Data.JoinSemilattice.Class.Ord

Associated Types

type OrdC Defined :: Type -> Constraint

Methods

lteR :: OrdC Defined x => (Defined x, Defined x, Defined Bool) -> (Defined x, Defined x, Defined Bool)

Mapping Defined Eq

Defined in Data.JoinSemilattice.Class.Mapping

Methods

mapR :: (Eq x, Eq y) => (Maybe (x -> y), Maybe (y -> x)) -> (Defined x, Defined y) -> (Defined x, Defined y)

Zipping Defined Eq

Defined in Data.JoinSemilattice.Class.Zipping

Methods

zipWithR :: (Eq x, Eq y, Eq z) => (Maybe ((x, y) -> z), Maybe ((x, z) -> y), Maybe ((y, z) -> x)) -> (Defined x, Defined y, Defined z) -> (Defined x, Defined y, Defined z)

Lifting Defined Eq

Defined in Data.JoinSemilattice.Class.Lifting

Methods

lift' :: Eq x => x -> Defined x

FlatMapping Defined Eq

Defined in Data.JoinSemilattice.Class.FlatMapping

Methods

flatMapR :: (Eq x, Eq y) => (Maybe (x -> Defined y), Maybe (Defined y -> x)) -> (Defined x, Defined y) -> (Defined x, Defined y)

Bounded x => Bounded (Defined x)

Defined in Data.JoinSemilattice.Defined

Methods

minBound :: Defined x

maxBound :: Defined x

Enum content => Enum (Defined content)

Defined in Data.JoinSemilattice.Defined

Methods

succ :: Defined content -> Defined content

pred :: Defined content -> Defined content

toEnum :: Int -> Defined content

fromEnum :: Defined content -> Int

enumFrom :: Defined content -> [Defined content]

enumFromThen :: Defined content -> Defined content -> [Defined content]

enumFromTo :: Defined content -> Defined content -> [Defined content]

enumFromThenTo :: Defined content -> Defined content -> Defined content -> [Defined content]

Eq x => Eq (Defined x)

Defined in Data.JoinSemilattice.Defined

Methods

(==) :: Defined x -> Defined x -> Bool

(/=) :: Defined x -> Defined x -> Bool

Fractional x => Fractional (Defined x)

Defined in Data.JoinSemilattice.Defined

Methods

(/) :: Defined x -> Defined x -> Defined x

recip :: Defined x -> Defined x

fromRational :: Rational -> Defined x

Integral content => Integral (Defined content)

Defined in Data.JoinSemilattice.Defined

Methods

quot :: Defined content -> Defined content -> Defined content

rem :: Defined content -> Defined content -> Defined content

div :: Defined content -> Defined content -> Defined content

mod :: Defined content -> Defined content -> Defined content

quotRem :: Defined content -> Defined content -> (Defined content, Defined content)

divMod :: Defined content -> Defined content -> (Defined content, Defined content)

toInteger :: Defined content -> Integer

Num x => Num (Defined x)

Defined in Data.JoinSemilattice.Defined

Methods

(+) :: Defined x -> Defined x -> Defined x

(-) :: Defined x -> Defined x -> Defined x

(*) :: Defined x -> Defined x -> Defined x

negate :: Defined x -> Defined x

abs :: Defined x -> Defined x

signum :: Defined x -> Defined x

fromInteger :: Integer -> Defined x

Ord x => Ord (Defined x)

Defined in Data.JoinSemilattice.Defined

Methods

compare :: Defined x -> Defined x -> Ordering

(<) :: Defined x -> Defined x -> Bool

(<=) :: Defined x -> Defined x -> Bool

(>) :: Defined x -> Defined x -> Bool

(>=) :: Defined x -> Defined x -> Bool

max :: Defined x -> Defined x -> Defined x

min :: Defined x -> Defined x -> Defined x

Real content => Real (Defined content)

Defined in Data.JoinSemilattice.Defined

Methods

toRational :: Defined content -> Rational

Show x => Show (Defined x)

Defined in Data.JoinSemilattice.Defined

Methods

showsPrec :: Int -> Defined x -> ShowS

show :: Defined x -> String

showList :: [Defined x] -> ShowS

Generic (Defined x)

Defined in Data.JoinSemilattice.Defined

Associated Types

type Rep (Defined x) :: Type -> Type

Methods

from :: Defined x -> Rep (Defined x) x0

to :: Rep (Defined x) x0 -> Defined x

Eq content => Semigroup (Defined content)

Defined in Data.JoinSemilattice.Defined

Methods

(<>) :: Defined content -> Defined content -> Defined content

sconcat :: NonEmpty (Defined content) -> Defined content

stimes :: Integral b => b -> Defined content -> Defined content

Eq content => Monoid (Defined content)

Defined in Data.JoinSemilattice.Defined

Methods

mempty :: Defined content

mappend :: Defined content -> Defined content -> Defined content

mconcat :: [Defined content] -> Defined content

Hashable x => Hashable (Defined x)

Defined in Data.JoinSemilattice.Defined

Methods

hashWithSalt :: Int -> Defined x -> Int

hash :: Defined x -> Int

Input (Defined content)

Defined in Data.JoinSemilattice.Defined

Associated Types

type Raw (Defined content)

Methods

from :: forall (m :: Type -> Type). Applicative m => Int -> [Raw (Defined content)] -> Config m (Defined content)

Eq content => Merge (Defined content)

Defined in Data.JoinSemilattice.Class.Merge

Methods

(<<-) :: Defined content -> Defined content -> Result (Defined content)

(Eq x, Num x) => SumR (Defined x)

Defined in Data.JoinSemilattice.Class.Sum

Methods

addR :: (Defined x, Defined x, Defined x) -> (Defined x, Defined x, Defined x)

(Eq x, Integral x) => IntegralR (Defined x)

Defined in Data.JoinSemilattice.Class.Integral

Methods

divModR :: (Defined x, Defined x, Defined x, Defined x) -> (Defined x, Defined x, Defined x, Defined x)

(Eq x, Fractional x) => FractionalR (Defined x)

Defined in Data.JoinSemilattice.Class.Fractional

Methods

multiplyR :: (Defined x, Defined x, Defined x) -> (Defined x, Defined x, Defined x)

(Eq x, Num x) => AbsR (Defined x)

Defined in Data.JoinSemilattice.Class.Abs

Methods

absR :: (Defined x, Defined x) -> (Defined x, Defined x)

type EqC Defined

Defined in Data.JoinSemilattice.Class.Eq

type EqC Defined = Eq

type OrdC Defined

Defined in Data.JoinSemilattice.Class.Ord

type OrdC Defined = Ord

type Rep (Defined x)

Defined in Data.JoinSemilattice.Defined

type Rep (Defined x) = D1 ('MetaData "Defined" "Data.JoinSemilattice.Defined" "holmes-0.3.2.0-IZRXzdzxzGIK7susMZefUq" 'False) (C1 ('MetaCons "Unknown" 'PrefixI 'False) (U1 :: Type -> Type) :+: (C1 ('MetaCons "Exactly" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 x)) :+: C1 ('MetaCons "Conflict" 'PrefixI 'False) (U1 :: Type -> Type)))

type Raw (Defined content)

Defined in Data.JoinSemilattice.Defined

type Raw (Defined content) = content

newtype Intersect (x :: Type)

A set type with intersection as the (<>) operation.

Constructors

Intersect

Fields

• toHashSet :: HashSet x

Instances

Foldable Intersect

Defined in Data.JoinSemilattice.Intersect

Methods

fold :: Monoid m => Intersect m -> m

foldMap :: Monoid m => (a -> m) -> Intersect a -> m

foldMap' :: Monoid m => (a -> m) -> Intersect a -> m

foldr :: (a -> b -> b) -> b -> Intersect a -> b

foldr' :: (a -> b -> b) -> b -> Intersect a -> b

foldl :: (b -> a -> b) -> b -> Intersect a -> b

foldl' :: (b -> a -> b) -> b -> Intersect a -> b

foldr1 :: (a -> a -> a) -> Intersect a -> a

foldl1 :: (a -> a -> a) -> Intersect a -> a

toList :: Intersect a -> [a]

null :: Intersect a -> Bool

length :: Intersect a -> Int

elem :: Eq a => a -> Intersect a -> Bool

maximum :: Ord a => Intersect a -> a

minimum :: Ord a => Intersect a -> a

sum :: Num a => Intersect a -> a

product :: Num a => Intersect a -> a

BooleanR Intersect

Defined in Data.JoinSemilattice.Class.Boolean

Methods

falseR :: Intersect Bool

trueR :: Intersect Bool

notR :: (Intersect Bool, Intersect Bool) -> (Intersect Bool, Intersect Bool)

andR :: (Intersect Bool, Intersect Bool, Intersect Bool) -> (Intersect Bool, Intersect Bool, Intersect Bool)

orR :: (Intersect Bool, Intersect Bool, Intersect Bool) -> (Intersect Bool, Intersect Bool, Intersect Bool)

EqR Intersect

Defined in Data.JoinSemilattice.Class.Eq

Associated Types

type EqC Intersect :: Type -> Constraint

Methods

eqR :: EqC' Intersect x => (Intersect x, Intersect x, Intersect Bool) -> (Intersect x, Intersect x, Intersect Bool)

OrdR Intersect

Defined in Data.JoinSemilattice.Class.Ord

Associated Types

type OrdC Intersect :: Type -> Constraint

Methods

lteR :: OrdC Intersect x => (Intersect x, Intersect x, Intersect Bool) -> (Intersect x, Intersect x, Intersect Bool)

Mapping Intersect Intersectable

Defined in Data.JoinSemilattice.Class.Mapping

Methods

mapR :: (Intersectable x, Intersectable y) => (Maybe (x -> y), Maybe (y -> x)) -> (Intersect x, Intersect y) -> (Intersect x, Intersect y)

Zipping Intersect Intersectable

Defined in Data.JoinSemilattice.Class.Zipping

Methods

zipWithR :: (Intersectable x, Intersectable y, Intersectable z) => (Maybe ((x, y) -> z), Maybe ((x, z) -> y), Maybe ((y, z) -> x)) -> (Intersect x, Intersect y, Intersect z) -> (Intersect x, Intersect y, Intersect z)

Lifting Intersect Intersectable

Defined in Data.JoinSemilattice.Class.Lifting

Methods

lift' :: Intersectable x => x -> Intersect x

FlatMapping Intersect Intersectable

Defined in Data.JoinSemilattice.Class.FlatMapping

Methods

flatMapR :: (Intersectable x, Intersectable y) => (Maybe (x -> Intersect y), Maybe (Intersect y -> x)) -> (Intersect x, Intersect y) -> (Intersect x, Intersect y)

Eq x => Eq (Intersect x)

Defined in Data.JoinSemilattice.Intersect

Methods

(==) :: Intersect x -> Intersect x -> Bool

(/=) :: Intersect x -> Intersect x -> Bool

(Intersectable x, Fractional x) => Fractional (Intersect x)

Defined in Data.JoinSemilattice.Intersect

Methods

(/) :: Intersect x -> Intersect x -> Intersect x

recip :: Intersect x -> Intersect x

fromRational :: Rational -> Intersect x

(Intersectable content, Num content) => Num (Intersect content)

Defined in Data.JoinSemilattice.Intersect

Methods

(+) :: Intersect content -> Intersect content -> Intersect content

(-) :: Intersect content -> Intersect content -> Intersect content

(*) :: Intersect content -> Intersect content -> Intersect content

negate :: Intersect content -> Intersect content

abs :: Intersect content -> Intersect content

signum :: Intersect content -> Intersect content

fromInteger :: Integer -> Intersect content

Ord x => Ord (Intersect x)

Defined in Data.JoinSemilattice.Intersect

Methods

compare :: Intersect x -> Intersect x -> Ordering

(<) :: Intersect x -> Intersect x -> Bool

(<=) :: Intersect x -> Intersect x -> Bool

(>) :: Intersect x -> Intersect x -> Bool

(>=) :: Intersect x -> Intersect x -> Bool

max :: Intersect x -> Intersect x -> Intersect x

min :: Intersect x -> Intersect x -> Intersect x

Show x => Show (Intersect x)

Defined in Data.JoinSemilattice.Intersect

Methods

showsPrec :: Int -> Intersect x -> ShowS

show :: Intersect x -> String

showList :: [Intersect x] -> ShowS

(Eq content, Hashable content) => Semigroup (Intersect content)

Defined in Data.JoinSemilattice.Intersect

Methods

(<>) :: Intersect content -> Intersect content -> Intersect content

sconcat :: NonEmpty (Intersect content) -> Intersect content

stimes :: Integral b => b -> Intersect content -> Intersect content

Intersectable content => Monoid (Intersect content)

Defined in Data.JoinSemilattice.Intersect

Methods

mempty :: Intersect content

mappend :: Intersect content -> Intersect content -> Intersect content

mconcat :: [Intersect content] -> Intersect content

Hashable x => Hashable (Intersect x)

Defined in Data.JoinSemilattice.Intersect

Methods

hashWithSalt :: Int -> Intersect x -> Int

hash :: Intersect x -> Int

Intersectable x => Input (Intersect x)

Defined in Data.JoinSemilattice.Intersect

Associated Types

type Raw (Intersect x)

Methods

from :: forall (m :: Type -> Type). Applicative m => Int -> [Raw (Intersect x)] -> Config m (Intersect x)

(Bounded x, Enum x, Ord x, Hashable x) => Merge (Intersect x)

Defined in Data.JoinSemilattice.Class.Merge

Methods

(<<-) :: Intersect x -> Intersect x -> Result (Intersect x)

(Intersectable x, Num x) => SumR (Intersect x)

Defined in Data.JoinSemilattice.Class.Sum

Methods

addR :: (Intersect x, Intersect x, Intersect x) -> (Intersect x, Intersect x, Intersect x)

(Bounded x, Enum x, Ord x, Hashable x, Integral x) => IntegralR (Intersect x)

Defined in Data.JoinSemilattice.Class.Integral

Methods

divModR :: (Intersect x, Intersect x, Intersect x, Intersect x) -> (Intersect x, Intersect x, Intersect x, Intersect x)

(Bounded x, Enum x, Ord x, Fractional x, Hashable x) => FractionalR (Intersect x)

Defined in Data.JoinSemilattice.Class.Fractional

Methods

multiplyR :: (Intersect x, Intersect x, Intersect x) -> (Intersect x, Intersect x, Intersect x)

(Bounded x, Enum x, Ord x, Hashable x, Num x) => AbsR (Intersect x)

Defined in Data.JoinSemilattice.Class.Abs

Methods

absR :: (Intersect x, Intersect x) -> (Intersect x, Intersect x)

type EqC Intersect

Defined in Data.JoinSemilattice.Class.Eq

type EqC Intersect = Intersectable

type OrdC Intersect

Defined in Data.JoinSemilattice.Class.Ord

type OrdC Intersect

type Raw (Intersect x)

Defined in Data.JoinSemilattice.Intersect

type Raw (Intersect x) = x

using :: (Applicative m, Intersectable x) => [Intersect x] -> Config m (Intersect x)

Produce a Config with the given initial value, where the refine function just tries each remaining candidate as a singleton.

data Prop (m :: Type -> Type) (content :: Type)

A propagator network with a "focus" on a particular cell. The focus is the cell that typically holds the result we're trying to compute.

Instances

(AbsR x, Fractional x, FractionalR x, Num x, MonadCell m) => Fractional (Prop m x)

Defined in Data.Propagator

Methods

(/) :: Prop m x -> Prop m x -> Prop m x

recip :: Prop m x -> Prop m x

fromRational :: Rational -> Prop m x

(AbsR x, SumR x, Num x, MonadCell m) => Num (Prop m x)

Defined in Data.Propagator

Methods

(+) :: Prop m x -> Prop m x -> Prop m x

(-) :: Prop m x -> Prop m x -> Prop m x

(*) :: Prop m x -> Prop m x -> Prop m x

negate :: Prop m x -> Prop m x

abs :: Prop m x -> Prop m x

signum :: Prop m x -> Prop m x

fromInteger :: Integer -> Prop m x

up :: Applicative m => Cell m x -> Prop m x

Lift a cell into a propagator network. Mostly for internal library use.

down :: (MonadCell m, Monoid x) => Prop m x -> m (Cell m x)

Lower a propagator network's focal point down to a cell. Mostly for internal library use.

lift :: forall f m c x. (MonadCell m, c x) => Lifting f c => x -> Prop m (f x)

over :: (Merge x, Merge y) => (x -> y) -> Prop m x -> Prop m y

Lift a regular function into a propagator network. The function is lifted into a relationship with one-way information flow.

unary :: (Merge x, Merge y) => ((x, y) -> (x, y)) -> Prop m x -> Prop m y

Lift a unary relationship into a propagator network. Unlike over, this allows information to travel in both directions.

binary :: (Merge x, Merge y, Merge z) => ((x, y, z) -> (x, y, z)) -> Prop m x -> Prop m y -> Prop m z

Lift a binary relationship into a propagator network. This allows three-way information flow.

(.$) :: (Mapping f c, c x, c y) => (x -> y) -> Prop m (f x) -> Prop m (f y)

Lift a regular function over a propagator network and its parameter type. Unlike over, this function abstracts away the specific behaviour of the parameter type (such as Defined).

(.>>=) :: (FlatMapping f c, c x, c y) => Prop m (f x) -> (x -> f y) -> Prop m (f y)

Produce a network in which the raw values of a given network are used to produce new parameter types. See the "wave function collapse" demo for an example usage.

zipWith' :: (Zipping f c, c x, c y, c z) => (x -> y -> z) -> Prop m (f x) -> Prop m (f y) -> Prop m (f z)

Lift a three-way relationship over two propagator networks' foci to produce a third propagator network with a focus on the third value in the relationship.

... It's liftA2 for propagators.

(.&&) :: BooleanR f => Prop m (f Bool) -> Prop m (f Bool) -> Prop m (f Bool) infixr 3

Different parameter types come with different representations for Bool. This function takes two propagator networks focusing on boolean values, and produces a new network in which the focus is the conjunction of the two values.

It's a lot of words, but the intuition is, "(&&) over propagators".

all' :: (BooleanR f, MonadCell m) => (x -> Prop m (f Bool)) -> [x] -> Prop m (f Bool)

Run a predicate on all values in a list, producing a list of propagator networks focusing on boolean values. Then, produce a new network with a focus on the conjunction of all these values.

In other words, "all over propagators".

allWithIndex' :: (BooleanR f, MonadCell m) => (Int -> x -> Prop m (f Bool)) -> [x] -> Prop m (f Bool)

The same as the all' function, but with access to the index of the element within the array. Typically, this is useful when trying to relate each element to other elements within the array.

For example, cells "surrounding" the current cell in a conceptual "board".

and' :: (BooleanR f, MonadCell m) => [Prop m (f Bool)] -> Prop m (f Bool)

Given a list of propagator networks with a focus on boolean values, create a new network with a focus on the conjugation of all these values.

In other words, "and over propagators".

(.||) :: BooleanR f => Prop m (f Bool) -> Prop m (f Bool) -> Prop m (f Bool) infixr 2

Calculate the disjunction of two boolean propagator network values.

any' :: (BooleanR f, MonadCell m) => (x -> Prop m (f Bool)) -> [x] -> Prop m (f Bool)

Run a predicate on all values in a list, producing a list of propagator networks focusing on boolean values. Then, produce a new network with a focus on the disjunction of all these values.

In other words, "any over propagators".

anyWithIndex' :: (BooleanR f, MonadCell m) => (Int -> x -> Prop m (f Bool)) -> [x] -> Prop m (f Bool)

The same as the any' function, but with access to the index of the element within the array. Typically, this is useful when trying to relate each element to other elements within the array.

For example, cells "surrounding" the current cell in a conceptual "board".

or' :: (BooleanR f, MonadCell m) => [Prop m (f Bool)] -> Prop m (f Bool)

Given a list of propagator networks with a focus on boolean values, create a new network with a focus on the disjunction of all these values.

In other words, "or over propagators".

not' :: (BooleanR f, MonadCell m) => Prop m (f Bool) -> Prop m (f Bool)

Given a propagator network with a focus on a boolean value, produce a network with a focus on its negation.

... It's "not over propagators".

false :: (BooleanR f, MonadCell m) => Prop m (f Bool)

Different parameter types come with different representations for Bool. This value is a propagator network with a focus on a polymorphic "falsey" value.

true :: (BooleanR f, MonadCell m) => Prop m (f Bool)

Different parameter types come with different representations for Bool. This value is a propagator network with a focus on a polymorphic "truthy" value.

(.*) :: (FractionalR x, MonadCell m) => Prop m x -> Prop m x -> Prop m x infixl 7

Given two propagator networks, produce a new network that focuses on the product of the two given networks' foci.

... It's (*) lifted over propagator networks. The reverse information flow is fractional division, (/).

(./) :: (FractionalR x, MonadCell m) => Prop m x -> Prop m x -> Prop m x infixl 7

Given two propagator networks, produce a new network that focuses on the division of the two given networks' foci.

... It's (/) lifted over propagator networks.

(.+) :: (SumR x, MonadCell m) => Prop m x -> Prop m x -> Prop m x infixl 6

Given two propagator networks, produce a new network that focuses on the sum of the two given networks' foci.

... It's (+) lifted over propagator networks.

(.-) :: (SumR x, MonadCell m) => Prop m x -> Prop m x -> Prop m x infixl 6

Given two propagator networks, produce a new network that focuses on the difference between the two given networks' foci.

... It's (-) lifted over propagator networks.

(.<) :: (OrdR f, OrdC f x, MonadCell m) => Prop m (f x) -> Prop m (f x) -> Prop m (f Bool) infix 4

Given two propagator networks, produce a new network that calculates whether the first network's focus be less than the second.

In other words, "it's (<) for propagators".

(.<=) :: (OrdR f, OrdC f x, MonadCell m) => Prop m (f x) -> Prop m (f x) -> Prop m (f Bool) infix 4

Given two propagator networks, produce a new network that calculates whether the first network's focus be less than or equal to the second.

In other words, "it's (<=) for propagators".

(.>) :: (OrdR f, OrdC f x, MonadCell m) => Prop m (f x) -> Prop m (f x) -> Prop m (f Bool) infix 4

Given two propagator networks, produce a new network that calculates whether the first network's focus be greater than the second.

In other words, "it's (>) for propagators".

(.>=) :: (OrdR f, OrdC f x, MonadCell m) => Prop m (f x) -> Prop m (f x) -> Prop m (f Bool) infix 4

Given two propagator networks, produce a new network that calculates whether the first network's focus be greater than or equal to the second.

In other words, "it's (>=) for propagators".

(.==) :: (EqR f, EqC f x, MonadCell m) => Prop m (f x) -> Prop m (f x) -> Prop m (f Bool) infix 4

Given two propagator networks, produce a new propagator network with the result of testing the two for equality.

In other words, "it's (==) for propagators".

(./=) :: (EqR f, EqC f x, MonadCell m) => Prop m (f x) -> Prop m (f x) -> Prop m (f Bool) infix 4

Given two propagator networks, produce a new propagator network with the result of testing the two for inequality.

In other words, "it's (/=) for propagators".

distinct :: (EqR f, EqC f x, MonadCell m) => [Prop m (f x)] -> Prop m (f Bool)

Given a list of networks, produce the conjunction of (./=) applied to every possible pair. The resulting network's focus is the answer to whether every propagator network's focus is different to the others.

Are all the values in this list distinct?

(.%.) :: (IntegralR x, MonadCell m) => Prop m x -> Prop m x -> Prop m x infixl 7

Given two propagator networks, produce a new network that focuses on the modulo of the two given networks' integral foci.

... It's mod lifted over propagator networks.

(.*.) :: (Num x, IntegralR x) => Prop m x -> Prop m x -> Prop m x infixl 7

Given two propagator networks, produce a new network that focuses on the product between the two given networks' integral foci.

... It's (*) lifted over propagator networks. Crucially, the reverse information flow uses integral division, which should work the same way as div.

(./.) :: (IntegralR x, MonadCell m) => Prop m x -> Prop m x -> Prop m x infixl 7

Given two propagator networks, produce a new network that focuses on the division of the two given networks' integral foci.

... It's div lifted over propagator networks.

abs' :: (AbsR x, MonadCell m) => Prop m x -> Prop m x

Produce a network that focuses on the absolute value of another network's focus.

... It's abs lifted over propagator networks.

negate' :: (Num x, SumR x, MonadCell m) => Prop m x -> Prop m x

Produce a network that focuses on the negation of another network's focus.

... It's negate lifted over propagator networks.

recip' :: (Num x, FractionalR x, MonadCell m) => Prop m x -> Prop m x

Produce a network that focuses on the reciprocal of another network's focus.

... It's recip lifted over propagator networks.