-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Binary and exponential searches -- -- These modules address the problem of finding the boundary of an -- upward-closed set of integers, using a combination of exponential and -- binary searches. Variants are provided for searching within bounded -- and unbounded intervals of both Integer and bounded integral -- types. @package binary-search @version 0.1 -- | Searching unbounded intervals of integers for the boundary of an -- upward-closed set, using a combination of exponential and binary -- search. module Numeric.Search.Integer -- | O(log(abs n)). Search the integers. -- -- If p is an upward-closed predicate, search p returns -- the least n satisfying p. If no such n -- exists, either because no integer satisfies p or all do, -- search p does not terminate. -- -- For example, the following function computes discrete logarithms (base -- 2): -- -- 
--   discreteLog :: Integer -> Integer
--   discreteLog n = search (\ k -> 2^k <= n)
--
search :: (Integer -> Bool) -> Integer -- | O(log(n-l)). Search the integers from a given lower bound. -- -- If p is an upward-closed predicate, searchFrom p l = -- search (\ i -> i >= l && p i). If no such -- n exists (because no integer satisfies p), -- searchFrom p does not terminate. searchFrom :: (Integer -> Bool) -> Integer -> Integer -- | O(log(h-n)). Search the integers up to a given upper bound. -- -- If p is an upward-closed predicate, searchTo p h == -- Just n if and only if n is the least number n -- <= h satisfying p. searchTo :: (Integer -> Bool) -> Integer -> Maybe Integer -- | O(m log(n\m))/. Two-dimensional search, using an algorithm due -- described in -- -- -- -- If p is closed upwards in each argument on non-negative -- integers, search2 p returns the minimal non-negative pairs -- satisfying p, listed in order of increasing x-coordinate. -- -- m and n refer to the smaller and larger dimensions of -- the rectangle containing the boundary. -- -- For example, -- -- 
--   search2 (\ x y -> x^2 + y^2 >= 25)  ==  [(0,5),(3,4),(4,3),(5,0)]
--
search2 :: (Integer -> Integer -> Bool) -> [(Integer, Integer)] -- | Binary search of a bounded interval of an integral type for the -- boundary of an upward-closed set, using a combination of exponential -- and binary search. module Numeric.Search.Range -- | O(log(h-l)). Search a bounded interval of some integral type. -- -- If p is an upward-closed predicate, searchFromTo p l h == -- Just n if and only if n is the least number l <= -- n <= h satisfying p. -- -- For example, the following function determines the first index (if -- any) at which a value occurs in an ordered array: -- -- 
--   searchArray :: Ord a => a -> Array Int a -> Maybe Int
--   searchArray x array = do
--     let (lo, hi) = bounds array
--     k <- searchFromTo (\ i -> array!i >= x) lo hi
--     guard (array!k == x)
--     return k
--
searchFromTo :: Integral a => (a -> Bool) -> a -> a -> Maybe a -- | Searching unbounded intervals within bounded integral types for the -- boundary of an upward-closed set, using a combination of exponential -- and binary search. module Numeric.Search.Bounded -- | O(log(abs n)). Search a bounded integral type. -- -- If p is an upward-closed predicate, search p returns -- Just n if and only if n is the least such satisfying -- p. search :: (Bounded a, Integral a) => (a -> Bool) -> Maybe a -- | O(log(abs n)). Search the part of a bounded integral type from -- a given point. -- -- If p is an upward-closed predicate, searchFrom p l -- returns Just n if and only if n is the least n -- >= l satisfying p. searchFrom :: (Bounded a, Integral a) => (a -> Bool) -> a -> Maybe a -- | O(log(abs n)). Search the part of a bounded integral type up to -- a given point. -- -- If p is an upward-closed predicate, searchTo p h -- returns Just n if and only if n is the least n -- <= h satisfying p. searchTo :: (Bounded a, Integral a) => (a -> Bool) -> a -> Maybe a -- | Monadic binary search combinators. module Numeric.Search.Combinator.Monadic -- | The generalized type for binary search functions. type BinarySearchM m a b = InitializerM m a b -> CutterM m a b -> PredicateM m a b -> m (Seq (Range a b)) -- | BookEnd comes in order [LEnd, REnd, LEnd, REnd ...], and -- represents the ongoing state of the search results. Two successive -- BookEnd LEnd x1 y1, REnd x2 y1 represents a -- claim that pred x == y1 for all x such that x1 -- <= x <= x2 . Like this: -- -- 
--   is (x^2 > 20000) ?
--   
--   LEnd    REnd  LEnd     REnd
--   0        100  200       300
--   |_ False _|    |_ True  _|
--
data BookEnd a b REnd :: !a -> !b -> BookEnd a b LEnd :: !a -> !b -> BookEnd a b -- | Range ((x1,x2),y) denotes that pred x == y -- for all x1 <= x <= x2 . type Range a b = ((a, a), b) -- | PredicateM m a b calculates the predicate in the -- context m. type PredicateM m a b = a -> m b -- | InitializerM generates the initial set of ranges. type InitializerM m a b = PredicateM m a b -> m (Seq (BookEnd a b)) -- | CutterM p x1 x2 decides if we should further -- investigate the gap between x1 and x2. If so, it -- gives a new value x3 wrapped in a Just. CutterM -- may optionally use the predicate. type CutterM m a b = PredicateM m a b -> a -> a -> m (Maybe a) -- | an initializer with the initial range specified. initConstM :: Monad m => a -> a -> InitializerM m a b -- | an initializer that searches for the full bound. initBoundedM :: (Monad m, Bounded a) => InitializerM m a b -- | a cutter for integral types. cutIntegralM :: (Monad m, Integral a) => CutterM m a b -- | The most generalized version of search. searchWithM :: (Functor m, Monad m, Eq b) => BinarySearchM m a b instance (Eq a, Eq b) => Eq (BookEnd a b) instance (Show a, Show b) => Show (BookEnd a b) -- | Pure counterpart for binary search. module Numeric.Search.Combinator.Pure -- | 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. --
  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 .
    3. --
module Numeric.Search -- | Range ((x1,x2),y) denotes that pred x == y -- for all x1 <= x <= x2 . type Range a b = ((a, a), b) -- | The generalized type for binary search functions. type BinarySearchM m a b = InitializerM m a b -> CutterM m a b -> PredicateM m a b -> m (Seq (Range a b)) -- | PredicateM m a b calculates the predicate in the -- context m. type PredicateM m a b = a -> m b -- | InitializerM generates the initial set of ranges. type InitializerM m a b = PredicateM m a b -> m (Seq (BookEnd a b)) -- | CutterM p x1 x2 decides if we should further -- investigate the gap between x1 and x2. If so, it -- gives a new value x3 wrapped in a Just. CutterM -- may optionally use the predicate. type CutterM m a b = PredicateM m a b -> a -> a -> m (Maybe a) -- | The most generalized version of search. searchWithM :: (Functor m, Monad m, Eq b) => BinarySearchM m a b