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

[Vladimir Matveev]

Many thanks. This is very useful :)

2010/8/23 Sebastian Fischer <sebf at informatik.uni-kiel.de>:
>
> 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.)
>
>
>
>