Copyright | (c) Ross Paterson 2008 |
---|---|

License | BSD-style |

Maintainer | ross@soi.city.ac.uk |

Stability | experimental |

Portability | portable |

Safe Haskell | Safe |

Language | Haskell98 |

Searching unbounded intervals of integers for the boundary of an upward-closed set, using a combination of exponential and binary search.

# One-dimensional searches

search :: (Integer -> Bool) -> Integer Source

*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)

searchFrom :: (Integer -> Bool) -> Integer -> Integer Source

*O(log(n-l))*.
Search the integers from a given lower bound.

If `p`

is an upward-closed predicate,
`searchFrom p l = `

.
If no such `search`

(\ i -> i >= l && p i)`n`

exists (because no integer satisfies `p`

),
`searchFrom p`

does not terminate.

searchTo :: (Integer -> Bool) -> Integer -> Maybe Integer Source

*O(log(h-n))*.
Search the integers up to a given upper bound.

If `p`

is an upward-closed predicate, `searchTo p h == `

if and only if `Just`

n`n`

is the least number `n <= h`

satisfying `p`

.

# Two-dimensional searches

search2 :: (Integer -> Integer -> Bool) -> [(Integer, Integer)] Source

*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)]