Control.Search

Lazily finds all (non-isomorphic) values of or below a given size that satisfy a predicate.

Is there a value of or below a given size that satisfies this predicate?

Find a counterexample to the given predicate, of or below a given size. If no counterexample is found, the number of performed executions of the predicate is returned.

Lazily finds all non-isomorphic (w.r.t. laziness) inputs to a predicate and returns them along with the result of the predicate.

Unsafe version of search. Non-deterministic for some predicates.

SmallCheck-like test driver. Tests a property with gradually increasing sizes until a conunterexample is found. For each size, it shows the worst case number of tests required (if the predicate is fully eager).

Stop testing after a given number of seconds

Options for parallel conjunction strategies. Only matters for predicates using the Cool data type instead of Bool.

Commutative conjunction

Commutative disjunction

Parallel implication

Negation

Concurrent booleans. Writing properties with the Cool data type often yields faster searches compared to Bool.

Provides better interoperability between Bool and Cool by overloading operators.

A sized functor is an applicative functor extended with a notion of cost/size of contained values. This is useful for any type of bounded recursion over infinite sets, most notably for various kind of enumerations.

The intention is that every sized functor definition models a (usually) infinite set (technically a bag) with a finite number of values of any given size. As long as every cyclic (recursive) definition has at least one application of pay, this invariant is guaranteed.

The module Control.Enumerable provides sized functor definitions for a lot of data types, such that the size of a value is the number of constructor applications it contains. It also allows deriving these functors for any user defined data type (using Template Haskell).

Takes a constructor of arity 1

Takes a constructor with arity 0 (a pure value)

An infix synonym for fmap.

The name of this operator is an allusion to Prelude.$. Note the similarities between their types:

 ($)  ::              (a -> b) ->   a ->   b
(<$>) :: Functor f => (a -> b) -> f a -> f b

Whereas Prelude.$ is function application, <$> is function application lifted over a Functor.

Examples

Convert from a Maybe Int to a Maybe String using show:

>>> show <$> NothingNothing

>>> show <$> Just 3Just "3"

Convert from an Either Int Int to an Either Int String using show:

>>> show <$> Left 17Left 17

>>> show <$> Right 17Right "17"

Double each element of a list:

>>> (*2) <$> [1,2,3][2,4,6]

Apply even to the second element of a pair:

>>> even <$> (2,2)(2,True)

A functor with application, providing operations to

• embed pure expressions (pure), and

• sequence computations and combine their results (<*> and liftA2).

A minimal complete definition must include implementations of pure and of either <*> or liftA2. If it defines both, then they must behave the same as their default definitions:

(<*>) = liftA2 id

liftA2 f x y = f Prelude.<$> x <*> y

Further, any definition must satisfy the following:

Identity

pure id <*> v = v

Composition

pure (.) <*> u <*> v <*> w = u <*> (v <*> w)

Homomorphism

pure f <*> pure x = pure (f x)

Interchange

u <*> pure y = pure ($ y) <*> u

The other methods have the following default definitions, which may be overridden with equivalent specialized implementations:

• u *> v = (id <$ u) <*> v

• u <* v = liftA2 const u v

As a consequence of these laws, the Functor instance for f will satisfy

• fmap f x = pure f <*> x

It may be useful to note that supposing

forall x y. p (q x y) = f x . g y

it follows from the above that

liftA2 p (liftA2 q u v) = liftA2 f u . liftA2 g v

If f is also a Monad, it should satisfy

• pure = return

• m1 <*> m2 = m1 >>= (\x1 -> m2 >>= (\x2 -> return (x1 x2)))

• (*>) = (>>)

(which implies that pure and <*> satisfy the applicative functor laws).

Replace all locations in the input with the same value. The default definition is fmap . const, but this may be overridden with a more efficient version.

Examples

Perform a computation with Maybe and replace the result with a constant value if it is Just:

>>> 'a' <$ Just 2Just 'a'>>> 'a' <$ NothingNothing

A variant of <*> with the types of the arguments reversed. It differs from flip (<*>) in that the effects are resolved in the order the arguments are presented.

Examples

>>> (<**>) (print 1) (id <$ print 2)12

>>> flip (<*>) (print 1) (id <$ print 2)21

>>> ZipList [4, 5, 6] <**> ZipList [(+1), (*2), (/3)]ZipList {getZipList = [5.0,10.0,2.0]}

A monoid on applicative functors.

If defined, some and many should be the least solutions of the equations:

• some v = (:) Prelude.<$> v <*> many v

• many v = some v <|> pure []

Examples

>>> Nothing <|> Just 42Just 42

>>> [1, 2] <|> [3, 4][1,2,3,4]

>>> empty <|> print (2^15)32768

Lift a function to actions. Equivalent to Functor's fmap but implemented using only Applicative's methods: liftA f a = pure f <*> a

As such this function may be used to implement a Functor instance from an Applicative one.

Examples

Using the Applicative instance for Lists:

>>> liftA (+1) [1, 2][2,3]

Or the Applicative instance for Maybe

>>> liftA (+1) (Just 3)Just 4

Lift a ternary function to actions.

The class Typeable allows a concrete representation of a type to be calculated.

Guarantees local sharing. All enumerations are shared inside each invokation of local, but may not be shared between them.

This is the primary way to access enumerations for usage. Guarantees global sharing of enumerations of the same type. Note that this means the enumerations are never garbage collected.

One or none.

It is useful for modelling any computation that is allowed to fail.

Examples

Using the Alternative instance of Control.Monad.Except, the following functions:

>>> import Control.Monad.Except

>>> canFail = throwError "it failed" :: Except String Int>>> final = return 42                :: Except String Int

Can be combined by allowing the first function to fail:

>>> runExcept $ canFail *> finalLeft "it failed"

>>> runExcept $ optional canFail *> finalRight 42

The sum of a collection of actions using (<|>), generalizing concat.

asum is just like msum, but generalised to Alternative.

Examples

Basic usage:

>>> asum [Just "Hello", Nothing, Just "World"]Just "Hello"

The Const functor.

Examples

>>> fmap (++ "World") (Const "Hello")Const "Hello"

Because we ignore the second type parameter to Const, the Applicative instance, which has (<*>) :: Monoid m => Const m (a -> b) -> Const m a -> Const m b essentially turns into Monoid m => m -> m -> m, which is (<>)

>>> Const [1, 2, 3] <*> Const [4, 5, 6]Const [1,2,3,4,5,6]

Lists, but with an Applicative functor based on zipping.

Examples

In contrast to the Applicative for GHC.List.List:

>>> (+) <$> [1, 2, 3] <*> [4, 5, 6][5,6,7,6,7,8,7,8,9]

The Applicative instance of ZipList applies the operation by pairing up the elements, analogous to zipWithN

>>> (+) <$> ZipList [1, 2, 3] <*> ZipList [4, 5, 6]ZipList {getZipList = [5,7,9]}

>>> (,,,) <$> ZipList [1, 2] <*> ZipList [3, 4] <*> ZipList [5, 6] <*> ZipList [7, 8]ZipList {getZipList = [(1,3,5,7),(2,4,6,8)]}

>>> ZipList [(+1), (^2), (/ 2)] <*> ZipList [5, 5, 5]ZipList {getZipList = [6.0,25.0,2.5]}

Work in progress

A class of infinite precision integral types. Integer is the principal class member.

Share/memoize a class member of type f a.

Used instead of enumerate when manually building instances.

Builds an enumeration of a data type from a list of constructors (see c0-c7)

Derive an instance of Enumberable with Template Haskell, with rules for some specific constructors

Builds a suitable definition for coEnumerate given an pattern matching function for a data type (see source for examples).