Module Control.Search.SearchTree.Generators

This library implements some operations to generate search trees for various data types.

The library also provides combinators to support the easy definition of search tree generators for user-defined data types. If a data type is defined by

data T a1 ... an = ... | C t1 ... tn | ....

then one can define a search tree generator for this type by

genT gena1 ... genan =
  ... ||| genCons<n> C gen_t1 ... gen_t1 ||| ...

where gen_ti denotes the search tree generator for type ti. For instance, a search tree generator for the type

data Tree a = Leaf a
            | Node [Tree a]

can be defined by

genTree gena =  genCons1 Leaf gena
            ||| genCons1 Node (genList (genTree gena))

Author: Michael Hanus

Version: January 2024

Summary of exported operations:

(|||) :: SearchTree a -> SearchTree a -> SearchTree a  Deterministic 
Constructs an alternative of two search trees.
genCons0 :: a -> SearchTree a  Deterministic 
Constructs a generator for a nullary constructor.
genCons1 :: (a -> b) -> SearchTree a -> SearchTree b  Deterministic 
Constructs a generator for a unary constructor where the generator for the argument type is provided.
genCons2 :: (a -> b -> c) -> SearchTree a -> SearchTree b -> SearchTree c  Deterministic 
Constructs a generator for a binary constructor where the generators for the argument types are provided.
genCons3 :: (a -> b -> c -> d) -> SearchTree a -> SearchTree b -> SearchTree c -> SearchTree d  Deterministic 
Constructs a generator for a ternary constructor where the generators for the argument types are provided.
genCons4 :: (a -> b -> c -> d -> e) -> SearchTree a -> SearchTree b -> SearchTree c -> SearchTree d -> SearchTree e  Deterministic 
Constructs a generator for a constructor of arity 4 where the generators for the argument types are provided.
genCons5 :: (a -> b -> c -> d -> e -> f) -> SearchTree a -> SearchTree b -> SearchTree c -> SearchTree d -> SearchTree e -> SearchTree f  Deterministic 
Constructs a generator for a constructor of arity 5 where the generators for the argument types are provided.
genNat :: SearchTree Int  Deterministic 
Generates a search tree for positive natural numbers:
genInt :: SearchTree Int  Deterministic 
Generates a search tree for integer values.
genFloat :: SearchTree Float  Deterministic 
Generates a search tree for Float values.
genBool :: SearchTree Bool  Deterministic 
Generates a search tree for Boolean values.
genChar :: SearchTree Char  Deterministic 
Generates a search tree for character values.
genList :: SearchTree a -> SearchTree [a]  Deterministic 
Generates a search tree for list values where the search tree for the elements is given as a parameter.
genMaybe :: SearchTree a -> SearchTree (Maybe a)  Deterministic 
Generates a search tree for Maybe values where the search tree for the possible element is given as a parameter.
genEither :: SearchTree a -> SearchTree b -> SearchTree (Either a b)  Deterministic 
Generates a search tree for Either values where the search tree for the possible elements is given as a parameter.
genUnit :: SearchTree ()  Deterministic 
Generates a search tree for the unit values.
genPair :: SearchTree a -> SearchTree b -> SearchTree (a,b)  Deterministic 
Generates a search tree for pair of values where the search tree generators for the components types are given as parameters.
genTriple :: SearchTree a -> SearchTree b -> SearchTree c -> SearchTree (a,b,c)  Deterministic 
Generates a search tree for triple of values where the search tree generators for the components types are given as parameters.
genTuple4 :: SearchTree a -> SearchTree b -> SearchTree c -> SearchTree d -> SearchTree (a,b,c,d)  Deterministic 
Generates a search tree for quadruple of values where the search tree generators for the components types are given as parameters.
genTuple5 :: SearchTree a -> SearchTree b -> SearchTree c -> SearchTree d -> SearchTree e -> SearchTree (a,b,c,d,e)  Deterministic 
Generates a search tree for 5-tuple of values where the search tree generators for the components types are given as parameters.
genOrdering :: SearchTree Ordering  Deterministic 
Generates a search tree for the Ordering values.

Exported operations:

(|||) :: SearchTree a -> SearchTree a -> SearchTree a  Deterministic 

Constructs an alternative of two search trees.

Further infos:
  • defined as right-associative infix operator with precedence 1
  • solution complete, i.e., able to compute all solutions

genCons0 :: a -> SearchTree a  Deterministic 

Constructs a generator for a nullary constructor.

Further infos:
  • solution complete, i.e., able to compute all solutions

genCons1 :: (a -> b) -> SearchTree a -> SearchTree b  Deterministic 

Constructs a generator for a unary constructor where the generator for the argument type is provided.

genCons2 :: (a -> b -> c) -> SearchTree a -> SearchTree b -> SearchTree c  Deterministic 

Constructs a generator for a binary constructor where the generators for the argument types are provided.

genCons3 :: (a -> b -> c -> d) -> SearchTree a -> SearchTree b -> SearchTree c -> SearchTree d  Deterministic 

Constructs a generator for a ternary constructor where the generators for the argument types are provided.

genCons4 :: (a -> b -> c -> d -> e) -> SearchTree a -> SearchTree b -> SearchTree c -> SearchTree d -> SearchTree e  Deterministic 

Constructs a generator for a constructor of arity 4 where the generators for the argument types are provided.

genCons5 :: (a -> b -> c -> d -> e -> f) -> SearchTree a -> SearchTree b -> SearchTree c -> SearchTree d -> SearchTree e -> SearchTree f  Deterministic 

Constructs a generator for a constructor of arity 5 where the generators for the argument types are provided.

genNat :: SearchTree Int  Deterministic 

Generates a search tree for positive natural numbers:

genInt :: SearchTree Int  Deterministic 

Generates a search tree for integer values.

genFloat :: SearchTree Float  Deterministic 

Generates a search tree for Float values.

genBool :: SearchTree Bool  Deterministic 

Generates a search tree for Boolean values.

Further infos:
  • solution complete, i.e., able to compute all solutions

genChar :: SearchTree Char  Deterministic 

Generates a search tree for character values. In order to obtain readable values, we only generate letters and digits.

genList :: SearchTree a -> SearchTree [a]  Deterministic 

Generates a search tree for list values where the search tree for the elements is given as a parameter.

genMaybe :: SearchTree a -> SearchTree (Maybe a)  Deterministic 

Generates a search tree for Maybe values where the search tree for the possible element is given as a parameter.

genEither :: SearchTree a -> SearchTree b -> SearchTree (Either a b)  Deterministic 

Generates a search tree for Either values where the search tree for the possible elements is given as a parameter.

genUnit :: SearchTree ()  Deterministic 

Generates a search tree for the unit values.

Further infos:
  • solution complete, i.e., able to compute all solutions

genPair :: SearchTree a -> SearchTree b -> SearchTree (a,b)  Deterministic 

Generates a search tree for pair of values where the search tree generators for the components types are given as parameters.

genTriple :: SearchTree a -> SearchTree b -> SearchTree c -> SearchTree (a,b,c)  Deterministic 

Generates a search tree for triple of values where the search tree generators for the components types are given as parameters.

genTuple4 :: SearchTree a -> SearchTree b -> SearchTree c -> SearchTree d -> SearchTree (a,b,c,d)  Deterministic 

Generates a search tree for quadruple of values where the search tree generators for the components types are given as parameters.

genTuple5 :: SearchTree a -> SearchTree b -> SearchTree c -> SearchTree d -> SearchTree e -> SearchTree (a,b,c,d,e)  Deterministic 

Generates a search tree for 5-tuple of values where the search tree generators for the components types are given as parameters.

genOrdering :: SearchTree Ordering  Deterministic 

Generates a search tree for the Ordering values.

Further infos:
  • solution complete, i.e., able to compute all solutions