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 sjoerd@w3future.com