| Safe Haskell | Safe-Inferred |
|---|
Numeric.Search.Combinator.Monadic
Description
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))
- data BookEnd a b
- type Range a b = ((a, 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)
- initConstM :: Monad m => a -> a -> InitializerM m a b
- initBoundedM :: (Monad m, Bounded a) => InitializerM m a b
- cutIntegralM :: (Monad m, Integral a) => CutterM m a b
- searchWithM :: forall m a b. (Functor m, Monad m, Eq b) => BinarySearchM m a b
Documentation
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.
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 _|
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
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.