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 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 where

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.

Methods

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

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

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