úÎMüKù     (c) Ross Paterson 2008 BSD-styleross@soi.city.ac.uk experimentalportableSafe 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.JFor example, the following function computes discrete logarithms (base 2): JdiscreteLog :: Integer -> Integer discreteLog n = search (\ k -> 2^k <= n) O(log(n-l))0. Search the integers from a given lower bound.If p! is an upward-closed predicate, searchFrom p l =  (\ i -> i >= l && p i). If no such n& exists (because no integer satisfies p),  searchFrom p does not terminate. O(log(h-n))1. Search the integers up to a given upper bound.If p is an upward-closed predicate, searchTo p h ==  n if and only if n is the least number n <= h satisfying p. O(m log(n/m))>. Two-dimensional search, using an algorithm due described inRichard 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 p3 returns the minimal non-negative pairs satisfying p., listed in order of increasing x-coordinate.m and nV refer to the smaller and larger dimensions of the rectangle containing the boundary. For example, Asearch2 (\ x y -> x^2 + y^2 >= 25) == [(0,5),(3,4),(4,3),(5,0)]&Search a bounded interval of integers.If p is an upward-closed predicate, CsearchIntegerRange p l h = 'search' (\ i -> i >= l && p i || i > h)Cost:  O(log(h-l)) calls to p.Like , but assuming  l <= h && p h.  (c) Ross Paterson 2008 BSD-styleross@soi.city.ac.uk experimentalportableSafe O(log(h-l))3. 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.uFor 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!Like , but assuming  l <= h && p h.!!(c) Ross Paterson 2008 BSD-styleross@soi.city.ac.uk experimentalportableSafe 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. O(log(abs n))A. 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. O(log(abs n))B. 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."Like , but assuming  l <= h && p h.#$"#$"Safe -3457FNV 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. .   should generate a list of   s, where each   has different -- predicate. (value, (lo,hi)) represents the finding that pred x == value for  lo <= x <= hi&. By using this type, we can readily % a list of   . The   datatype is similar to & , but differes in that all  , values are equal to each other, and all - values are also equal to each other. The  ` type is used to binary-searching for some predicate and meanwhile returning evidences for that.QPerform split forever, until we cannot find a mid-value due to machine precision.Perform splitting until hi - lo <= eps . Mother of all search variations.U carefully keeps track of the latest predicate found, so that it works well with the   class.Pick up the smallest a that satisfies  pred a == b .Pick up the largest a that satisfies  pred a == b .lSet 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.DSet the upper boundary explicitly and search for the lower boundary.DSet the lower boundary explicitly and search for the upper boundary.,Set the lower and upper boundary explicitly.        SafeDPerform search over pure predicates. The monadic version of this is  .   Safe   '       !"#$%$$&' () *+,binar_2apVFK5Z79w2KkaxYg65o0Numeric.Search.IntegerNumeric.Search.RangeNumeric.Search.Bounded!Numeric.Search.Combinator.MonadicNumeric.Search.Combinator.PureNumeric.Searchsearch searchFromsearchTosearch2 searchFromToSplitterInitializesSearchinitializeSearchMRangeEvidenceCounterExampleExample splitForever splitTillsearchMsmallestlargest$fInitializesSearcha(,)$fInitializesSearcha(,)0$fInitializesSearcha(,)1$fInitializesSearcha(,)2$fMonadEvidence$fApplicativeEvidence $fOrdEvidence $fEqEvidencebaseGHC.BaseJustsearchIntegerRangesearchSafeRange search2Rect searchDownsearchUpGHC.Listlookup Data.EitherEither