Numeric.Search.Combinator.Monadic

Monadic binary search combinators.

Documentation

type BinarySearchM m a b = InitializerM m a b -> CutterM m a b -> PredicateM m a b -> m (Seq (Range a b))

The generalized type for binary search functions.

data BookEnd a b

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  _|

Constructors

REnd !a !b

LEnd !a !b

Instances

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

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

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

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

type PredicateM m a b = a -> m b

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))

InitializerM generates the initial set of ranges.

type CutterM m a b = PredicateM m a b -> a -> a -> m (Maybe a)

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 b

an initializer with the initial range specified.

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

an initializer that searches for the full bound.

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

a cutter for integral types.

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

The most generalized version of search.