Most programming languages have a random number generator of some kind. The Random class in the System namespace provides the default implementation in .NET. It can produce random integers and floating point numbers. That is all well and good, but we need to generate many more types than just numbers. The question is: how can we generalize the Random class to provide values of any type?
The answer is that we need to turn the random value generator into an abstract
concept, and define it as a function with multiple implementations. The function
gets a random number generator and transforms its output to a specific type T.
We define this abstract function as a delegate and call it Gen<T>.
namespace LinqCheck
{
using System;
using System.Collections.Generic;
using System.Linq;
using ExtensionCord;
public delegate T Gen<T> (Random rnd, int size);
The delegate takes as arguments an instance of the Random class and size, which represents the range of the returned value. The bigger the size the wider range of values should be returned. For integers, the size parameter limits the maximum number that the generator can return. For strings, it specifies the maximum length. The interpretation of the argument is thus context-sensitive.
We could now provide an implementation of Gen<T> for every type T that
we would like to generate, but that would result in a lot of boilerplate
code. Rather than going down that path, let's take our abstraction one step
further and make Gen<T> an instance of a
monad.
The Internet is littered with articles and blog posts explaining monads through category theory or using some (obscure) analogy. Leaving theoretical and pedagogical aspects aside, we will just show a real-world example of a monad implemented in C#. Even if you are unfamiliar with the concept, hopefully you can grasp the principle by following the code.
To build a monad you first of all need a generic type. Monad defines a way to compose instances of a generic type together by providing two simple operations: return and bind. Assuming our generic type is denoted by M \langle T \rangle, where T is the type parameter, the operations are defined as follows (we are using the curried notation here):
All monads share these two operations. They differ, however, in how the operations are implemented. There are also laws which all monads must obey, but we can ignore them for now.
To make things more concrete, let's implement the two operators for our
Gen<T> delegate. We put the operations into a static class called Gen.
public static class Gen
{
The signature of the return operation is:
The operation takes a value of type T and returns it wrapped in the
monad type M \langle T \rangle. Since return is a reserved keyword
in C# it is bad practice to define a method with that name. Instead,
we name it ToGen to denote that the method transforms a value into
the Gen monad. It is a generic, static, extension method whose
signature in C# syntax looks like this:
public static Gen<T> ToGen<T> (this T value)
{
To implement the method, we can use a functional programming technique commonly called as following the types. It entails realizing that when implementing a pure method, we can only return a value which we can construct from our parameters.
The only parameter we get is a value of type T. We have to return
a value of type Gen<T>, which is an alias for the delegate
(Random, int) => T. There is practically only one way to implement
that delegate given the parameters we have at hand.
return (rnd, size) => value;
}
When we follow the types the implementation becomes obvious.
The signature of bind is somewhat more complicated:
but it can be mapped to the C# syntax in a straightforward fashion. Again, we define the operation as static, generic, extension method.
public static Gen<U> Bind<T, U> (this Gen<T> gen, Func<T, Gen<U>> func)
{
Let's again follow the types to implement the method. We need to
return a value of type Gen<U> which corresponds to the delegate
(Random, int) => U. So, we need to return a lambda expression
with two parameters rnd and size.
return (rnd, size) =>
{
How should we implement this lambda expression? Well, we have
been given two parameters: a generator of type Gen<T> and a
function which maps T to Gen<U>. To get a value of type T
we need to call gen. Its arguments (Random, int) we get
from the parameters of the lambda expression.
var a = gen (rnd, size);
Now we have a value of type T in variable a. The only thing
we can do with that variable is to feed it to func to get a
generator of type Gen<U>. To get the expected result type U
of our lambda expression, we call this generator with the same
rnd and size parameters as before.
return func (a) (rnd, size);
};
}
Note that the process was almost mechanical. Think for a while, if you could implement the method differently. You will notice that if you try to change the implementation in any way, the code will not compile anymore; the types do not match.
This is the reason, why we usually do not have to concern ourselves with the monad laws. If your monad type is a pure function, it is impossible to define the return and bind operation in a way that violates the monad laws. There is literally only one way to implement them. Be warned that this realization can easily blow your mind...
Before going further, let's step back and contemplate what we just
implemented. We defined two operations: ToGen converts a value into
a generator, and Bind turns a generator for T's into generator for
U's when given a function that maps a value of type T to a
generator of type Gen<U>.
Essentially we defined a way to create generators and chain them
together while hiding the two parameters of the Gen<T> delegate.
This does not sound like a big deal, but it is.
We can construct arbitrary complex generators and implement almost all the functionality we need using just these two operations. The instance of the Random class and the size parameter are passed along transparently in the background. This simplifies our code and makes it composable. With monads we achieve true code reusability.
In the introduction there was a vague claim that LINQ and monads are
somehow related. Now we will show exactly how. We will implement LINQ's
core operations Select and SelectMany using ToGen and Bind. The
Select* methods enable the syntactic sugaring that allows us to write
generators as LINQ expressions.
When C# compiler is desugaring a LINQ expression, it just rewrites it
using the Select and SelectMany extension methods. If these methods
are defined somewhere and they have the correct signature, then the
compiler will be happy.
The trick is thus to define those methods for our own monad type, and we get a domain specific language for our generators. This DSL just happens to have the same syntax as LINQ. Haskell provides syntactic sugaring for monads too, although its syntax resembles an imperative program rather than a SQL query. Nevertheless, the idea is exactly the same.
The signature of the LINQ's Select method is almost the same as for
Bind. The only difference is the type of the function given as the
second argument. Instead of Func<T, Gen<U>> it is Func<T, U>.
Converting the function type to one expected by Bind is trivial using
ToGen.
public static Gen<U> Select<T, U> (this Gen<T> gen, Func<T, U> select)
{
return gen.Bind (a => select (a).ToGen ());
}
The SelectMany operation is called flatMap in some functional
languages. It performs a double Bind as it combines a generator for
T's and a generator for U's, and maps them to a generator for V's.
Whenever we have more than one select clause in a LINQ expression this
method is called.
public static Gen<V> SelectMany<T, U, V> (this Gen<T> gen,
Func<T, Gen<U>> project, Func<T, U, V> select)
{
As for Select the correct implementation reveals itself by
following the types. Note that the types force us to arrange
the Bind operations in a specific order.
return gen.Bind (a => project (a).Bind (b => select (a, b).ToGen ()));
}
Using Bind and ToGen makes the implementation of Select and
SelectMany completely generic. This means that these methods are
implemented exactly the same way for any monad we might come up with.
Unfortunately it is not possible to reuse these implementations for
other monads like in Haskell since the C# type system lacks
type classes, but copying
and pasting will work as well.
There is another monad type in LinqCheck: Prop<T>. Check for yourself
that its implementation of Select and SelectMany is same as above.
LINQ's Where combinator we cannot define it in terms of ToGen and
Bind. Where filters out generated values which do not match a
specified predicate. It might need to call the generator repeatedly to
obtain a value that satisfies the predicate. In the worst case, it
might not find a matching value at all. The combinator gives up after
100 tries and throw an exception. It is the caller's responsibility to
ensure that the predicate is not too strict.
public static Gen<T> Where<T> (this Gen<T> gen, Func<T, bool> predicate)
{
return (rnd, size) =>
{
T res;
var tries = 0;
do
res = gen (rnd, size);
while (!predicate (res) && ++tries < 100);
if (tries >= 100)
throw new ArgumentException ("Could not generate a " +
"random value which satisfies the predicate.");
return res;
};
}
New generators can be now defined as LINQ expressions. As an example, let's define two new combinators which combine two generators into a generator of tuples.
public static Gen<Tuple<T, U>> Plus<T, U> (this Gen<T> gen1, Gen<U> gen2)
{
return from a in gen1
from b in gen2
select Tuple.Create (a, b);
}
public static Gen<Tuple<T, U, V>> Plus<T, U, V> (this Gen<T> gen1,
Gen<U> gen2, Gen<V> gen3)
{
return from a in gen1
from b in gen2
from c in gen3
select Tuple.Create (a, b, c);
}
In addition to combinators we naturally need generators for the
number types int and double. These generators exploit the
functionality of the Random class. The size parameter is used to
limit the generated values, if no explicit limit is specified.
public static Gen<int> ChooseInt ()
{
return (rnd, size) => rnd.Next (-size / 2, size / 2);
}
public static Gen<int> ChooseInt (int min)
{
return (rnd, size) => rnd.Next (min, min + size);
}
public static Gen<int> ChooseInt (int min, int max)
{
return (rnd, size) => rnd.Next (min, max);
}
public static Gen<double> ChooseDouble ()
{
return (rnd, size) => ((rnd.NextDouble () - 0.5) * size);
}
public static Gen<double> ChooseDouble (double min)
{
return (rnd, size) => (rnd.NextDouble () * size) + min;
}
public static Gen<double> ChooseDouble (double min, double max)
{
return (rnd, size) => (rnd.NextDouble () * (max - min)) + min;
}
Another way to generate a random value is to select it from a predefined set. This set can be given as an array or as an IEnumerable.
public static Gen<T> ChooseFrom<T> (params T[] values)
{
return (rnd, size) => values[rnd.Next (values.Length)];
}
public static Gen<T> ElementOf<T> (IEnumerable<T> enumerable)
{
return ChooseFrom (enumerable.ToArray ());
}
We need also to do type conversions between the generators. The following methods are defined mostly for convenience, to avoid boilerplate code when constructing generators.
public static Gen<U> Cast<T, U> (this Gen<T> gen) where T : U
{
return gen.Bind (x => ((U)x).ToGen ());
}
public static Gen<long> ToLong (this Gen<int> gen)
{
return gen.Bind (x => ((long)x).ToGen ());
}
public static Gen<float> ToFloat (this Gen<double> gen)
{
return gen.Bind (x => ((float)x).ToGen ());
}
Once we can generate primitive types, the next step is to generate collections of them. Since practically all collections implement the IEnumerable interface, we can use it as a basis to generate any collection type.
First let's define an infinite sequence of values. This is the most general collection generator from which the more restricted versions are derived.
private static IEnumerable<T> InfiniteEnumerable<T> (Gen<T> gen,
Random rnd, int size)
{
while (true) yield return gen (rnd, size);
}
The second variant returns the specified number of random values.
private static IEnumerable<T> FixedEnumerable<T> (Gen<T> gen,
Random rnd, int size, int length)
{
return InfiniteEnumerable (gen, rnd, size).Take (length);
}
And the third variant returns a finite but random number of elements.
private static IEnumerable<T> RandomEnumerable<T> (Gen<T> gen,
Random rnd, int size)
{
return FixedEnumerable (gen, rnd, size, rnd.Next (size));
}
The following version takes the limits from the generator's arguments. It is the easiest way to convert a generator into a collection generator.
public static Gen<IEnumerable<T>> EnumerableOf<T> (this Gen<T> gen)
{
return (rnd, size) => RandomEnumerable (gen, rnd, size);
}
Below are the corresponding generators for arrays. They utilize the IEnumerable generators and the extension methods defined in System.Linq.Enumerable and ExtensionCord library.
public static Gen<T[]> ArrayOf<T> (this Gen<T> gen)
{
return (rnd, size) => RandomEnumerable (gen, rnd, size).ToArray ();
}
public static Gen<T[]> FixedArrayOf<T> (this Gen<T> gen, int length)
{
return (rnd, size) => FixedEnumerable (gen, rnd, size, length)
.ToArray ();
}
public static Gen<T[,]> Fixed2DArrayOf<T> (this Gen<T> gen,
int dimension1, int dimension2)
{
return (rnd, size) => InfiniteEnumerable (gen, rnd, size)
.To2DArray (dimension1, dimension2);
}
Sometimes we have more than one generator for a type, and we want to
randomly choose one of them. The OneOf combinator will choose a
generator from an array using even distribution. I.e. each choice
has an equal chance to be selected.
public static Gen<T> OneOf<T> (params Gen<T>[] gens)
{
return ChooseInt (0, gens.Length).Bind (i => gens[i]);
}
If you want a skewed distribution of the choices, you can use the
Frequency method. It allows you to specify the frequency for each
choice. The frequencies are defined as integers with relative ranges.
For example, if choice A has a frequency of 3 and choice B has 12,
choice B is 4 times more likely to be selected than A.
public static Gen<T> Frequency<T> (params Tuple<int, Gen<T>>[] freqGens)
{
var sum = 0;
for (int i = 0; i < freqGens.Length; i++)
freqGens[i] = Tuple.Create (sum += freqGens[0].Item1,
freqGens[i].Item2);
return ChooseInt (1, sum).Bind (x =>
freqGens.First (fg => fg.Item1 >= x).Item2);
}
}
}
Before wrapping up the chapter, let's discuss the requirement of determinism. Generators are not truly random; their output depends on the seed provided to the instance of the Random class that we pass around. To put it differently, they produce pseudorandom values.
This is important because we want to be able to generate a same sequence
of values multiple times when we are generating test data. All of the
combinators work deterministically. They extract random numbers from the rnd
object and pass it around in the same manner every time they are called. This
ensures that whatever generator we compose, given the same seed, it will
generate the same value.