Numeric.Search.Combinator.Monadic

Monadic binary search combinators.

Evidence

data Evidence a b

The Evidence datatype is similar to Either , but differes in that all CounterEvidence values are equal to each other, and all Evidence values are also equal to each other. The Evidence type is used to binary-searching for some predicate and meanwhile returning evidences for that.

In other words, Evidence is a Bool with additional information why it is True or False.

>>> Evidence "He owns the gun" == Evidence "He was at the scene"
True
>>> Evidence "He loved her" == CounterEvidence "He loved her"
False

Constructors

CounterEvidence a

Evidence b

Instances

Monad (Evidence e)

Functor (Evidence a)

Applicative (Evidence e)

Eq (Evidence b a)

Ord (Evidence b a)

(Read a, Read b) => Read (Evidence a b)

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

Search range

data Range b a

The Range k lo k' hi represents the search result that pred x == k for lo <= x <= hi. The Range type also holds the evidences for the lower and the upper boundary.

Constructors

Range

Fields

loKey :: b

loVal :: a

hiKey :: b

hiVal :: a

type SearchRange a = ([a], [a])

The lists of candidate for lower and upper bounds from which the search may be started.

initializeSearchM :: (Monad m, Eq b) => SearchRange a -> (a -> m b) -> m [Range b a]

Set the lower and upper boundary from those available from the candidate lists. From the pair of list, the initializeSearchM tries to find the first (lo, hi) such that pred lo /= pred hi, by the breadth-first search.

minToMax :: Bounded a => SearchRange a

Search between minBound and maxBound .

exponential :: Num a => SearchRange a

positiveExponential :: Num a => SearchRange a

nonNegativeExponential :: Num a => SearchRange a

negativeExponential :: Num a => SearchRange a

nonPositiveExponential :: Num a => SearchRange a

Splitters

type Splitter a = a -> a -> Maybe a

splitForever :: Integral a => Splitter a

Perform split forever, until we cannot find a mid-value due to machine precision.

splitTill :: Integral a => a -> Splitter a

Perform splitting until hi - lo <= eps .

Searching

searchM :: forall a m b init. (Monad m, Eq b) => SearchRange a -> Splitter a -> (a -> m b) -> m [Range b a]

Mother of all search variations.

searchM keeps track of the predicates found, so that it works well with the Evidence type.

Postprocess

lookupRanges :: Eq b => b -> [Range b a] -> Maybe (Range b a)

smallest :: Eq b => b -> [Range b a] -> Maybe a

Pick up the smallest a that satisfies pred a == b .

largest :: Eq b => b -> [Range b a] -> Maybe a

Pick up the largest a that satisfies pred a == b .