On Jun 19, 2009, at 5:06 PM, Sebastian Fischer wrote:
Your Monad and MonadPlus instances lead me to an interesting
observation. Various strategies for non-deterministic search can be
implemented using FMList by expressing failure and choice via a
Monoid instance.
I have just finished a revision of a paper that explains how to
factor two-continuation based backtracking (and other strategies)
into a continuation monad transformer and a type class for non-
deterministic computations (I'd be glad to receive comments!).
http://www-ps.informatik.uni-kiel.de/~sebf/pub/atps09.html
Now I recognise that one can also use FMList as the part that
provides return and >>= and any Monoid for failure and choice.
Especially, one can implement breadth-first search (bfs) using a
monoid that collects levels of a search tree and iterative deepening
depth-first search (idfs) using a monoid that represents depth-
bounded computations.
I have updated my package level-monad to use your library and monoids:
http://hackage.haskell.org/package/level-monad
The employed Monoid instances do not satisfy any monoid law.
However, these are the simplest implementations of bfs and idfs that
I am aware of, so I don't care very much ;)
Very nice. It is cool to see someone using this already! I see you did
performance tests. How does your current version compare to f.e. one
based on DiffLists?
I wonder though, aren't you worried that updated versions of FMList
might use the monoid laws to rewrite certains bits, and your code
would break? Essentially you are using FMLists as a tree structure,
which isn't possible when you abide by the monoid laws.
I think you should be able to do the same thing in as many lines,
using f.e. the ChoiceT type from MonadLib, where bfs and idfsBy are
variations on runChoiceT. The ChoiceEff part might complicate things a
bit though. But I might be missing some essential detail.
greetings,
--
Sjoerd Visscher
sjo...@w3future.com
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
