search-0.1: Infinite search in finite time with Hilbert's epsilon

Data.Search

Synopsis

# Documentation

newtype Search a b Source

Given a test that is required to execute in finite time for _all_ inputs, even infinite ones, `Search` should productively yield an answer.

I currently also assume that comparison of scores can be done in finite time for all scores.

This rules out large score sets.

`Search Bool` can be used for predicate searches.

Constructors

 Search Fieldsoptimum :: (b -> a) -> b

Instances

 Typeable2 Search Profunctor Search (Ord x, Ord a, Hilbert x b) => Hilbert x (Search a b) Monad (Search a) Functor (Search a) Applicative (Search a) Ord a => Alt (Search a) Apply (Search a) Bind (Search a)

pessimum :: Search (Down a) b -> (b -> a) -> bSource

Find the worst-scoring result of a search.

optimalScore :: Search a b -> (b -> a) -> aSource

What is the best score obtained by the search?

pessimalScore :: Search (Down a) b -> (b -> a) -> aSource

What is the worst score obtained by the search?

cps :: Search a b -> Cont a bSource

`Search` is more powerful than `Cont`.

This provides a canonical monad homomorphism into `Cont`.

union :: Ord a => Search a b -> Search a b -> Search a bSource

pair :: Ord a => b -> b -> Search a bSource

fromList :: Ord a => [b] -> Search a bSource

# Hilbert's epsilon

class Hilbert a b whereSource

Methods

epsilon :: Search a bSource

Instances

 Ord x => Hilbert x Word16 Ord x => Hilbert x Word8 Ord x => Hilbert x Int16 Ord x => Hilbert x Int8 Ord x => Hilbert x Char Ord x => Hilbert x Ordering Ord x => Hilbert x All Ord x => Hilbert x Any Ord x => Hilbert x Bool Hilbert x () (Ord x, Hilbert x a) => Hilbert x (Last a) (Ord x, Hilbert x a) => Hilbert x (First a) (Ord x, Hilbert x a) => Hilbert x (Maybe a) (Ord x, Hilbert x a) => Hilbert x (ZipList a) (Ord x, Hilbert x a) => Hilbert x [a] Hilbert x a => Hilbert x (Sum a) Hilbert x a => Hilbert x (Product a) (Ord x, Ord a, Hilbert x b) => Hilbert x (Search a b) (Ord x, Hilbert x a, Hilbert x b) => Hilbert x (Either a b) (Hilbert x a, Hilbert x b) => Hilbert x (a, b) Hilbert x (Proxy * a) (Hilbert x a, Hilbert x b, Hilbert x c) => Hilbert x (a, b, c) Hilbert x a => Hilbert x (Tagged * s a) (Hilbert x a, Hilbert x b, Hilbert x c, Hilbert x d) => Hilbert x (a, b, c, d) (Hilbert x a, Hilbert x b, Hilbert x c, Hilbert x d, Hilbert x e) => Hilbert x (a, b, c, d, e)

best :: Hilbert a b => (b -> a) -> bSource

search for an optimal answer using Hilbert's epsilon

````>>> ````search (>4) :: Int8
```5
```

worst :: Hilbert (Down a) b => (b -> a) -> bSource

What is the worst scoring answer by Hilbert's epsilon?

bestScore :: Hilbert a b => (b -> a) -> aSource

worstScore :: Hilbert (Down a) b => (b -> a) -> aSource

# Boolean-valued search

every :: Hilbert Bool b => (b -> Bool) -> BoolSource

exists :: Hilbert Bool b => (b -> Bool) -> BoolSource

does there exist an element satisfying the predicate?

````>>> ````exists (>(maxBound::Int8))
```False
```