Sebastian Fischer sebf at informatik.uni-kiel.de
Mon Aug 23 06:23:31 EDT 2010

```On Aug 22, 2010, at 11:09 PM, Vladimir Matveev wrote:

> are there any materials
> except LogicT.pdf from link on the logict hackage entry? I'd like to
> read something on this interesting topic

The functional pearl

A program to solve Sudoku
by Richard Bird
http://www.cs.tufts.edu/~nr/comp150fp/archive/richard-bird/
sudoku.pdf

If you get your hands on a copy of "The Fun of Programming", which has
been edited in honour of Richard Birds 60th birthday, you can have a
look at

Chapter 9, Combinators for logic programming
by Mike Spivey and Silvija Seres

I did not find this chapter online.

by Edward Z. Yang

which gives an introduction to the Logic monad (and two others).

In my doctoral thesis I give a brief introduction to nondeterminism
monads in general and how to implement some specific instances:

On Functional-Logic Programming and its Application to Testing
by Sebastian Fischer
http://www-ps.informatik.uni-kiel.de/~sebf/thesis.pdf

There are various nondeterminism monads on Hackage. If you restrict
with all of them simply by changing a type signature.

The list monad (not on Hackage because defined in the Prelude)
implements backtracking via depth-first search.

The Hackage package control-monad-omega [1] by Luke Palmer uses list
diagonalisation to overcome limitations of the list monad. It is
described to implement breadth-first search which, in my opinion, it
doesn't exactly.

depth-first search and breadth-first search. The latter enumerates
results of the search space in breadth-first (that is level) order.
The former does something similar with better space usage.

The different implementations of nondeterminism monads often differ
significantly in how much memory they use. The list monad uses little
memory but often diverges when the search space is infinite. Breadth-
first search is a complete strategy (it does not diverge infinite
search spaces and, thus, eventually finds every result) but has
excessive memory requirements. Oleg Kiselyov has invented a complete
strategy with moderate memory requirements which I have packaged as

I recommend using the list or logic monad if the search space is
finite and the stream monad or iterative deepening dfs if the search
space is infinite.

Cheers,
Sebastian