A Range kata implementation in F# by Mark Seemann
This time with some property-based testing.
This article is an instalment in a short series of articles on the Range kata. In the previous article I described my first attempt at the kata, and also complained that I had to think of test cases myself. When I find it tedious coming up with new test cases, I usually start to wonder if it'd be easier to use property-based testing.
Thus, when I decided to revisit the kata, the variation that I was most interested in pursuing was to explore whether it would make sense to use property-based testing instead of a set of existing examples.
Since I also wanted to do the second attempt in F#, I had a choice between FsCheck and Hedgehog. Each have their strengths and weaknesses, but since I already know FsCheck so well, I decided to go with Hedgehog.
I also soon discovered that I had no interest in developing the full suite of capabilities implied by the kata. Instead, I decided to focus on just the data structure itself, as well as the contains function. As in the previous article, this function can also be used to cover the kata's ContainsRange feature.
Getting started #
There's no rule that you can't combine property-based testing with test-driven development (TDD). On the contrary, that's how I often do it. In this exercise, I first wrote this test:
[<Fact>] let ``Closed range contains list`` () = Property.check <| property { let! xs = Gen.int16 (Range.linearBounded ()) |> Gen.list (Range.linear 1 99) let min = List.min xs let max = List.max xs let actual = (Closed min, Closed max) |> Range.contains xs Assert.True (actual, sprintf "Range [%i, %i] expected to contain list." min max) }
We have to be careful when reading and understanding this code: There are two Range modules in action here!
Hedgehog comes with a Range module that you must use to define how it samples values from domains. Examples of that here are Range.linearBounded and Range.linear.
On the other hand, I've defined my contains function in a Range module, too. As long as there's no ambiguity, the F# compiler doesn't have a problem with that. Since there's no contains function in the Hedgehog Range module, the F# compiler isn't confused.
We humans, on the other hand, might be confused, and had this been a code base that I had to maintain for years, I might seriously consider whether I should rename my own Range module to something else, like Interval, perhaps.
In any case, the first test (or property, if you will) uses a technique that I often use with property-based testing. I'm still searching for a catchy name for this, but here we may call it something like reverse test-case assembly. My goal is to test a predicate, and this particular property should verify that for a given Equivalence Class, the predicate is always true.
While we may think of an Equivalence Class as a set from which we pick test cases, I don't actually have a full enumeration of such a set. I can't have that, since that set is infinitely big. Instead of randomly picking values from a set that I can't fully populate, I instead carefully pick test case values in such a way that they would all belong to the same set partition (Equivalence Class).
The test name suggests the test case: I'd like to verify that given I have a closed range, when I ask it whether a list within that range is contained, then the answer is true. How do I pick such a test case?
I do it in reverse. You can say that the sampling is the dual of the test. I start with a list (xs) and only then do I create a range that contains it. Since the first test case is for a closed range, the min and max values are sufficient to define such a range.
How do I pass that property?
Degenerately, as is often the case with TDD beginnings:
module Range = let contains _ _ = true
Even though the Closed range contains list property effectively executes a hundred test cases, the Devil's Advocate can easily ignore that and instead return hard-coded true.
More properties are required to flesh out the behaviour of the function.
Open range #
While I do keep the transformation priority premise in mind when picking the next test (or, here, property), I'm rarely particularly analytic about it. Since the first property tests that a closed range barely contains a list of values from its minimum to its maximum, it seemed like a promising next step to consider the case where the range consisted of open endpoints. That was the second test I wrote, then:
[<Fact>] let ``Open range doesn't contain endpoints`` () = Property.check <| property { let! min = Gen.int32 (Range.linearBounded ()) let! max = Gen.int32 (Range.linearBounded ()) let actual = (Open min, Open max) |> Range.contains [min; max] Assert.False (actual, sprintf "Range (%i, %i) expected not to contain list." min max) }
This property simply states that if you query the contains predicate about a list that only contains the endpoints of an open range, then the answer is false because the endpoints are Open.
One implementation that passes both tests is this one:
module Range = let contains _ endpoints = match endpoints with | Open _, Open _ -> false | _ -> true
This implementation is obviously still incorrect, but we have reason to believe that we're moving closer to something that will eventually work.
Tick-tock #
In the spirit of the transformation priority premise, I've often found that when test-driving a predicate, I seem to fall into a tick-tock pattern where I alternate between tests for a true return value, followed by a test for a false return value, or the other way around. This was also the case here. The previous test was for a false value, so the third test requires true to be returned:
[<Fact>] let ``Open range contains list`` () = Property.check <| property { let! xs = Gen.int64 (Range.linearBounded ()) |> Gen.list (Range.linear 1 99) let min = List.min xs - 1L let max = List.max xs + 1L let actual = (Open min, Open max) |> Range.contains xs Assert.True (actual, sprintf "Range (%i, %i) expected to contain list." min max) }
This then led to this implementation of the contains function:
module Range = let contains ys endpoints = match endpoints with | Open x, Open z -> ys |> List.forall (fun y -> x < y && y < z) | _ -> true
Following up on the above true-demanding test, I added one that tested a false scenario:
[<Fact>] let ``Open-closed range doesn't contain endpoints`` () = Property.check <| property { let! min = Gen.int16 (Range.linearBounded ()) let! max = Gen.int16 (Range.linearBounded ()) let actual = (Open min, Closed max) |> Range.contains [min; max] Assert.False (actual, sprintf "Range (%i, %i] expected not to contain list." min max) }
This again led to this implementation:
module Range = let contains ys endpoints = match endpoints with | Open x, Open z -> ys |> List.forall (fun y -> x < y && y < z) | Open x, Closed z -> false | _ -> true
I had to add four more tests before I felt confident that I had the right implementation. I'm not going to show them all here, but you can look at the repository on GitHub if you're interested in the interim steps.
Types and functionality #
So far I had treated a range as a pair (two-tuple), just as I had done with the code in my first attempt. I did, however, have a few other things planned for this code base, so I introduced a set of explicit types:
type Endpoint<'a> = Open of 'a | Closed of 'a type Range<'a> = { LowerBound : Endpoint<'a>; UpperBound : Endpoint<'a> }
The Range record type is isomorphic to a pair of Endpoint values, so it's not strictly required, but does make things more explicit.
To support the new type, I added an ofEndpoints function, and finalized the implementation of contains:
module Range = let ofEndpoints (lowerBound, upperBound) = { LowerBound = lowerBound; UpperBound = upperBound } let contains ys r = match r.LowerBound, r.UpperBound with | Open x, Open z -> ys |> List.forall (fun y -> x < y && y < z) | Open x, Closed z -> ys |> List.forall (fun y -> x < y && y <= z) | Closed x, Open z -> ys |> List.forall (fun y -> x <= y && y < z) | Closed x, Closed z -> ys |> List.forall (fun y -> x <= y && y <= z)
As is so often the case in F#, pattern matching makes such functions a pleasure to implement.
Conclusion #
I was curious whether using property-based testing would make the development process of the Range kata simpler. While each property was simple, I still had to write eight of them before I felt I'd fully described the problem. This doesn't seem like much of an improvement over the example-driven approach I took the first time around. It seems to be a comparable amount of code, and on one hand a property is more abstract than an example, but on the hand usually also covers more ground. I feel more confident that this implementation works, because I know that it's being exercised more rigorously.
When I find myself writing a property per branch, so to speak, I always feel that I missed a better way to describe the problem. As an example, for years I would demonstrate how to test the FizzBuzz kata with property-based testing by dividing the problem into Equivalence Classes and then writing a property for each partition. Just as I've done here. This is usually possible, but smells of being too coupled to the implementation.
Sometimes, if you think about the problem long enough, you may be able to produce an alternative set of properties that describe the problem in a way that's entirely decoupled from the implementation. After years, I finally managed to do that with the FizzBuzz kata.
I didn't succeed doing that with the Range kata this time around, but maybe later.
