2014/06/09 by Jules Hedges
Computer Science · #cs.PL
paper · pdf · doi:10.4204/eptcs.153.3
published as EPTCS 153, 2014, pp. 31-50 · In Proceedings MSFP 2014, arXiv:1406.1534
arxiv created 2014/06/09 · arxiv updated 2014/06/10
This paper extends Escardo and Oliva's selection monad to the selection monad transformer, a general monadic framework for expressing backtracking search algorithms in Haskell. The use of the closely related continuation monad transformer for similar purposes is also discussed, including an implementation of a DPLL-like SAT solver with no explicit recursion. Continuing a line of work exploring connections between selection functions and game theory, we use the selection monad transformer with the nondeterminism monad to obtain an intuitive notion of backward induction for a certain class of nondeterministic games.