[Haskell-cafe] Simple Sudoku solver using Control.Monad.Logic
dpx.infinity at gmail.com
Mon Aug 23 07:04:25 EDT 2010
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
> 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
> 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
> 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  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  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 .
> 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.
> : http://hackage.haskell.org/package/control-monad-omega
> : http://hackage.haskell.org/package/level-monad
> : http://hackage.haskell.org/package/stream-monad
> Underestimating the novelty of the future is a time-honored tradition.
More information about the Haskell-Cafe