binary-search-0.1: Binary and exponential searches

Safe HaskellSafe-Inferred



Monadic binary search combinators.



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.

data BookEnd a b Source

BookEnd comes in order [LEnd, REnd, LEnd, REnd ...], and represents the ongoing state of the search results. Two successive BookEnd LEnd x1 y1, REnd x2 y1 represents a claim that pred x == y1 for all x such that x1 <= x <= x2 . Like this:

 is (x^2 > 20000) ?

 LEnd    REnd  LEnd     REnd
 0        100  200       300
 |_ False _|    |_ True  _|


REnd !a !b 
LEnd !a !b 


(Eq a, Eq b) => Eq (BookEnd a b) 
(Show a, Show b) => Show (BookEnd a b) 

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

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

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.

initConstM :: Monad m => a -> a -> InitializerM m a bSource

an initializer with the initial range specified.

initBoundedM :: (Monad m, Bounded a) => InitializerM m a bSource

an initializer that searches for the full bound.

cutIntegralM :: (Monad m, Integral a) => CutterM m a bSource

a cutter for integral types.

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

The most generalized version of search.