Copyright	(c) Ross Paterson 2008
License	BSD-style
Maintainer	ross@soi.city.ac.uk
Stability	experimental
Portability	portable
Safe Haskell	Safe-Inferred
Language	Haskell2010

Numeric.Search.Bounded

Description

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

Synopsis

search :: (Bounded a, Integral a) => (a -> Bool) -> Maybe a
searchFrom :: (Bounded a, Integral a) => (a -> Bool) -> a -> Maybe a
searchTo :: (Bounded a, Integral a) => (a -> Bool) -> a -> Maybe a

Documentation

search :: (Bounded a, Integral a) => (a -> Bool) -> Maybe a Source #

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.

searchFrom :: (Bounded a, Integral a) => (a -> Bool) -> a -> Maybe a Source #

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.

searchTo :: (Bounded a, Integral a) => (a -> Bool) -> a -> Maybe a Source #

O(log(abs n)). 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.