binary-search-0.1: Binary and exponential searches

Numeric.Search

Description

This package provides combinators to construct many variants of binary search. Most generally, it provides the binary search over predicate of the form `(Eq b, Monad m) => a -> m b` . The other searches are derived as special cases of this function.

`BinarySearch` assumes two things;

1. `b`, the codomain of `PredicateM` belongs to type class `Eq`.
2. Each value of `b` form a convex set in the codomain space of the PredicateM. That is, if for certain pair `(left, right) :: (a, a)` satisfies `pred left == val && pred right == val`, then also ```pred x == val``` for all `x` such that `left <= x <= right` .

Synopsis

# Pure combinators

These are pure.

## Types

type Range a b = ((a, a), b)Source

`Range` `((x1,x2),y)` denotes that `pred x == y` for all `x1 <= x <= x2` .

## Types

type BinarySearchM m a b = InitializerM m a b -> CutterM m a b -> PredicateM m a b -> m (Seq (Range a b))Source

The generalized type for binary search functions.

type PredicateM m a b = a -> m bSource

`PredicateM` `m a b` calculates the predicate in the context `m`.

type InitializerM m a b = PredicateM m a b -> m (Seq (BookEnd a b))Source

`InitializerM` generates the initial set of ranges.

type CutterM m a b = PredicateM m a b -> a -> a -> m (Maybe a)Source

`CutterM` `p x1 x2` decides if we should further investigate the gap between `x1` and `x2`. If so, it gives a new value `x3` wrapped in a `Just`. `CutterM` may optionally use the predicate.

## Searchers

searchWithM :: forall m a b. (Functor m, Monad m, Eq b) => BinarySearchM m a bSource

The most generalized version of search.