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

Safe HaskellNone
LanguageHaskell98

Data.Search

Contents

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 

Fields

Instances

Profunctor Search Source # 

Methods

dimap :: (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 # 

Methods

epsilon :: 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 #

Functor (Search a) Source # 

Methods

fmap :: (a -> b) -> Search a a -> Search a b #

(<$) :: a -> Search a b -> Search a a #

Applicative (Search a) Source # 

Methods

pure :: 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 # 
Ord x => Hilbert x Word8 Source # 
Ord x => Hilbert x Int16 Source # 
Ord x => Hilbert x Int8 Source # 

Methods

epsilon :: Search x Int8 Source #

Ord x => Hilbert x Char Source # 

Methods

epsilon :: Search x Char Source #

Ord x => Hilbert x Ordering Source # 
Ord x => Hilbert x All Source # 

Methods

epsilon :: Search x All Source #

Ord x => Hilbert x Any Source # 

Methods

epsilon :: Search x Any Source #

Ord x => Hilbert x Bool Source # 

Methods

epsilon :: Search x Bool Source #

Hilbert x () Source # 

Methods

epsilon :: Search x () Source #

(Ord x, Hilbert x a) => Hilbert x (Last a) Source # 

Methods

epsilon :: Search x (Last a) Source #

(Ord x, Hilbert x a) => Hilbert x (First a) Source # 

Methods

epsilon :: Search x (First a) Source #

(Ord x, Hilbert x a) => Hilbert x (Maybe a) Source # 

Methods

epsilon :: Search x (Maybe a) Source #

(Ord x, Hilbert x a) => Hilbert x (ZipList a) Source # 

Methods

epsilon :: Search x (ZipList a) Source #

(Ord x, Hilbert x a) => Hilbert x [a] Source # 

Methods

epsilon :: Search x [a] Source #

Hilbert x a => Hilbert x (Sum a) Source # 

Methods

epsilon :: Search x (Sum a) Source #

Hilbert x a => Hilbert x (Product a) Source # 

Methods

epsilon :: Search x (Product a) Source #

(Ord x, Ord a, Hilbert x b) => Hilbert x (Search a b) Source # 

Methods

epsilon :: Search x (Search a b) Source #

(Ord x, Hilbert x a, Hilbert x b) => Hilbert x (Either a b) Source # 

Methods

epsilon :: Search x (Either a b) Source #

(Hilbert x a, Hilbert x b) => Hilbert x (a, b) Source # 

Methods

epsilon :: Search x (a, b) Source #

Hilbert x (Proxy * a) Source # 

Methods

epsilon :: Search x (Proxy * a) Source #

(Hilbert x a, Hilbert x b, Hilbert x c) => Hilbert x (a, b, c) Source # 

Methods

epsilon :: Search x (a, b, c) Source #

Hilbert x a => Hilbert x (Tagged * s a) Source # 

Methods

epsilon :: 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 # 

Methods

epsilon :: 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 # 

Methods

epsilon :: 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

Eq B Source # 

Methods

(==) :: B -> B -> Bool #

(/=) :: B -> B -> Bool #

Ord B Source # 

Methods

compare :: B -> B -> Ordering #

(<) :: B -> B -> Bool #

(<=) :: B -> B -> Bool #

(>) :: B -> B -> Bool #

(>=) :: B -> B -> Bool #

max :: B -> B -> B #

min :: B -> B -> B #

Read B Source # 
Show B Source # 

Methods

showsPrec :: 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