search-0.2: 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

 Source # Methodsdimap :: (a -> b) -> (c -> d) -> Search b c -> Search a d #lmap :: (a -> b) -> Search b c -> Search a c #rmap :: (b -> c) -> Search a b -> Search a c #(#.) :: Coercible * c b => (b -> c) -> Search a b -> Search a c #(.#) :: Coercible * b a => Search b c -> (a -> b) -> Search a c # (Ord x, Ord a, Hilbert x b) => Hilbert x (Search a b) Source # Methodsepsilon :: Search x (Search a b) Source # Monad (Search a) Source # Methods(>>=) :: Search a a -> (a -> Search a b) -> Search a b #(>>) :: Search a a -> Search a b -> Search a b #return :: a -> Search a a #fail :: String -> Search a a # Source # Methodsfmap :: (a -> b) -> Search a a -> Search a b #(<\$) :: a -> Search a b -> Search a a # Source # Methodspure :: a -> Search a a #(<*>) :: Search a (a -> b) -> Search a a -> Search a b #(*>) :: Search a a -> Search a b -> Search a b #(<*) :: Search a a -> Search a b -> Search a a # Ord a => Alt (Search a) Source # Methods() :: Search a a -> Search a a -> Search a a #some :: Applicative (Search a) => Search a a -> Search a [a] #many :: Applicative (Search a) => Search a a -> Search a [a] # Apply (Search a) Source # Methods(<.>) :: Search a (a -> b) -> Search a a -> Search a b #(.>) :: Search a a -> Search a b -> Search a b #(<.) :: Search a a -> Search a b -> Search a a # Bind (Search a) Source # Methods(>>-) :: Search a a -> (a -> Search a b) -> Search a b #join :: Search a (Search a a) -> Search a a #

pessimum :: Search (Down a) b -> (b -> a) -> b Source #

Find the worst-scoring result of a search.

optimalScore :: Search a b -> (b -> a) -> a Source #

What is the best score obtained by the search?

pessimalScore :: Search (Down a) b -> (b -> a) -> a Source #

What is the worst score obtained by the search?

cps :: Search a b -> Cont a b Source #

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 b Source #

pair :: Ord a => b -> b -> Search a b Source #

fromList :: Ord a => [b] -> Search a b Source #

# Hilbert's epsilon

class Hilbert a b where Source #

Methods

epsilon :: Search a b Source #

epsilon :: (GHilbert a (Rep b), Generic b) => Search a b Source #

Instances

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

best :: Hilbert a b => (b -> a) -> b Source #

search for an optimal answer using Hilbert's epsilon

>>> best (>4) :: Int8
5


worst :: Hilbert (Down a) b => (b -> a) -> b Source #

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

bestScore :: Hilbert a b => (b -> a) -> a Source #

worstScore :: Hilbert (Down a) b => (b -> a) -> a Source #

# Boolean-valued search

newtype B Source #

Bool with a lazier Ord as suggested here

Constructors

 B Bool

Instances

 Source # Methods(==) :: B -> B -> Bool #(/=) :: B -> B -> Bool # Source # Methodscompare :: B -> B -> Ordering #(<) :: B -> B -> Bool #(<=) :: B -> B -> Bool #(>) :: B -> B -> Bool #(>=) :: B -> B -> Bool #max :: B -> B -> B #min :: B -> B -> B # Source # MethodsreadList :: ReadS [B] # Source # MethodsshowsPrec :: Int -> B -> ShowS #show :: B -> String #showList :: [B] -> ShowS #

every :: forall b. Hilbert B b => (b -> Bool) -> Bool Source #

exists :: forall b. Hilbert B b => (b -> Bool) -> Bool Source #

does there exist an element satisfying the predicate?

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