-- 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. c.f. -- Numeric.Search for the examples. -- -- These search function can search for pure and monadic predicates, of -- type: -- -- 
--   pred :: Eq b => a -> b
--   pred :: (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 2.0.0 -- | 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. --
-- -- Example 1. Find the approximate square root of 3. -- -- 
--   >>> largest  True  $ search positiveExponential divForever (\x -> x^2 < 3000000)
--   Just 1732
--   
--   >>> smallest False $ search positiveExponential divForever (\x -> x^2 < 3000000)
--   Just 1733
--   
--   >>> largest  True  $ search positiveExponential divideForever (\x -> x^2 < (3::Double))
--   Just 1.7320508075688772
--   
--   >>> largest  True  $ search positiveExponential (divideTill 0.125) (\x -> x^2 < (3::Double))
--   Just 1.625
--   
--   >>> smallest False $ search positiveExponential (divideTill 0.125) (\x -> x^2 < (3::Double))
--   Just 1.75
--
-- -- Pay attention to use the appropriate exponential search combinator to -- set up the initial search range. For example, the following code works -- as expected: -- -- 
--   >>> largest  True  $ search nonNegativeExponential divideForever (\x -> x^2 < (0.5::Double))
--   Just 0.7071067811865475
--
-- -- But this one does not terminate: -- -- 
--   > largest  True  $ search positiveExponential divideForever (x -> x^2 < (0.5::Double))
--   ... runs forever ...
--
-- -- Example 2. Find the range of integers whose quotinent 7 is -- equal to 6. -- -- This is an example of how we can search for discete and -- multi-valued predicate. -- -- 
--   >>> smallest 6 $ search (fromTo 0 100) divForever (\x -> x `div` 7)
--   Just 42
--   
--   >>> largest  6 $ search (fromTo 0 100) divForever (\x -> x `div` 7)
--   Just 48
--
-- -- Example 3. Find the minimum size of the container that can fit -- three bars of length 4, and find an actual way to fit them. -- -- We will solve this using a satisfiability modulo theory (SMT) solver. -- Since we need to evoke IO to call for the SMT solver, This is a -- usecase for a monadic binary search. -- -- 
--   >>> import Data.List (isPrefixOf)
--   
--   >>> :{
--   do
--     -- x fits within the container
--     let x ⊂ r = (0 .<= x &&& x .<= r-4)
--     -- x and y does not collide
--     let x ∅ y = (x+4 .<= y )
--     let contain3 :: Integer -> IO (Evidence () String)
--         contain3 r' = do
--           let r = fromInteger r' :: SInteger
--           ret <- show <$> sat (\x y z -> bAnd [x ⊂ r, y ⊂ r, z ⊂ r, x ∅ y, y ∅ z])
--           if "Satisfiable" `isPrefixOf` ret
--             then return $ Evidence ret
--             else return $ CounterEvidence ()
--     Just sz  <- smallest evidence <$> searchM positiveExponential divForever contain3
--     putStrLn $ "Size of the container: " ++ show sz
--     Just msg <- evidenceForSmallest <$> searchM positiveExponential divForever contain3
--     putStrLn msg
--   :}
--   Size of the container: 12
--   Satisfiable. Model:
--     s0 = 0 :: Integer
--     s1 = 4 :: Integer
--     s2 = 8 :: Integer
--
module Numeric.Search -- | The Evidence datatype is similar to Either , but -- differes in that all CounterEvidence values are equal to each -- other, and all Evidence values are also equal to each other. -- The Evidence type is used to binary-searching for some -- predicate and meanwhile returning evidences for that. -- -- In other words, Evidence is a Bool with additional -- information why it is True or False. -- -- 
--   >>> Evidence "He owns the gun" == Evidence "He was at the scene"
--   True
--   
--   >>> Evidence "He loved her" == CounterEvidence "He loved her"
--   False
--
data Evidence a b CounterEvidence :: a -> Evidence a b Evidence :: b -> Evidence a b -- | evidence = Evidence undefined. We can use this -- combinator to look up for some Evidence, since all -- Evidences are equal. evidence :: Evidence a b -- | counterEvidence = CounterEvidence undefined. We -- can use this combinator to look up for any CounterEvidence, -- since all CounterEvidences are equal. counterEvidence :: Evidence a b -- | The Range k lo k' hi represents the search result that -- pred x == k for lo <= x <= hi. The -- Range type also holds the evidences for the lower and the upper -- boundary. data Range b a Range :: b -> a -> b -> a -> Range b a [loKey] :: Range b a -> b [loVal] :: Range b a -> a [hiKey] :: Range b a -> b [hiVal] :: Range b a -> a -- | The (possibly infinite) lists of candidates for lower and upper bounds -- from which the search may be started. type SearchRange 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. initializeSearchM :: (Monad m, Eq b) => SearchRange a -> (a -> m b) -> m [Range b a] -- | Start binary search from between minBound and maxBound. minToMax :: Bounded a => SearchRange a -- | Start binary search from between the given pair of boundaries. fromTo :: a -> a -> SearchRange a -- | Exponentially search for lower boundary from [-1, -2, -4, -8, -- ...], upper boundary from [0, 1, 2, 4, 8, ...]. Move on -- to the binary search once the first (lo, hi) is found such -- that pred lo /= pred hi. exponential :: Num a => SearchRange a -- | Lower boundary is 1, upper boundary is from [2, 4, 8, 16, -- ...]. positiveExponential :: Num a => SearchRange a -- | Lower boundary is 0, search upper boundary is from [1, 2, 4, 8, -- ...]. nonNegativeExponential :: Num a => SearchRange a -- | Lower boundary is [0.5, 0.25, 0.125, ...], upper boundary is -- from [1, 2, 4, 8, ...]. positiveFractionalExponential :: Fractional a => SearchRange a -- | Lower boundary is from [-2, -4, -8, -16, ...], upper boundary -- is -1. negativeExponential :: Num a => SearchRange a -- | Lower boundary is from [-1, -2, -4, -8, ...], upper boundary -- is -0. nonPositiveExponential :: Num a => SearchRange a -- | Lower boundary is [-1, -2, -4, -8, ...], upper boundary is -- from [-0.5, -0.25, -0.125, ...]. negativeFractionalExponential :: Fractional a => SearchRange a -- | The type of function that returns a value between (lo, hi) as -- long as one is available. type Splitter a = a -> a -> Maybe a -- | Perform split forever, until we cannot find a mid-value because -- hi-lo < 2. This splitter assumes that the arguments are -- Integral, and uses the div funtion. -- -- Note that our dividing algorithm always find the mid value for any -- hi-lo >= 2. -- -- 
--   >>> prove $ \x y -> (y .>= x+2 &&& x+2 .> x) ==> let z = (x+1) `sDiv` 2 + y `sDiv` 2  in x .< z &&& z .< (y::SInt32)
--   Q.E.D.
--
divForever :: Integral a => Splitter a -- | Perform splitting until hi - lo <= eps. divTill :: Integral a => a -> Splitter a -- | Perform split forever, until we cannot find a mid-value due to machine -- precision. This one uses (/) operator. divideForever :: (Eq a, Fractional a) => Splitter a -- | Perform splitting until hi - lo <= eps. divideTill :: (Ord a, Fractional a) => a -> Splitter a -- | Perform search over pure predicates. The monadic version of this is -- searchM. search :: Eq b => SearchRange a -> Splitter a -> (a -> b) -> [Range b a] -- | Mother of all search variations. -- -- searchM keeps track of the predicates found, so that it works -- well with the Evidence type. searchM :: forall a m b. (Functor m, Monad m, Eq b) => SearchRange a -> Splitter a -> (a -> m b) -> m [Range b a] -- | Look up for the first Range with the given predicate. lookupRanges :: Eq b => b -> [Range b a] -> Maybe (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 -- | Get the content of the evidence for the smallest a which -- satisfies pred a. evidenceForSmallest :: [Range (Evidence b1 b2) a] -> Maybe b2 -- | Get the content of the evidence for the largest a which -- satisfies pred a. evidenceForLargest :: [Range (Evidence b1 b2) a] -> Maybe b2 -- | Get the content of the counterEvidence for the smallest a -- which does not satisfy pred a. counterEvidenceForSmallest :: [Range (Evidence b1 b2) a] -> Maybe b1 -- | Get the content of the counterEvidence for the largest a -- which does not satisfy pred a. counterEvidenceForLargest :: [Range (Evidence b1 b2) a] -> Maybe b1 instance GHC.Base.Functor (Numeric.Search.Evidence a) instance (GHC.Read.Read a, GHC.Read.Read b) => GHC.Read.Read (Numeric.Search.Evidence a b) instance (GHC.Show.Show a, GHC.Show.Show b) => GHC.Show.Show (Numeric.Search.Evidence a b) instance (GHC.Classes.Ord b, GHC.Classes.Ord a) => GHC.Classes.Ord (Numeric.Search.Range b a) instance (GHC.Classes.Eq b, GHC.Classes.Eq a) => GHC.Classes.Eq (Numeric.Search.Range b a) instance (GHC.Read.Read b, GHC.Read.Read a) => GHC.Read.Read (Numeric.Search.Range b a) instance (GHC.Show.Show b, GHC.Show.Show a) => GHC.Show.Show (Numeric.Search.Range b a) instance GHC.Classes.Eq (Numeric.Search.Evidence b a) instance GHC.Classes.Ord (Numeric.Search.Evidence b a) instance GHC.Base.Applicative (Numeric.Search.Evidence e) instance GHC.Base.Monad (Numeric.Search.Evidence e) -- | 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