Monadic constraint programming
- 1 March 2009
- journal article
- research article
- Published by Cambridge University Press (CUP) in Journal of Functional Programming
- Vol. 19 (6), 663-697
- https://doi.org/10.1017/s0956796809990086
Abstract
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 in which 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 transformers. 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.Keywords
This publication has 20 references indexed in Scilit:
- Nondeterministic Control for Hybrid SearchConstraints, 2006
- FUNCTIONAL PEARL: A program to solve SudokuJournal of Functional Programming, 2006
- Backtracking, interleaving, and terminating monad transformersACM SIGPLAN Notices, 2005
- Search and strategies in OPLACM Transactions on Computational Logic, 2000
- Theory and practice of constraint handling rulesThe Journal of Logic Programming, 1998
- Alma-OACM Transactions on Programming Languages and Systems, 1998
- Polytypic unificationJournal of Functional Programming, 1998
- Programming constraint inference enginesPublished by Springer Science and Business Media LLC ,1997
- The execution algorithm of mercury, an efficient purely declarative logic programming languageThe Journal of Logic Programming, 1996
- The Oz Programming ModelPublished by Springer Science and Business Media LLC ,1995