binary-search-0.1: Binary and exponential searches

Safe HaskellSafe-Inferred




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.


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

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



Monadic combinators

These are monadic.


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.


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

The most generalized version of search.