-- 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
--   
--   
--   
- Numeric.Search provides the generic search combinator, to
--   search for pure and monadic predicates.
--   
- Numeric.Search.Bounded , Numeric.Search.Integer ,
--   Numeric.Search.Range provides the various specialized
--   searchers, which means less number of function arguments, and easier
--   to use.
--   
--   
@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;
--   
--   
--   
- b, the codomain of PredicateM belongs to type
--   class Eq.
--   
- 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.
--   
--   
--   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.Internal.Base.Applicative (Numeric.Search.Evidence e)
instance GHC.Classes.Eq (Numeric.Search.Evidence b a)
instance (GHC.Classes.Eq b, GHC.Classes.Eq a) => GHC.Classes.Eq (Numeric.Search.Range b a)
instance GHC.Internal.Base.Functor (Numeric.Search.Evidence a)
instance GHC.Internal.Base.Monad (Numeric.Search.Evidence e)
instance GHC.Classes.Ord (Numeric.Search.Evidence b a)
instance (GHC.Classes.Ord b, GHC.Classes.Ord a) => GHC.Classes.Ord (Numeric.Search.Range b a)
instance (GHC.Internal.Read.Read a, GHC.Internal.Read.Read b) => GHC.Internal.Read.Read (Numeric.Search.Evidence a b)
instance (GHC.Internal.Read.Read b, GHC.Internal.Read.Read a) => GHC.Internal.Read.Read (Numeric.Search.Range b a)
instance (GHC.Internal.Show.Show a, GHC.Internal.Show.Show b) => GHC.Internal.Show.Show (Numeric.Search.Evidence a b)
instance (GHC.Internal.Show.Show b, GHC.Internal.Show.Show a) => GHC.Internal.Show.Show (Numeric.Search.Range b a)

-- | 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
--   
--   
--   
- Richard Bird, Saddleback search: a lesson in algorithm
--   design, in Mathematics of Program Construction 2006,
--   Springer LNCS vol. 4014, pp82-89.
--   
--   
--   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
