Safe Haskell  SafeInferred 

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.
Eq
b, Monad
m) => a > m b
BinarySearch
assumes two things;

b
, the codomain ofPredicateM
belongs to type classEq
.  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)
satisfiespred left == val && pred right == val
, then alsopred x == val
for allx
such thatleft <= x <= right
.
 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
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
.
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))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
Searchers
searchWithM :: forall m a b. (Functor m, Monad m, Eq b) => BinarySearchM m a bSource
The most generalized version of search.