1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
cabal-version: 2.0
Name: binary-search
Version: 2.0.0
Build-Type: Simple
License: BSD3
license-file: LICENSE
Author: supercede <support@supercede.com>, Ross Paterson <ross@soi.city.ac.uk>, Takayuki Muranushi <muranushi@gmail.com>
Maintainer: supercede <support@supercede.com>
Category: Algorithms
Synopsis: Binary and exponential searches
Description:
__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.
.
<<https://travis-ci.org/nushio3/binary-search.svg?branch=master>>
library
default-language: Haskell2010
exposed-modules: Numeric.Search
Numeric.Search.Bounded
Numeric.Search.Integer
Numeric.Search.Range
Ghc-Options: -Wall
build-depends: base >=4.5 && < 5
, transformers
, containers >= 0.4
Test-Suite spec
default-language: Haskell2010
Type: exitcode-stdio-1.0
Hs-Source-Dirs: test
Ghc-Options: -Wall
Main-Is: Spec.hs
Other-Modules: PureSpec
Build-Depends: base >=4.7 && < 5
, binary-search
, hspec >= 1.3
, QuickCheck >= 2.5
Source-Repository head
Type: git
Location: https://github.com/riskbook/binary-search
|
