This package provides combinators to construct many variants of
binary search. Most generally, it provides the binary search over
predicate of the form
( . The other
searches are derived as special cases of this function.
Monad m) => a -> m b
BinarySearch assumes two things;
- type Range a b = ((a, a), b)
- type BinarySearchM m a b = InitializerM m a b -> CutterM m a b -> PredicateM m a b -> m (Seq (Range a b))
- type PredicateM m a b = a -> m b
- type InitializerM m a b = PredicateM m a b -> m (Seq (BookEnd a b))
- type CutterM m a b = PredicateM m a b -> a -> a -> m (Maybe a)
- searchWithM :: forall m a b. (Functor m, Monad m, Eq b) => BinarySearchM m a b
These are pure.
((x1,x2),y) denotes that
pred x == y for all
x1 <= x <= x2 .
These are monadic.
The generalized type for binary search functions.
InitializerM generates the initial set of ranges.
The most generalized version of search.