Erlang Central

# Difference between revisions of "Recursive Genereators"

From ErlangCentral Wiki

## 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)).
```

The generator for 'set' is, however, not very satisfactory. For a long discussion see the research paper: ["http://portal.acm.org/citation.cfm?id=1411275" Testing Erlang Data Types with Quviq QuickCheck], by Thomas Arts, Laura M. Castro and John Hughes. In short,

• In case of a test failure or a sample you are exposed to the internal representation of the set, without knowing how the set is created,
• You may test the sets module insufficiently by only considering sets created in this way,
• You miss the opportunity to test operations on sets that are result of the newly added product operation.
• Instead we propose to define a generator for sets recursively, by applying the operators available in the sets module. We need an extra argument to bind the size of the recursion. We create symbolic calls in order to be sure we can track the history of the set creation and in addition to simplify the presentation.

```set(Gen,0) ->
{call,sets,new,[]};
set(Gen,Size) ->
oneof([set(Gen,0),
{call,sets,from_list,[list(Gen)]},
```set(Gen) ->