Safe Haskell | Safe-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))
- 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.