Data.Search

Documentation

newtype Search a b

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

optimum :: (b -> a) -> b

Instances

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)

Typeable (* -> * -> *) Search

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

Find the worst-scoring result of a search.

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

What is the best score obtained by the search?

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

What is the worst score obtained by the search?

cps :: Search a b -> Cont a b

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

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

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

Hilbert's epsilon

class Hilbert a b where

Hilbert's epsilon

Minimal complete definition

Nothing

Methods

epsilon :: Search a b

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) -> b

search for an optimal answer using Hilbert's epsilon

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

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

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

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

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

Boolean-valued search

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

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

does there exist an element satisfying the predicate?

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