Safe Haskell | None |
---|---|
Language | Haskell2010 |
Simple Generics
-based arbitrary
generators.
Here is an example. Define your type.
data Tree a = Leaf a | Node (Tree a) (Tree a) deriving Generic
Pick an arbitrary
implementation.
instance Arbitrary a => Arbitrary (Tree a) where arbitrary =genericArbitrary
(weights
(9%
8%
()))
arbitrary ::
picks a Gen
(Tree a)Leaf
with probability 9/17, or a
Node
with probability 8/17, and recursively fills their fields with
arbitrary
.
Distribution of constructors
The distribution of constructors can be specified using weights
applied to
a special list of weights in the same order as the data type definition.
This assigns to each constructor a probability proportional to its weight;
in other words, p_C = weight_C / sumOfWeights
.
The list of weights is built up with the (
operator as a cons, and using
the unit %
)()
as the empty list, in the order corresponding to the data type
definition.
For Tree
, genericArbitrary
produces code equivalent to the following:
genericArbitrary
:: Arbitrary a =>Weights
(Tree a) -> Gen (Tree a)genericArbitrary
(weighted
(x%
y%
())) = frequency [ (x, Leaf <$> arbitrary) , (y, Node <$> arbitrary <*> arbitrary) ]
The weights actually have type
(just a newtype
around W
"ConstructorName"Int
), so that you can annotate a weight with its corresponding
constructor, and it will be checked that you got the order right.
This will type-check.
weighted
((x ::W
"Leaf")%
(y ::W
"Node")%
()) ::Weights
(Tree a)weighted
(x%
(y ::W
"Node")%
()) ::Weights
(Tree a)
This will not: the first requires an order of constructors different from
the definition of the Tree
type; the second doesn't have the right number
of weights.
weighted
((x ::W
"Node")%
y%
()) ::Weights
(Tree a)weighted
(x%
y%
z%
()) ::Weights
(Tree a)
Uniform distribution
You can specify the uniform distribution with uniform
.
For Tree
,
produces code equivalent to the
following:genericArbitrary
uniform
genericArbitrary
uniform
:: Arbitrary a => Gen (Tree a)genericArbitrary
uniform
= oneof [ Leaf <$> arbitrary -- Uses Arbitrary a , Node <$> arbitrary <*> arbitrary -- Uses Arbitrary (Tree a) ]
Note that for many types, a uniform distribution tends to produce big
values. For instance for Tree a
, generated values are finite but the
average number of Leaf
and Node
constructors is infinite.
Ensuring termination
As was just mentioned, one must be careful with recursive types to avoid producing extremely large values.
The alternative genericArbitrary'
implements a simple strategy to keep
values at reasonable sizes: the size parameter of Gen
is divided among the
fields of the chosen constructor. When it reaches zero, the generator
selects a finite term whenever it can find any of the given type. This
generally ensures that the number of constructors remains close to the
initial size parameter passed to Gen
.
A natural number n
determines the maximum depth of terms that can be
used to end recursion.
It is encoded using
and Z
:: Z
.S
:: n -> S
n
genericArbitrary'
n (weights
(...))
With n =
, the generator looks for a simple nullary constructor. If none
exist at the current type, as is the case for our Z
Tree
type, it carries on
as in genericArbitrary
.
genericArbitrary'
Z
:: Arbitrary a =>Weights
(Tree a) -> Gen (Tree a)genericArbitrary'
Z
(weights
(x%
y%
())) = frequency [ (x, Leaf <$> arbitrary) , (y, scale (`div` 2) $ Node <$> arbitrary <*> arbitrary) -- 2 because Node is 2-ary. ]
Here is another example with nullary constructors:
data Tree' = Leaf1 | Leaf2 | Node3 Tree' Tree' Tree' deriving Generic instance Arbitrary Tree' where arbitrary =genericArbitrary'
Z
(weights
(1%
2%
3%
()))
Here,
is equivalent to:genericArbitrary'
Z
genericArbitrary'
Z
::Weights
Tree' -> Gen Tree'genericArbitrary'
Z
(weights
(x%
y%
z%
())) = sized $ n -> if n == 0 then -- If the size parameter is zero, the non-nullary alternative is discarded. frequency $ [ (x, return Leaf1) , (y, return Leaf2) ] else frequency $ [ (x, return Leaf1) , (y, return Leaf2) , (z, resize (n `div` 3) node) -- 3 because Node3 is 3-ary ] where node = Node3 <$> arbitrary <*> arbitrary <*> arbitrary
To increase the chances of termination when no nullary constructor is directly
available, such as in Tree
, we can pass a larger depth n
. The effectiveness
of this parameter depends on the concrete type the generator is used for.
For instance, if we want to generate a value of type Tree ()
, there is a
value of depth 1 (represented by
) that we can use to end
recursion: S
Z
Leaf ()
.
genericArbitrary'
(S
Z
) ::Weights
(Tree ()) -> Gen (Tree ())genericArbitrary'
(S
Z
) (weights
(x%
y%
())) = sized $ n -> if n == 0 then return (Leaf ()) else frequency [ (x, Leaf <$> arbitrary) , (y, scale (`div` 2) $ Node <$> arbitrary <*> arbitrary) ]
Because the argument of Tree
must be inspected in order to discover
values of type Tree ()
, we incur some extra constraints if we want
polymorphism.
UndecidableInstances
is also required.
instance (Arbitrary a, Generic a,ListBaseCases
Z
(Rep a)) => Arbitrary (Tree a) where arbitrary =genericArbitrary'
(S
Z
) (weights
(1%
2%
()))
A synonym is provided for brevity.
instance (Arbitrary a,BaseCases'
Z a) => Arbitrary (Tree a) where arbitrary =genericArbitrary'
(S
Z
) (weights
(1%
2%
()))
- genericArbitrary :: forall a. (Generic a, GA Unsized (Rep a)) => Weights a -> Gen a
- genericArbitrary' :: forall n a. (Generic a, GA (Sized n) (Rep a)) => n -> Weights a -> Gen a
- data Weights a
- data W c
- weights :: (Weights_ (Rep a), Int, ()) -> Weights a
- (%) :: WeightBuilder a => W (First a) -> Prec a r -> (a, Int, r)
- uniform :: UniformWeight (Weights_ (Rep a)) => Weights a
- data Z = Z
- data S n = S n
- type BaseCases' n a = (Generic a, ListBaseCases n (Rep a))
- class BaseCases n f
- class ListBaseCases n f
Arbitrary implementations
genericArbitrary :: forall a. (Generic a, GA Unsized (Rep a)) => Weights a -> Gen a Source #
Pick a constructor with a given distribution, and fill its fields recursively.
Like genericArbitrary'
, with bounded size to ensure termination for
recursive types.
Specifying finite distributions
Trees of weights assigned to constructors of type a
,
rescaled to obtain a probability distribution.
Two ways of constructing them.
weights
(x1%
x2%
...%
xn%
()) ::Weights
auniform
::Weights
a
Using weights
, there must be exactly as many weights as
there are constructors.
uniform
is equivalent to
(automatically fills out the right number of 1s).weights
(1 %
... %
1 %
())
weights :: (Weights_ (Rep a), Int, ()) -> Weights a Source #
A smart constructor to specify a custom distribution.
(%) :: WeightBuilder a => W (First a) -> Prec a r -> (a, Int, r) Source #
A binary constructor for building up trees of weights.
Type-level natural numbers
Generic classes for finite values
type BaseCases' n a = (Generic a, ListBaseCases n (Rep a)) Source #
For convenience.
class ListBaseCases n f Source #
A ListBaseCases n (
constraint basically provides the list of
values of type Rep
a)a
with depth at most n
.
ListBaseCases n U1 Source # | |
(ListBaseCases n f, ListBaseCases n g) => ListBaseCases n ((:*:) f g) Source # | |
(ListBaseCases n f, ListBaseCases n g) => ListBaseCases n ((:+:) f g) Source # | |
ListBaseCases Z (K1 i c) Source # | |
ListBaseCases n f => ListBaseCases n (M1 i c f) Source # | |
(Generic c, ListBaseCases n (Rep c)) => ListBaseCases (S n) (K1 i c) Source # | |