Many thanks. This is very useful :)
2010/8/23 Sebastian Fischer <s...@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.) > > > > _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
