Safe Haskell | Safe |
---|---|
Language | Haskell98 |
This package provides combinators to construct many variants of
binary search. Most generally, it provides the binary search over
predicate of the form (
. The other
searches are derived as special cases of this function.Eq
b, Monad
m) => a -> m b
BinarySearch
assumes two things;
b
, the codomain ofPredicateM
belongs to type classEq
.- 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)
satisfiespred left == val && pred right == val
, then alsopred x == val
for allx
such thatleft <= x <= right
.
- data Evidence a b
- = CounterExample a
- | Example b
- type Range b a = (b, (a, a))
- class InitializesSearch a x
- splitForever :: Integral a => Splitter a
- splitTill :: Integral a => a -> Splitter a
- search :: (InitializesSearch a init, Eq b) => init -> Splitter a -> (a -> b) -> [Range b a]
- searchM :: forall a m b init. (Monad m, InitializesSearch a init, Eq b) => init -> Splitter a -> (a -> m b) -> m [Range b a]
- smallest :: Eq b => b -> [Range b a] -> Maybe a
- largest :: Eq b => b -> [Range b a] -> Maybe a
Evidence
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.
Search Range
class InitializesSearch a x 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.
InitializesSearch a ([a], [a]) Source | Set the lower and upper boundary from those available from the candidate lists.
From the pair of list, the |
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
splitForever :: Integral a => Splitter a Source
Perform split forever, until we cannot find a mid-value due to machine precision.
Search
search :: (InitializesSearch a init, Eq b) => init -> Splitter a -> (a -> b) -> [Range b a] Source
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] Source