-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Binary and exponential searches -- -- Introduction -- -- This package provides varieties of binary search functions. -- -- These search function can search for predicates of the type pred -- :: (Integral a, Eq b) => a -> b, or monadic predicates -- pred :: (Integral a, Eq b, Monad m) => a -> m b. The -- predicates must satisfy that the domain range for any codomain value -- is continuous; that is, ∀x≦y≦z. pred x == pred z ⇒ pred y == pred -- x . -- -- For example, we can 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. -- -- The package was created by Ross Paterson, and extended by Takayuki -- Muranushi, to be used together with SMT solvers. -- -- The Module Structure -- -- -- @package binary-search @version 0.9 -- | 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 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. data Evidence a b CounterExample :: a -> Evidence a b Example :: b -> Evidence a b -- | (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 . type Range b a = (b, (a, a)) -- | 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. class InitializesSearch a x initializeSearchM :: (InitializesSearch a x, Monad m, Eq b) => x -> (a -> m b) -> m [Range b a] -- | Set the lower and upper boundary explicitly. -- | Set the lower boundary explicitly and search for the upper boundary. -- | Set the upper boundary explicitly and search for the lower boundary. -- | 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. type Splitter a = a -> a -> Maybe a -- | Perform split forever, until we cannot find a mid-value due to machine -- precision. splitForever :: Integral a => Splitter a -- | Perform splitting until hi - lo <= eps . splitTill :: Integral a => a -> Splitter a -- | Mother of all search variations. -- -- searchM carefully keeps track of the latest predicate found, so -- that it works well with the Evidence class. searchM :: (Monad m, InitializesSearch a init, Eq b) => init -> Splitter a -> (a -> m b) -> m [Range b a] -- | Pick up the smallest a that satisfies pred a == b . smallest :: (Eq b) => b -> [Range b a] -> Maybe a -- | Pick up the largest a that satisfies pred a == b . largest :: (Eq b) => b -> [Range b a] -> Maybe a instance GHC.Base.Functor (Numeric.Search.Combinator.Monadic.Evidence a) instance (GHC.Read.Read a, GHC.Read.Read b) => GHC.Read.Read (Numeric.Search.Combinator.Monadic.Evidence a b) instance (GHC.Show.Show a, GHC.Show.Show b) => GHC.Show.Show (Numeric.Search.Combinator.Monadic.Evidence a b) instance GHC.Classes.Eq (Numeric.Search.Combinator.Monadic.Evidence b a) instance GHC.Classes.Ord (Numeric.Search.Combinator.Monadic.Evidence b a) instance GHC.Base.Applicative (Numeric.Search.Combinator.Monadic.Evidence e) instance GHC.Base.Monad (Numeric.Search.Combinator.Monadic.Evidence e) instance Numeric.Search.Combinator.Monadic.InitializesSearch a (a, a) instance Numeric.Search.Combinator.Monadic.InitializesSearch a (a, [a]) instance Numeric.Search.Combinator.Monadic.InitializesSearch a ([a], a) instance Numeric.Search.Combinator.Monadic.InitializesSearch a ([a], [a]) -- | Pure counterpart for binary search. module Numeric.Search.Combinator.Pure -- | 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. data Evidence a b CounterExample :: a -> Evidence a b Example :: b -> Evidence a b -- | (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 . type Range b a = (b, (a, a)) -- | 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. class InitializesSearch a x -- | Perform split forever, until we cannot find a mid-value due to machine -- precision. splitForever :: Integral a => Splitter a -- | Perform splitting until hi - lo <= eps . splitTill :: Integral a => a -> Splitter a -- | Perform search over pure predicates. The monadic version of this is -- searchM . search :: (InitializesSearch a init, Eq b) => init -> Splitter a -> (a -> b) -> [Range b a] -- | Pick up the smallest a that satisfies pred a == b . smallest :: (Eq b) => b -> [Range b a] -> Maybe a -- | Pick up the largest a that satisfies pred a == b . largest :: (Eq b) => b -> [Range b a] -> Maybe a -- | 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 -- | 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. data Evidence a b CounterExample :: a -> Evidence a b Example :: b -> Evidence a b -- | (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 . type Range b a = (b, (a, a)) -- | 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. class InitializesSearch a x -- | Perform split forever, until we cannot find a mid-value due to machine -- precision. splitForever :: Integral a => Splitter a -- | Perform splitting until hi - lo <= eps . splitTill :: Integral a => a -> Splitter a -- | Perform search over pure predicates. The monadic version of this is -- searchM . search :: (InitializesSearch a init, Eq b) => init -> Splitter a -> (a -> b) -> [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. searchM :: (Monad m, InitializesSearch a init, Eq b) => init -> Splitter a -> (a -> m b) -> m [Range b a] -- | Pick up the smallest a that satisfies pred a == b . smallest :: (Eq b) => b -> [Range b a] -> Maybe a -- | Pick up the largest a that satisfies pred a == b . largest :: (Eq b) => b -> [Range b a] -> Maybe a