Monadic constraint programming

Tom Schrijvers, Peter Stuckey, Philip Wadler

Research output: Contribution to journalArticlepeer-review

Abstract

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.
Original languageEnglish
Pages (from-to)663-697
Number of pages35
JournalJournal of Functional Programming
Volume19
Issue number6
Early online date14 Aug 2009
DOIs
Publication statusPublished - 2009

Keywords

  • Informatics
  • Computer Science

Fingerprint Dive into the research topics of 'Monadic constraint programming'. Together they form a unique fingerprint.

Cite this