GitLab

Remove parallel strategies that have not proven useful.
API cleanup

Fair search strategies are now implemented so that they return lazy
lists instead of the old monadic lists.

Adding asymmetric strategies with the eval monad. These strategies
continue splitting only in the right/left subtrees whereas the
left/right subtrees are evaluated in sequence. This may
especially good for search trees that look like this
                           ?
                          / \
                         s   ?
                            / \
                           s   ?
                              / \
                             s   …
where s stands for nearly equally sized search trees.

Add bag strategies which do not use STM.

Implement a breadth-first strategy with gang-of-threads for use with
SetFunctions. When the result of the search contains a Choice,
it is not evaluated any further, but its evaluation is deferred lazily.

This splitAll strategy uses a common
parallele evaluation strategy with a parallel bfs search strategy.

Add two new search strategies based on the initial one and therefore
branching into two threads at each choice. Both do less
synchronisation and are therefore more scalable.

Add a fair strategy base on the bag-of-tasks approach which should
reduce the memory usage compared to the normal fair search.

This commit adds various new strategies using a bag-of-tasks
approach. The strategies resemble breadth-first search and
depth-first-search and are parametrized with strategies to
split the work-queues/stacks.

System.Cmd is deprecated now.

According to the Functor-Applicative-Monad proposal Monads now depends
on Applicative and MonadPlus depends on Alternative. This commit adds
instances for these for both SearchTree and UnsafeSearchTree.

http://www.haskell.org/haskellwiki/Functor-Applicative-Monad_Proposal

Now there are four strategies based on the eval monad (there was only
one before). One strategy splits the evaluation at every choice
(splitAll). At every choice the strategy creates a new spark, which
can be evaluated in parallel. The other strategies are used to reduce
the number of sparks that are created:
- splitLimitDepth n splits the evaluation for a depth of n
- splitAlternating n splits at every n-th choice
- splitPower splits at every node with a distance of 2^i from the root

The parallel search strategy conSearch is very similar to the
fairSearch but it is not fair as it limits the maximum number of
threads to be used.

The new parallel getOneValue implementation does not evaluate the whole
monadic list anymore, but stoppes after the first element instead. This
makes it possible for strategies to stop remaining running evaluations.

Bindings for a new search strategy.