Numeric.Search.Combinator.Pure

Pure counterpart for binary search.

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.

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

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

Splitters

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 .

Search

search :: Eq b => SearchRange a -> Splitter a -> (a -> b) -> [Range b a]

Perform search over pure predicates. The monadic version of this is searchM .

Postprocess

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 .