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