This Haskell library provides an implementation of the MonadPlus type class that represents the search space as a tree that can be used to define different search strategies.
This library is on Hackage. The easiest way to install it is to use cabal-install and simply type
$ cabal install tree-monad
in a shell.
To use this library import it as follows.
import Control.Monad
import Control.Monad.SearchTree
Now monadic actions can be represented as trees. For example, the monadic action
mzero `mplus` return 42
describes the following search tree.
Choice None (One 42)
Different search strategies can be implemented as traversals of this tree structure. For example, depth-first search looks as follows:
dfs :: SearchTree a -> [a]
dfs None = []
dfs (One x) = [x]
dfs (Choice l r) = dfs l ++ dfs r
Because SearchTree is a monad, we can use do-notation to build trees. For example, consider the following function that creates a full binary tree of given height.
full 1 = return 1
full (n+1) = do i <- full n
return (n-i) `mplus` return (i+1)
Here are some example calls of full with corresponding results:
*Main> full 1 :: SearchTree Int
One 1
*Main> full 2 :: SearchTree Int
Choice (One 0) (One 2)
*Main> full 3 :: SearchTree Int
Choice (Choice (One 2) (One 1)) (Choice (One 0) (One 3))
Although SearchTree is a full-fledged instance of MonadPlus, the implementation of the bind operation is not optimal. If you are interested in the details, then read Janis Voigtlaenders paper on Asymptotic Improvement of Computations over Free Monads. If not, simply note that nesting calls of >>= to the left is bad for performance.
There is a different type Search that is also an instance of Monad and MonadPlus and does not suffer from this performance penalty. The function
searchTree :: Search a -> SearchTree a
converts a value of type Search a into one of type SearchTree a. As an aside, the implementation of >>= for Search is also more efficient if it is not nested to the left because it does not involve pattern matching on tree constructors.
Incidentally, the function full nests >>= to the left, so we can use it to compare the performance of both monads. The following example is borrowed from Janis's paper:
zigzag :: SearchTree a -> a
zigzag = zig
where
zig (One x) = x
zig (Choice l _) = zag l
zag (One x) = x
zag (Choice _ r) = zig r
This function descends a single path of a search tree and yields the leaf at its end. Because of behaviour similar to the naive reverse function in terms of ++, the function zigzag . full has quadratic run time. Similar to the solution in case of reverse where functional lists can be used to achieve linear run time, the implementation of Search uses continuations and the function zigzag . searchTree . full has linear run time.
There is a blog post on parallel tree search that implements a parallel version of depth-first search based on search trees using explicit parallelism. The package parallel-tree-search on Hackage uses the library described here to implement the function parSearch shown there.
For bug reports or feedback contact .