binary-search-0.1: Binary and exponential searches

Description

Synopsis

# 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.

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

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