[Haskell-cafe] ANNOUNCE fmlist

[Sjoerd Visscher]

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 at w3future.com