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

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)

Methods

epsilon :: Search x (Search a b)

Monad (Search a)

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)

Methods

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

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

Applicative (Search a)

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)

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)

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)

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

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

Methods

epsilon :: Search a b

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

Instances

Ord x => Hilbert x Word16

Methods

epsilon :: Search x Word16

Ord x => Hilbert x Word8

Methods

epsilon :: Search x Word8

Ord x => Hilbert x Int16

Methods

epsilon :: Search x Int16

Ord x => Hilbert x Int8

Methods

epsilon :: Search x Int8

Ord x => Hilbert x Char

Methods

epsilon :: Search x Char

Ord x => Hilbert x Ordering

Methods

epsilon :: Search x Ordering

Ord x => Hilbert x All

Methods

epsilon :: Search x All

Ord x => Hilbert x Any

Methods

epsilon :: Search x Any

Ord x => Hilbert x Bool

Methods

epsilon :: Search x Bool

Hilbert x ()

Methods

epsilon :: Search x ()

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

Methods

epsilon :: Search x (Last a)

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

Methods

epsilon :: Search x (First a)

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

Methods

epsilon :: Search x (Maybe a)

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

Methods

epsilon :: Search x (ZipList a)

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

Methods

epsilon :: Search x [a]

Hilbert x a => Hilbert x (Sum a)

Methods

epsilon :: Search x (Sum a)

Hilbert x a => Hilbert x (Product a)

Methods

epsilon :: Search x (Product a)

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

Methods

epsilon :: Search x (Search a b)

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

Methods

epsilon :: Search x (Either a b)

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

Methods

epsilon :: Search x (a, b)

Hilbert x (Proxy * a)

Methods

epsilon :: Search x (Proxy * a)

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

Methods

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

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

Methods

epsilon :: Search x (Tagged * s a)

(Hilbert x a, Hilbert x b, Hilbert x c, Hilbert x d) => Hilbert x (a, b, c, d)

Methods

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

Methods

epsilon :: Search x (a, b, c, d, e)

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

search for an optimal answer using Hilbert's epsilon

>>> best (>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

newtype B

Bool with a lazier Ord as suggested here

Constructors

B Bool

Instances

Eq B

Methods

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

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

Ord B

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

Methods

readsPrec :: Int -> ReadS B

readList :: ReadS [B]

readPrec :: ReadPrec B

readListPrec :: ReadPrec [B]

Show B

Methods

showsPrec :: Int -> B -> ShowS

show :: B -> String

showList :: [B] -> ShowS

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

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

does there exist an element satisfying the predicate?

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