[Haskell-cafe] ANNOUNCE fmlist

[Sebastian Fischer]

On Jun 19, 2009, at 7:12 PM, Sjoerd Visscher wrote:

> I see you did performance tests. How does your current version  
> compare to f.e. one based on DiffLists?

The current versions (0.4) of bfs and idfs based on FMList (0.5) use  
the same amount of memory and are about 10-15% slower than  
corresponding versions of breadth-first search and iterative deepening  
depth-first search based on CPS and DiffList when enumerating  
pythagorean triples without an upper bound (I didn't check other  
examples).

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

Manipulating w.r.t. monoid laws may change the order in which results  
are computed by bfs and idfs. However, I won't consider this breaking  
the code. The important property of bfs and idfs is that all results  
are eventually computed and I happily abstract from their order when  
enumerating results of non-deterministic computations. Other people  
may disagree though, so I should mention something about it in the docs.

If rewriting FMList w.r.t. monoid laws would break the completeness of  
the strategies I would be concerned. But currently I have the  
impression that parametricity ensures that I will always be able to  
convert an FMList into the (implicit) tree structures that I use for  
complete search.

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

I think so too. With a monad instance for a tree structure one can  
implement both strategies as well. However, the continuation-based  
implementation of monadic bind is more efficient when nested left  
associatively [1]. One could regain the asymptotic improvement of  
monadic bind by wrapping ChoiceT under ContT but that seems inelegant  
as it uses more monads than necessary.

By using a free representation of a pointed monoid one could use  
fmlists to generate the tree structure of a search space:

   data PMonoid a = Point a | Empty | Append (PMonoid a) (PMonoid a)

   instance Monoid PMonoid where
     mempty  = Empty
     mappend = Append

   treeSearch :: FMList a -> PMonoid a
   treeSearch l = unFM l Point

Just like this monoid instance violates the monoid laws, the monad  
"ChoiceT m" violates corresponding laws of MonadPlus:

     mzero `mplus` return 42
   = Choice NoAnswer (Answer 42)
  /= Answer 42
   = return 42

     a `mplus` (b `mplus` c)
   = Choice a (Choice b c)
  /= Choice (Choice a b) c
   = (a `mplus` b) `mplus` c

So also w.r.t. laws there is no advantage in using a tree monad  
explicitly. Manipulating a non-deterministic computation w.r.t. these  
laws will change the order of computed results.

Mike Spivey gets by without breaking these laws by introducing an  
additional combinator 'wrap' to increase the depth of the search [2].  
However, this additional combinator prevents the use of (only)  
MonadPlus and whether all results of a non-deterministic computation  
are eventually enumerated depends on appropriate use of 'wrap'.

Cheers,
Sebastian


[1]: J. Voigtländer, Asymptotic Improvement of Computations over Free  
Monads
       http://wwwtcs.inf.tu-dresden.de/~voigt/mpc08.pdf

[2]: Michael Spivey, Algebras for Combinatorial Search
       http://spivey.oriel.ox.ac.uk/mike/search-jfp.pdf

-- 
Underestimating the novelty of the future is a time-honored tradition.
(D.G.)



-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 163 bytes
Desc: This is a digitally signed message part
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20090622/48f0daa3/PGP.bin