Numeric.Search

This package provides combinators to construct many variants of binary search. Most generally, it provides the binary search over predicate of the form (Eq b, Monad m) => a -> m b . The other searches are derived as special cases of this function.

BinarySearch assumes two things;

1. b, the codomain of PredicateM belongs to type class Eq.
2. Each value of b form a convex set in the codomain space of the PredicateM. That is, if for certain pair (left, right) :: (a, a) satisfies pred left == val && pred right == val, then also pred x == val for all x such that left <= x <= right .

Evidence

data Evidence a b

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

Constructors

CounterExample a

Example 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

type Range b a = (b, (a, a))

(value, (lo,hi)) represents the finding that pred x == value for lo <= x <= hi. By using this type, we can readily lookup a list of Range .

class InitializesSearch a x

A type x is an instance of SearchInitializer a, if x can be used to set up the lower and upper inital values for binary search over values of type a. . initializeSearchM should generate a list of Range s, where each Range has different -- predicate.

Minimal complete definition

initializeSearchM

Instances

InitializesSearch a ([a], [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.

InitializesSearch a ([a], a)

Set the upper boundary explicitly and search for the lower boundary.

InitializesSearch a (a, [a])

Set the lower boundary explicitly and search for the upper boundary.

InitializesSearch a (a, a)

Set the lower and upper boundary explicitly.

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 :: (InitializesSearch a init, Eq b) => init -> Splitter a -> (a -> b) -> [Range b a]

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

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

Mother of all search variations.

searchM carefully keeps track of the latest predicate found, so that it works well with the Evidence class.

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 .