Monad Transformers for Backtracking Search

Abstract

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.

In Proceedings MSFP 2014, arXiv:1406.1534

Cited by in corpus (3)

• The selection monad as a CPS transformation
• String diagrams for game theory
• A Higher-order Framework for Decision Problems and Games