úÎlxi00      !"#$%&'()*+,-./(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 == 0 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)]1&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.2Like , but assuming  l <= h && p h.312312(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 k4Like , but assuming  l <= h && p h.44(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.5Like , but assuming  l <= h && p h.675675Safe -3457FNV2The type of function that returns a value between (lo, hi) as long as one is available. lThe (possibly infinite) lists of candidates for lower and upper bounds from which the search may be started. The Range k lo k' hi# represents the search result that  pred x == k for  lo <= x <= hi. The  D type also holds the evidences for the lower and the upper boundary.The  datatype is similar to 8 , 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.In other words,  is a 9' with additional information why it is : or ;.<Evidence "He owns the gun" == Evidence "He was at the scene"True9Evidence "He loved her" == CounterEvidence "He loved her"False =  <1. We can use this combinator to look up for some  , since all  s are equal. =  <0. We can use this combinator to look up for any  , since all  s are equal.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.!Start binary search from between = and >.>Start binary search from between the given pair of boundaries.-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.,Lower boundary is 1, upper boundary is from [2, 4, 8, 16, ...].3Lower boundary is 0, search upper boundary is from [1, 2, 4, 8, ...].Lower boundary is [0.5, 0.25, 0.125, ...], upper boundary is from [1, 2, 4, 8, ...].Lower boundary is from [-2, -4, -8, -16, ...], upper boundary is -1.Lower boundary is from [-1, -2, -4, -8, ...], upper boundary is -0.Lower boundary is [-1, -2, -4, -8, ...], upper boundary is from [-0.5, -0.25, -0.125, ...].@Perform split forever, until we cannot find a mid-value because  hi-lo < 2G. This splitter assumes that the arguments are Integral, and uses the ? funtion.DNote that our dividing algorithm always find the mid value for any  hi-lo >= 2.pprove $ \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. Perform splitting until hi - lo <= eps.!pPerform split forever, until we cannot find a mid-value due to machine precision. This one uses `(/)` operator."Perform splitting until hi - lo <= eps.#DPerform search over pure predicates. The monadic version of this is $.$ Mother of all search variations.$E keeps track of the predicates found, so that it works well with the  type.%Look up for the first   with the given predicate.&Pick up the smallest a that satisfies  pred a == b.'Pick up the largest a that satisfies  pred a == b.(1Get the content of the evidence for the smallest a which satisfies pred a.)0Get the content of the evidence for the largest a which satisfies pred a.*8Get the content of the counterEvidence for the smallest a which does not satisfy pred a.+7Get the content of the counterEvidence for the largest a which does not satisfy pred a.(  !"#$%&'()*+,-./$  !"#$%&'()*+(/.-,   !"#$%&'()*+!   !"#$%&'()*+,-./@       !"#$%&'()*+,-./012343356/789:;9:<9:=/>?/@A/@B/CDEbinar_CZQzr4o8wPyKza2V0cdSfSNumeric.Search.IntegerNumeric.Search.RangeNumeric.Search.BoundedNumeric.Searchsearch searchFromsearchTosearch2 searchFromToSplitter SearchRangeRangeloKeyloValhiKeyhiValEvidenceCounterEvidenceevidencecounterEvidenceinitializeSearchMminToMaxfromTo exponentialpositiveExponentialnonNegativeExponentialpositiveFractionalExponentialnegativeExponentialnonPositiveExponentialnegativeFractionalExponential divForeverdivTill divideForever divideTillsearchM lookupRangessmallestlargestevidenceForSmallestevidenceForLargestcounterEvidenceForSmallestcounterEvidenceForLargest$fMonadEvidence$fApplicativeEvidence $fOrdEvidence $fEqEvidencebaseGHC.BaseJustsearchIntegerRangesearchSafeRange search2Rect searchDownsearchUp Data.EitherEitherghc-prim GHC.TypesBoolTrueFalseGHC.Err undefinedGHC.EnumminBoundmaxBoundGHC.Realdiv