Erlang Central

Recursive Genereators

Recursive Generators

Assume you write a function that takes a recursively defined data type as input and you like to test it with QuickCheck. How would you do that?

Example - Cartesian product of sets

We add the function 'product/2' to Erlang's sets module (in standard library) computing the Cartesian product of two sets. A new set can be constructed by associating every element of one set with every element of another set. The Cartesian product of two sets A and B, denoted by A × B is the set of all ordered pairs (a, b) such that a is a member of A and b is a member of B.

For example,

> S1 = sets:from_list([1,2]),
S2 = sets:from_list([red,white,blue]),
sets:to_list(sets:product(S1,S2)).
[{1,red},{1,white},{1,blue},{2,red},{2,white},{2,blue}]

In the fashion of test driven development, we start by writing down a property that should hold.

prop_relative_complement() ->
?FORALL({S1,S2},{set(int()),set(colour())},
begin
equal(sets:to_list(sets:product(S1,S2)),
[ {I,C} || I<-sets:to_list(S1), C<-sets:to_list(S2)])
end).

%% Since lists originating from sets may have the elements in different
%% orders, we need to compare that they contain the same elements.
equal(L1,L2) ->
(L1 -- L2) == [] andalso (L2 -- L1) == [].

Surely, we could implement the product function with the list comprehension above, but we want a more efficient implementation. The test, however, need not at all be efficient.

Generators for data type

After formulating the property, we need to implement the generators for the data types, sets and colours in our case, since there is a standard generator for integers. Picking a colour from a predefined set of colours is simple. Creating a set needs a thought... we have to use the library functions in the set module to do so, since we do not want to rely upon the implementation details. One possibility is to simply create a list and turn it into a set:

colour() ->
elements([red,white,blue,yellow,green,black]).

set(Gen) ->
?LET(L,list(Gen),sets:from_list(L)).