Erlang Central

# Recursive Genereators

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

###### Getting Started
Getting Started with Erlang
Categories
Main page
Recent changes
Random page
Help
View source
Editing help