binary-search-2.0.0: Binary and exponential searches

# binary-search-2.0.0: 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.

Modules

binary-search-2.0.0

- Numeric
  Submodules
  - Numeric.Search
    Submodules
    - Numeric.Search.Bounded
    - Numeric.Search.Integer
    - Numeric.Search.Range