Erlang Central

Difference between revisions of "Recursive Genereators"

From ErlangCentral Wiki

(New page: Category:QuickCheck ==Authors== Thomas Arts ==Recursive Generators== Assume you write a function that takes a recursively defined data type as input and you like to ...)
 
Line 26:Line 26:
 
     ?FORALL({S1,S2},{set(int()),set(colour())},
 
     ?FORALL({S1,S2},{set(int()),set(colour())},
 
             begin
 
             begin
               equal(sets:to_list(sets:product(S1,S2))
+
               equal(sets:to_list(sets:product(S1,S2)),
 
                     [ {I,C} || I<-sets:to_list(S1), C<-sets:to_list(S2)])
 
                     [ {I,C} || I<-sets:to_list(S1), C<-sets:to_list(S2)])
 
             end).
 
             end).
Line 37:Line 37:
  
 
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.
 
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:
 +
<code>
 +
colour() ->
 +
elements([red,white,blue,yellow,green,black]).
 +
 +
set(Gen) ->
 +
?LET(L,list(Gen),sets:from_list(L)).
 +
</code>

Revision as of 11:23, 20 October 2008


Contents

Authors

Thomas Arts

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