holmes-0.3.2.0: Tools and combinators for solving constraint problems.

Data.Input.Config

Description

Simplistically, search problems are solved by running the computation with different input combinations, looking for any combinations that satisfy the constraints. In reality, we play some tricks to avoid running every possible input combination, but the principle is the same:

This module exposes the Config type, which stores an initial assignment for the input parameters (typically something close to mempty), and a function that generates possible refinements for those inputs.

For example, we might have a variable we know must be a number between 1 and 10. A good initial value for this might be a mempty value such as Unknown, with the refinements being Exactly the ten possible values.

The initial values are first fed into the computation before the propagators are established. Sometimes, these initial propagators can produce new information (such as advancing a few steps forward in a sudoku puzzle) before we even start to refine the inputs. The benefit here is that we can sometimes discover that a variable's search space is smaller than we realise, and so we end up with much less work to do!

Synopsis

# Documentation

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

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 Fieldsinitial :: [x] refine :: x -> m [x]

class Input (x :: Type) where Source #

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 Source #

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 Source #

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

#### Instances

Instances details
 Input (Defined content) Source # Instance detailsDefined in Data.JoinSemilattice.Defined Associated Typestype Raw (Defined content) Source # Methodsfrom :: forall (m :: Type -> Type). Applicative m => Int -> [Raw (Defined content)] -> Config m (Defined content) Source # Intersectable x => Input (Intersect x) Source # Instance detailsDefined in Data.JoinSemilattice.Intersect Associated Typestype Raw (Intersect x) Source # Methodsfrom :: forall (m :: Type -> Type). Applicative m => Int -> [Raw (Intersect x)] -> Config m (Intersect x) Source #

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

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!