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.)
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
