Documentation

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.

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.

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.

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

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

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.

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!

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.

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!"

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!

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.

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.

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.

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

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.

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

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

Embed a regular value inside a parameter type.

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

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.

Comparison between two values and their (<) result.

Comparison between two values and their (>) result.

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

A relationship between two values and their sum.

A relationship between a value and its negation.

A relationship between two values and their difference.

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

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

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

Defines simple "levels of knowledge" about a value.

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

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

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.

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

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

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

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

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

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

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.

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.

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".

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".

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".

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".

Calculate the disjunction of two boolean propagator network values.

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".

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".

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".

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".

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

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

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, (/).

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.

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.

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.

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".

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".

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".

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".

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".

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".

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?

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.

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.

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.

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

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

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

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

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

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