Testing functions is important when developing software. A common way of writing automated tests is to use examples: provide a specific input to a function and check that it returns the expected output. Property-based testing is a different approach that focuses on verifying that a function has certain properties. For example, you might check that a List.sort function returns a list of the same length as it receives, that each of its elements is no bigger than the next and that the elements in the input list are also in the output list.
FsCheck is a popular library for property-based testing in F#. It allows developers to define properties that should always be true for a given function and automatically generates random input to check whether the properties are true.
In this post, we will start by testing F#'s Set.union function works correctly. This example may seem somewhat abstract, but don't worry! There's a discussion of properties you might write for a "normal" function too.
Understanding Set.union
A set is a collection of elements where no element is repeated. The union of two sets A and B is another set that contains every element in one or both of A and B.
In F#, sets are typed, so all elements in a set have the same type. The Set.union function in F# combines two sets, returning a new set that contains all elements from both input sets.
To ensure that Set.union is implemented correctly, we can define three properties that must hold:
- All elements of
aare inSet.union a b. - All elements of
bare inSet.union a b. - All elements of
Set.union a bare either inaor inb.
If these properties are true of Set.union, we know that Set.union is working correctly.
We'll explore how to encode those properties in F# below. If you want to run the snippets in an F# script, you'll need to start your file with the following:
#r "nuget: FsCheck"
open FsCheckProperty 1: all elements of a are in Set.union a b
To test the first property, we can use FsCheck to generate random sets and verify that all elements of the first set are present in the result of the union operation. Here’s how we can implement this:
let allElementsInA a b =
let union = Set.union a b
a |> Set.forall (fun x -> union |> Set.contains x)
Check.Quick (fun (a: Set<int>) (b: Set<int>) -> allElementsInA a b)In this code snippet, we define a property allElementsInA that checks if every element in set a is also in the result of Set.union a b. The Check.Quick function runs the input function test with randomly generated sets of integers, and checks that it always returns true.
Property 2: all elements of b are in Set.union a b
Similarly, we can define a property to verify that all elements of the second set are included in the union:
let allElementsInB a b =
let union = Set.union a b
b |> Set.forall (fun x -> union |> Set.contains x)
Check.Quick (fun (a: Set<int>) (b: Set<int>) -> allElementsInB a b)This property, allElementsInB, ensures that every element in set b is present in the union of a and b.
Property 3: all elements of Set.union a b are in a or in b
Finally, we need to confirm that every element in the result of the union is one of the input sets:
let allElementsInUnionAreInAOrB a b =
let union = Set.union a b
union |> Set.forall (fun x -> a |> Set.contains x || b |> Set.contains x)
Check.Quick (fun (a: Set<int>) (b: Set<int>) -> allElementsInUnionAreInAOrB a b)The property allElementsInUnionAreInAOrB checks that every element in the union of a and b is contained in either a or b (or both).
Running the tests
You can find the complete implementation of these tests in the accompanying GitHub repository for this post. Here’s an excerpt from the terminal showing the results of running one of the above snippets:
Ok, passed: 100 tests.The property has been checked 100 times, and passed every time (the number of iterations is configurable). While this doesn't guarantee that our implementation is correct, it means that it's very unlikely that it's incorrect.
We used integer sets when testing Set.union, but we could have used any value that implements System.IComparable. FsCheck doesn't support generating any random IComparable, but can in some cases generate random values with generic type parameters. For example, when testing the generic property (fun x -> List.rev (List.rev x) = x), it will generate lists of different concrete types (List<int>, List<string>, List<int * string option> etc.). This can help to catch edge cases that you might not have considered!
A real-world example
Imagine that you're playing a game where cards are drawn and discarded from the top of a deck of cards, and occasionally the discard pile is shuffled and put back on top of the deck. You want to keep track of the shuffled "layers", so that you can work out which cards will be drawn, and which cards could be drawn, when drawing n cards. As an example, suppose that the top layer contains 3♦ and 4❤, and the next layer has 5♣, 6♠ and 7❤. Then you know that if you draw three cards you will draw 3♦ and 4❤, and you could also draw one of 5♣, 6♠ and 7❤.
Now imagine that you want to write an application that keeps track of this for you. Some properties you can check for the set of cards returned from the cardsThatCanBeDrawn function when drawing n cards from a layered deck are:
- The returned set of cards is empty if
nis 0. - It contains all cards in the deck if
nis at least as big as the number of cards in the deck. - It has at least
ncards ifnis postive but less than the number of cards in the deck. - It is one of the "rolling unions" of the top few layers of cards (which are themselves sets). That is, it's either empty, or it's the top layer, or the union of the top two layers, or the union of the top three layers etc.
- The previous "rolling union" has fewer than
ncards.
These properties completely specify how the function should behave. If the implementation has all of those properites, then it must return the correct answer!
This was useful for the first F# hobby application that I built for tracking where cards in the infection deck are in the board game Pandemic.
Conclusion
Property-based testing is a powerful technique for ensuring the correctness of functions. By defining and validating properties, we can often gain more confidence in our code than example-based tests might provide. Give property-based testing a try in your own projects to see if you like it!
For further information, check out the following resources:
- The FsCheck Documentation.
- Scott Wlaschin's property-based testing blog series.
- Mark Seemann's Pluralsight course "Introduction to Property-based Testing with F#".
