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.)