CB      portable experimentalross@soi.city.ac.uk Safe-Inferred 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. KFor example, the following function computes discrete logarithms (base 2): # discreteLog :: Integer -> Integer * discreteLog n = search (\ k -> 2^k <= n)  O(log(n-l)). / 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)). 0 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 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 p3 returns the minimal non-negative pairs satisfying p, - listed in order of increasing x-coordinate. m and n3 refer to the smaller and larger dimensions of the $ rectangle containing the boundary.  For example, C search2 (\ 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,  E searchIntegerRange 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. portable experimentalross@soi.city.ac.uk Safe-Inferred O(log(h-l)). 2 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. HFor example, the following function determines the first index (if any) . at which a value occurs in an ordered array: 7 searchArray :: Ord a => a -> Array Int a -> Maybe Int  searchArray x array = do  let (lo, hi) = bounds array 1 k <- searchFromTo (\ i -> array!i >= x) lo hi  guard (array!k == x)  return k Like , but assuming l <= h && p h. portable experimentalross@soi.city.ac.uk Safe-Inferred 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)). @ 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)). A 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-Inferred  p x1 x2. decides if we should further investigate the  gap between x1 and x2. If so, it gives a new value x3 wrapped  in a . # may optionally use the predicate.  & generates the initial set of ranges.   m a b) calculates the predicate in the context m.    ((x1,x2),y) denotes that  pred x == y for all  x1 <= x <= x2 .  + comes in order [LEnd, REnd, LEnd, REnd ...], and 5 represents the ongoing state of the search results.  Two successive    LEnd x1 y1,  REnd x2 y1 represents a  claim that  pred x == y1 for all x such that x1 <= x <= x2 .  Like this:  is (x^2 > 20000) ?   LEnd REnd LEnd REnd  0 100 200 300  |_ False _| |_ True _| 2The generalized type for binary search functions. 1an initializer with the initial range specified. 1an initializer that searches for the full bound. a cutter for integral types. (The most generalized version of search.           Safe-Inferred Safe-Inferred          binary-search-0.1Numeric.Search.IntegerNumeric.Search.RangeNumeric.Search.Bounded!Numeric.Search.Combinator.MonadicNumeric.Search.Combinator.PureNumeric.Searchsearch searchFromsearchTosearch2 searchFromToCutterM InitializerM PredicateMRangeBookEndLEndREnd BinarySearchM initConstM initBoundedM cutIntegralM searchWithMbase Data.MaybeJustsearchIntegerRangesearchSafeRange search2Rect searchDownsearchUp