[Haskell-cafe] ANNOUNCE fmlist
Sebastian Fischer
sebf at informatik.uni-kiel.de
Mon Jun 22 03:55:54 EDT 2009
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
More information about the Haskell-Cafe
mailing list