Documentation

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.

In our regular Haskell coding, a binary function usually looks something like x -> y -> z. When we view it as a relationship, we see that it's actually a relationship between three values: x, y, and z.

Given a function that takes everything we currently know about these three values, and returns three "updates" based on what each can learn from the others, we can lift our three-way relationship (which, again, we can intuit as a multi-directional binary function) into a network as a three-way propagator. As an illustrative example, we might convert the '(+)' function into something like:

addR :: (Int, Int, Int) -> (Int, Int, Int)
addR ( a, b, c ) = ( c - b, c - a, a + b )

In practice, these values must be Merge values (unlike Int), and so any of them could be mempty, or less-than-well-defined. This function will take the three results as updates, and Merge it into the cell, so they will only make a difference if we've learnt something new.

Create a cell with "no information", which we represent as mempty. When we evaluate propagator computations written with the Prop abstraction, this function is used to create the result cells at each node of the computation.

It's therefore important that your mempty value is reasonably efficient to compute, as larger computations may involve producing many of these values as intermediaries. An Intersect of all Int values, for example, is going to make things run very slowly.

This function takes two cells, and establishes propagators between them in both directions. These propagators simply copy across any updates that either cell receives, which means that the two cells end up holding exactly the same value at all times.

After calling this function, the two cells are entirely indistinguishable, as they will always be equivalent. We can intuit this function as "merging two cells into one".

A standard unary function goes from an input value to an output value. However, in the world of propagators, it is more powerful to rethink this as a relationship between two values.

A good example is the negate function. It doesn't matter whether you know the input or the output; it's always possible to figure out the one you're missing. Why, then, should our program only run in one direction? We could rephrase negate from 'Int -> Int' to something more like:

negateR :: ( Maybe Int, Maybe Int ) -> ( Maybe Int, Maybe Int )
negateR ( x, y ) = ( x | fmap negate y, y | fmap negate x )

Now, if we're missing one of the values, we can calculate it using the other! This, and the binary function's description above, give us an idea of how functions and relationships differ. The unary function simply lifts one of these expressions into a two-way propagator between two cells.

The Merge constraint means that we can use mempty to represent "knowing nothing" rather than the Maybe in the above example, which makes this function a little more generalised.