Journal of functional programming vol:19 issue:6 pages:663-697
A constraint programming system combines two essential components:
a constraint solver and a search engine. The constraint solver
reasons about satisfiability of
conjunctions of constraints, and the search engine controls the
search for solutions by iteratively exploring a
disjunctive search tree defined by the constraint program.
In this paper we give a monadic definition of constraint
programming where the solver is defined as a
monad threaded through the monadic search tree.
We are then able to define search and search strategies as
first class objects that
can themselves be built or extended by composable search
Search transformers give a powerful and unifying approach to viewing search
in constraint programming,
and the resulting constraint programming
system is first class and extremely flexible.