Safe Haskell	Safe
Language	Haskell98

Numeric.Search.Combinator.Monadic

Contents

Description

Monadic binary search combinators.

Synopsis

Evidence

data Evidence a b Source

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) Source
Functor (Evidence a) Source
Applicative (Evidence e) Source
Eq (Evidence b a) Source
Ord (Evidence b a) Source
(Read a, Read b) => Read (Evidence a b) Source
(Show a, Show b) => Show (Evidence a b) Source

Search range

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

(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 Source

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] Source

Instances

InitializesSearch a ([a], [a]) Source	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) Source	Set the upper boundary explicitly and search for the lower boundary.
InitializesSearch a (a, [a]) Source	Set the lower boundary explicitly and search for the upper boundary.
InitializesSearch a (a, a) Source	Set the lower and upper boundary explicitly.

Splitters

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

splitForever :: Integral a => Splitter a Source

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

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

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] Source

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 Source

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

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

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