4. Generating test cases
The QuickCheck tool for Haskell uses type classes so that arbitrary
values of various types may be generated behind the scenes. In SML,
we need to be more explicit, but the same holds true in Haskell if we
don't want the default generator (positive integers only, for
example). The Gen
module holds a wide range of tools for
creating random values of various structured types and, yes, even
functions!
We begin with the raw random number generator. The new
function generates a seed based on the current time. The range
function produces random integers between those in the given pair,
inclusive. The generator is applicative, in the sense that it returns
the new state of the random number generator.
 type rand
val new : unit → rand
val range : int * int → rand → int * rand

The generator for a type takes a random number stream
and produces a value of that type, along with the new state
of the stream.
 type 'a gen = rand → 'a * rand
type ('a, 'b) co = 'a → 'b gen → 'b gen

4.1 Randomvalue combinators
lift v
is a generator that always produces the given value.
select
picks uniform randomly from the values in the vector,
while choose
picks uniform randomly from the generators
in the vector, to produce a value. For example:
 Gen.choose #[Gen.lift 42, Gen.Int.int]

will return the number 42 with 50% probability, and a random integer
otherwise (but recall that Gen.Int.int
is biased toward zero and
the extrema). The primed version pairs each generator with an integer
weight to bias the choice (making it nonuniform).
 val lift : 'a → 'a gen
val select : 'a vector → 'a gen
val choose : 'a gen vector → 'a gen
val choose' : (int * 'a gen) vector → 'a gen

The functions ending in L
are the same, except they
operate on lists instead of vectors.
 val selectL : 'a list → 'a gen
val chooseL : 'a gen list → 'a gen
val chooseL' : (int * 'a gen) list → 'a gen

Here are some basic map and filtering functions over generators.
 val filter : ('a → bool) → 'a gen → 'a gen
val zip : ('a gen * 'b gen) → ('a * 'b) gen
val zip3 : ('a gen * 'b gen * 'c gen) →
('a * 'b * 'c) gen
val zip4 : ('a gen * 'b gen * 'c gen * 'd gen) →
('a * 'b * 'c * 'd) gen
val map : ('a → 'b) → 'a gen → 'b gen
val map2 : ('a * 'b → 'c) → ('a gen * 'b gen) →
'c gen
val map3 : ('a * 'b * 'c → 'd) →
('a gen * 'b gen * 'c gen) → 'd gen
val map4 : ('a * 'b * 'c * 'd → 'e) →
('a gen * 'b gen * 'c gen * 'd gen) →
'e gen

flip
is just like flipping a fair coin. With
flip'
, the coin is biased by the pair of integers given:
flip' (3,5)
will choose true
threeeights of the time,
and false
fiveeights.
 val flip : bool gen
val flip' : int * int → bool gen

These produce lists or optional values by consulting the
boolean generator about when to produce the nil list or NONE
.
 val list : bool gen → 'a gen → 'a list gen
val option : bool gen → 'a gen → 'a option gen

The following function produces any kind of sequential
collection type, you just provide the tabulate
function
as the first parameter. The integer generator then determines
how many elements the collection will have.
 val vector : (int * (int → 'a) → 'b) →
int gen * 'a gen → 'b gen

Here is an example, showing how we can generate strings
with vector
:
 Gen.vector CharVector.tabulate
(Gen.range(6,10), Gen.select #[#"a", #"b", #"c"])

Here is a sample of the strings it generated in one test:
 › "abbacccbbb" : CharVector.vector
› "bccbaabacb" : CharVector.vector
› "aacbbbaba" : CharVector.vector
› "aabbaca" : CharVector.vector
› "acaacbb" : CharVector.vector
› "cbbbccab" : CharVector.vector
› "bbcaccca" : CharVector.vector

 val variant : (int,'b) co
val arrow : ('a, 'b) co * 'b gen → ('a → 'b) gen
val cobool : (bool, 'b) co
val colist : ('a, 'b) co → ('a list, 'b) co
val coopt : ('a, 'b) co → ('a option, 'b) co

These turn generators into a stream of values. You can
limit them by a given integer, or just use the default maximum
number of values from the Settings
.
 type stream
val start : rand → stream
val limit' : int → 'a gen → ('a,stream) reader
val limit : 'a gen → ('a,stream) reader

4.2 Basis types
In addition to the general combinators, practically all of the
SML Basis types have associated generators in substructures. The
following generators can be instantiated for whatever character and
string types your implementation provides, such as
Gen.WideText.charByType
. For the default character and string
types, however, these are found in the toplevel of the Gen
structure.
 type char
type string
type substring
val char : char gen
val charRange : char * char → char gen
val charFrom : string → char gen
val charByType : (char → bool) → char gen
val string : (int gen * char gen) → string gen
val substring : string gen → substring gen
val cochar : (char, 'b) co
val costring : (string, 'b) co
val cosubstring : (substring, 'b) co

The functions in Gen.Int
(and Gen.Int32
, Gen.IntInf
,
etc.) generate integers in various ranges. They can easily be instantiated
for whatever integer types your implementation provides. They are biased
so that zero, maxInt
, and minInt
(if they exist) are
generated much more often than other integers.
 eqtype int
val int : int gen
val pos : int gen
val neg : int gen
val nonpos : int gen
val nonneg : int gen
val coint : (int, 'b) co

The functions generating unsigned words are in structures such as
Gen.Word
, Gen.Word8
, Gen,Word32
, etc., depending
on your implementation.
 eqtype word
val word : word gen
val coword : (word, 'b) co

These are in Gen.Real
structure. Currently, real numbers are
generated from strings of (decimal) digits, rather than from bits.
So some valid reals will never be generated. This may not be sufficient
for testing numerical code.
 type real
val real : real gen
val frac : real gen
val pos : real gen
val neg : real gen
val nonpos : real gen
val nonneg : real gen
val finite : real gen

Generate dates and times from Gen.DateTime
. The
dateFromYear
function uses the given generator to produce
the year, but then it comes up with a month, day, hour, minute,
and second itself. A few days are more likely than others because
we do not bother to generate the correct number of days based on the
month. This makes May 1st more likely than May 2nd, because it could
also have been generated as April 31st. (The Basis Date.date
normalizes the dates though, so you will never see April 31st.)
 val weekday : Date.weekday gen
val month : Date.month gen
val dateFromYear : int gen → Date.date gen
val time : Time.time gen

4.3 Recursive types
As pointed out in the QuickCheck paper, one needs to be careful when
generating treestructured data, due to the strong possibility of
nontermination. To avoid this problem, make the generator a function
of a decreasing integer parameter. When that parameter reaches zero,
the only choice is to return a leaf.
 datatype tree = Node of tree * tree  Leaf of int
fun gentree 0 = Gen.map Leaf Gen.Int.int
 gentree n =
Gen.choose' #[(1,Gen.map Leaf Gen.Int.int),
(4,Gen.map Node (Gen.zip(gentree(n div 2),
gentree(n div 2))))]

This document was generated by Chris League on April, 14 2008 using texi2html 1.78.