[Haskell-cafe] Simple Sudoku solver using Control.Monad.Logic

[Sebastian Fischer]

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

is an interesting read.

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.

Issue 15 of the Monad.Reader contains

     Adventures in Three Monads
     by Edward Z. Yang
     http://themonadreader.files.wordpress.com/2010/01/issue15.pdf

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
     Section 5.1, Nondeterminism monads
     http://www-ps.informatik.uni-kiel.de/~sebf/thesis.pdf

There are various nondeterminism monads on Hackage. If you restrict  
your algorithm to only use the MonadPlus interface you can experiment  
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.

My package level-monad [2] provides monads for iterative deepening  
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  
stream-monad [3].

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

[1]: http://hackage.haskell.org/package/control-monad-omega
[2]: http://hackage.haskell.org/package/level-monad
[3]: http://hackage.haskell.org/package/stream-monad



-- 
Underestimating the novelty of the future is a time-honored tradition.
(D.G.)