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.