Numeric.Search

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 .

Pure combinators

These are pure.

Types

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

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

Searchers

Combinators

Monadic combinators

These are monadic.

Types

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

The generalized type for binary search functions.

type PredicateM m a b = a -> m b

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

InitializerM generates the initial set of ranges.

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

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 b

The most generalized version of search.

Combinators