Journal of Functional Programming

Articles

Monadic constraint programming

TOM SCHRIJVERSa1, PETER STUCKEYa2 and PHILIP WADLERa3

a1 Department of Computer Science, K.U.Leuven, Leuven, Belgium (e-mail: tom.schrijvers@cs.kuleuven.be)

a2 National ICT Australia, Victoria Laboratory, Department of Computer Science and Software Engineering, University of Melbourne, Melbourne, Australia (e-mail: pjs@cs.mu.OZ.AU)

a3 School of Informatics, University of Edinburgh, Edinburgh, Scotland, UK (e-mail: philip.wadler@ed.ac.uk)

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.

(Online publication August 14 2009)