ploeh blog danish software design

In which a general transition function is composed from specialised transition functions.

This article is the fifth in a series of articles that demonstrate how to develop software using types and properties. In the previous article, you witnessed the continued walk-through of the Tennis Kata done with Property-Based Test-Driven Development. In these articles, you saw how to define small, specific functions that model the transition out of particular states. In this article, you'll see how to compose these functions to a more general function.

The source code for this article series is available on GitHub.

Composing the general function #

If you recall the second article in this series, what you need to implement is a state transition of the type Score -> Player -> Score. What you have so far are the following functions:

• scoreWhenPoints : PointsData -> Player -> Score
• scoreWhenForty : FortyData -> Player -> Score
• scoreWhenDeuce : Player -> Score
• scoreWhenAdvantage : Player -> Player -> Score
• scoreWhenGame : Player -> Score

You've seen the development of scoreWhenDeuce, scoreWhenAdvantage, and scoreWhenForty in previous articles, but you haven't seen scoreWhenGame or scoreWhenPoints. The development of these remaining functions follow similar principles, and use similar techniques. If you're interested in the details, you can always peruse the source code repository.

These five functions are all the building blocks you need to implement the desired function of the type Score -> Player -> Score. You may recall that Score is a discriminated union defined as:

type Score =
| Points of PointsData
| Forty of FortyData
| Deuce
| Advantage of Player
| Game of Player

Notice how these cases align with the five functions above. That's not a coincidence. The driving factor behind the design of these five function was to match them with the five cases of the Score type. In another article series, I've previously shown this technique, applied to a different problem.

You can implement the desired function by clicking the pieces together:

let score current winner = 
    match current with
    | Points p -> scoreWhenPoints p winner
    | Forty f -> scoreWhenForty f winner
    | Deuce -> scoreWhenDeuce winner
    | Advantage a -> scoreWhenAdvantage a winner
    | Game g -> scoreWhenGame g

There's not a lot to it, apart from matching on current. If, for example, current is a Forty value, the match is the Forty case, and f represents the FortyData value in that case. The destructured f can be passed as an argument to scoreWhenForty, together with winner. The scoreWhenForty function returns a Score value, so the score function has the type Score -> Player -> Score - exactly what you want!

Here's an example of using the function:

> score Deuce PlayerOne;;
val it : Score = Advantage PlayerOne

When the score is deuce and player one wins the ball, the resulting score is advantage to player one.

Properties for the score function #

Can you express some properties for the score function? Yes and no. You can't state particularly interesting properties about the function in isolation, but you can express meaningful properties about sequences of scores. We'll return to that in a later article. For now, let's focus on the function in itself.

You can, for example, state that the function can handle all input:

[<Property>]
let ``score returns a value`` (current : Score) (winner : Player) =
    let actual : Score = score current winner
    true // Didn't crash - this is mostly a boundary condition test

This property isn't particularly interesting. It's mostly a smoke test that I added because I thought that it might flush out boundary issues, if any exist. That doesn't seem to be the case.

You can also add properties that examine each case of input:

[<Property>]
let ``score Points returns correct result`` points winner =
    let actual = score (Points points) winner
 
    let expected = scoreWhenPoints points winner
    expected =! actual

Such a property is unlikely to be of much use, because it mostly reproduces the implementation details of the score function. Unless you're writing high-stakes software (e.g. for medical purposes), such properties are likely to have little or negative value. After all, tests are also code; do you trust the test code more than the production code? Sometimes, you may, but if you look at the source code for the score function, it's easy to review.

You can write four other properties, similar to the one above, but I'm going to skip them here. They are in the source code repository, though, so you're welcome to look there if you want to see them.

To be continued... #

In this article, you saw how to compose the five specific state transition functions into an overall state transition function. This is only a single function that calculates a score based on another score. In order to turn this function into a finite state machine, you must define an initial state and a way to transition based on a sequence of events.

In the next article, you'll see how to define the initial state, and in the article beyond that, you'll see how to move through a sequence of transitions.

If you're interested in learning more about designing with types, you can watch my Type-Driven Development with F# Pluralsight course.

An example of how to constrain generated input with FsCheck.

This article is the fourth in a series of articles that demonstrate how to develop software using types and properties. In the previous article, you saw how to express properties for a simple state transition: finding the next tennis score when the current score is advantage to a player. These properties were simple, because they had to hold for all input of the given type (Player). In this article, you'll see how to constrain the input that FsCheck generates, in order to express properties about tennis scores where one of the players have forty points.

The source code for this article series is available on GitHub.

Winning the game #

When one of the players have forty points, there are three possible outcomes of the next ball:

• If the player with forty points wins the ball, (s)he wins the game.
• If the other player has thirty points, and wins the ball, the score is deuce.
• If the other player has less than thirty points, and wins the ball, his or her points increases to the next level (from love to fifteen, or from fifteen to thirty).

The first property is the easiest to express, because it doesn't depend on the other player's points.

You may recall that when one of the players have forty points, you express that score with the FortyData record type:

type FortyData = { Player : Player; OtherPlayerPoint : Point }

Since Point is defined as Love | Fifteen | Thirty, it's clear that the Player who has forty points has a higher score than the other player - regardless of the OtherPlayerPoint value. This means that if that player wins, (s)he wins the game. It's easy to express that property with FsCheck:

[<Property>]
let ``Given player: 40 when player wins then score is correct``
    (current : FortyData) =
 
    let actual = scoreWhenForty current current.Player
 
    let expected = Game current.Player
    expected =! actual

Notice that this test function takes a single function argument called current, of the type FortyData. Since illegal states are unrepresentable, FsCheck can only generate legal values of that type.

The scoreWhenForty function is a function that explicitly models what happens when the score is in the Forty case. The first argument is the data associated with the current score: current. The second argument is the winner of the next ball. In this test case, you want to express the case where the winner is the player who already has forty points: current.Player.

The expected outcome of this is always that current.Player wins the game.

The =! operator is a custom operator defined by Unquote, an assertion library. You can read the expression as expected must equal actual.

In order to pass this property, you must implement a scoreWhenForty function. This is the simplest implementation that could possible work:

let scoreWhenForty current winner = Game winner

While this passes all tests, it's obviously not a complete implementation.

Getting even #

Another outcome of a Forty score is that if the other player has thirty points, and wins the ball, the new score is deuce. Expressing this as a property is only slightly more involved:

[<Property>]
let ``Given player: 40 - other: 30 when other wins then score is correct``
    (current : FortyData) =
 
    let current = { current with OtherPlayerPoint = Thirty }
    let actual = scoreWhenForty current (other current.Player)
    Deuce =! actual

In this test case, the other player specifically has thirty points. There's no variability involved, so you can simply set OtherPlayerPoint to Thirty.

Notice that instead of creating a new FortyData value from scratch, this property takes current (which is generated by FsCheck) and uses a copy-and-update expression to explicitly bind OtherPlayerPoint to Thirty. This ensures that all other values of current can vary, but OtherPlayerPoint is fixed.

The first line of code shadows the current argument by binding the result of the copy-and-update expression to a new value, also called current. Shadowing means that the original current argument is no longer available in the rest of the scope. This is exactly what you want, because the function argument isn't guaranteed to model the test case where the other player has forty points. Instead, it can be any FortyData value. You can think of the argument provided by FsCheck as a seed used to arrange the Test Fixture.

The property proceeds to invoke the scoreWhenForty function with the current score, and indicating that the other player wins the ball. You saw the other function in the previous article, but it's so small that it can be repeated here without taking up much space:

let other = function PlayerOne -> PlayerTwo | PlayerTwo -> PlayerOne

Finally, the property asserts that deuce must equal actual. In other words, the expected result is deuce.

This property fails until you fix the implementation:

let scoreWhenForty current winner =
    if current.Player = winner
    then Game winner
    else Deuce

This is a step in the right direction, but still not the complete implementation. If the other player has only love or fifteen points, and wins the ball, the new score shouldn't be deuce.

Incrementing points #

The last test case is where it gets interesting. The situation you need to test is that one of the players has forty points, and the other player has either love or fifteen points. This feels like the previous case, but has more variable parts. In the previous test case (above), the other player always had thirty points, but in this test case, the other player's points can vary within a constrained range.

Perhaps you've noticed that so far, you haven't seen any examples of using FsCheck's API. Until now, we've been able to express properties from values generated by FsCheck without constraints. This is no longer possible, but fortunately, FsCheck comes with an excellent API that enables you to configure it. Here, you'll see how to configure it to create values from a proper subset of all possible values:

[<Property>]
let ``Given player: 40 - other: < 30 when other wins then score is correct``
    (current : FortyData) =
 
    let opp = Gen.elements [Love; Fifteen] |> Arb.fromGen
    Prop.forAll opp (fun otherPlayerPoint ->
        let current = { current with OtherPlayerPoint = otherPlayerPoint }
 
        let actual = scoreWhenForty current (other current.Player)
 
        let expected =
            incrementPoint current.OtherPlayerPoint
            |> Option.map (fun np -> { current with OtherPlayerPoint = np })
            |> Option.map Forty
        expected =! Some actual)

That's only nine lines of code, and some of it is similar to the previous property you saw (above). Still, F# code can have a high degree of information density, so I'll walk you through it.

FsCheck's API is centred around Generators and Arbitraries. Ultimately, when you need to configure FsCheck, you'll need to define an Arbitrary<'a>, but you'll often use a Gen<'a> value to do that. In this test case, you need to tell FsCheck to use only the values Love and Fifteen when generating Point values.

This is done in the first line of code. Gen.elements creates a Generator that creates random values by drawing from a sequence of possible values. Here, we pass it a list of two values: Love and Fifteen. Because both of these values are of the type Point, the result is a value of the type Gen<Point>. This Generator is piped to Arb.fromGen, which turns it into an Arbitrary (for now, you don't have to worry about exactly what that means). Thus, opp is a value of type Arbitrary<Point>.

You can now take that Arbitrary and state that, for all values created by it, a particular property must hold. This is what Prop.forAll does. The first argument passed is opp, and the second argument is a function that expresses the property. When the test runs, FsCheck call this function 100 times (by default), each time passing a random value generated by opp.

The next couple of lines are similar to code you've seen before. As in the case where the other player had thirty points, you can shadow the current argument with a new value where the other player's points is set to a value drawn from opp; that is, Love or Fifteen.

Notice how the original current value comes from an argument to the containing test function, whereas otherPlayerPoint comes from the opp Arbitrary. FsCheck is smart enough to enable this combination, so you still get the variation implied by combining these two sources of random data.

The actual value is bound to the result of calling scoreWhenForty with the current score, and indicating that the other player wins the ball.

The expected outcome is a new Forty value that originates from current, but with the other player's points incremented. There is, however, something odd-looking going on with Option.map - and where did that incrementPoint function come from?

In the previous article, you saw how sometimes, a test triggers the creation of a new helper function. Sometimes, such a helper function is of such general utility that it makes sense to put it in the 'production code'. Previously, it was the other function. Now, it's the incrementPoint function.

Before I show you the implementation of the incrementPoint function, I would like to suggest that you reflect on it. The purpose of this function is to return the point that comes after a given point. Do you remember how, in the article on designing with types, we quickly realised that love, fifteen, thirty, and forty are mere labels; that we don't need to do arithmetic on these values?

There's one piece of 'arithmetic' you need to do with these values, after all: you must be able to 'add one' to a value, in order to get the next value. That's the purpose of the incrementPoint function: given Love, it'll return Fifteen, and so on - but with a twist!

What should it return when given Thirty as input? Forty? That's not possible. There's no Point value higher than Thirty. Forty doesn't exist.

The object-oriented answer would be to throw an exception, but in functional programming, we don't like such arbitrary jump statements in our code. GOTO is, after all, considered harmful.

Instead, we can return None, but that means that we must wrap all the other return values in Some:

let incrementPoint = function
    | Love -> Some Fifteen
    | Fifteen -> Some Thirty
    | Thirty -> None

This function has the type Point -> Point option, and it behaves like this:

> incrementPoint Love;;
val it : Point option = Some Fifteen
> incrementPoint Fifteen;;
val it : Point option = Some Thirty
> incrementPoint Thirty;;
val it : Point option = None

Back to the property: the expected value is that the other player's points are incremented, and this new points value (np, for New Points) is bound to OtherPlayerPoint in a copy-and-update expression, using current as the original value. In other words, this expression returns the current score, with the only change that OtherPlayerPoint now has the incremented Point value.

This has to happen inside of an Option.map, though, because incrementPoint may return None. Furthermore, the new value created from current is of the type FortyData, but you need a Forty value. This can be achieved by piping the option value into another map that composes the Forty case constructor.

The expected value has the type Score option, so in order to be able to compare it to actual, which is 'only' a Score value, you need to make actual a Score option value as well. This is the reason expected is compared to Some actual.

One implementation that passes this and all previous properties is:

let scoreWhenForty current winner =
    if current.Player = winner
    then Game winner
    else
        match incrementPoint current.OtherPlayerPoint with
        | Some p -> Forty { current with OtherPlayerPoint = p }
        | None -> Deuce

Notice that the implementation also uses the incrementPoint function.

To be continued... #

In this article, you saw how, even when illegal states are unrepresentable, you may need to further constrain the input into a property in order to express a particular test case. The FsCheck combinator library can be used to do that. It's flexible and well thought-out.

While I could go on and show you how to express properties for more state transitions, you've now seen the most important techniques. If you want to see more of the tennis state transitions, you can always check out the source code accompanying this article series.

In the next article, instead, you'll see how to compose all these functions into a system that implements the tennis scoring rules.

If you're interested in learning more about Property-Based Testing, you can watch my introduction to Property-based Testing with F# Pluralsight course.

An example of Property-Based Test-Driven Development.

This article is the third in a series of articles that demonstrate how to develop software using types and properties. In the previous article, you saw how to get started with Property-Based Testing, using a Test-Driven Development tactic. In this article, you'll see the previous Tennis Kata example continued. This time, you'll see how to express properties for the state when one of the players have the advantage.

The source code for this article series is available on GitHub.

Winning the game #

When one of the players have the advantage in tennis, the result can go one of two ways: either the player with the advantage wins the ball, in which case he or she wins the game, or the other player wins, in which case the next score is deuce. This implies that you'll have to write at least two properties: one for each situation. Let's start with the case where the advantaged player wins the ball. Using FsCheck, you can express that property like this:

[<Property>]
let ``Given advantage when advantaged player wins then score is correct``
    (advantagedPlayer : Player) =
 
    let actual : Score = scoreWhenAdvantage advantagedPlayer advantagedPlayer
 
    let expected = Game advantagedPlayer
    expected =! actual

As explained in the previous article, FsCheck will interpret this function and discover that it'll need to generate arbitrary Player values for the advantagedPlayer argument. Because illegal states are unrepresentable, you're guaranteed valid values.

This property calls the scoreWhenAdvantage function (that doesn't yet exist), passing advantagedPlayer as argument twice. The first argument is an indication of the current score. The scoreWhenAdvantage function only models how to transition out of the Advantage case. The data associated with the Advantage case is the player currently having the advantage, so passing in advantagedPlayer as the first argument describes the current state to the function.

The second argument is the winner of the ball. In this test case, the same player wins again, so advantagedPlayer is passed as the second argument as well. The exact value of advantagedPlayer doesn't matter; this property holds for all (two) players.

The =! operator is a custom operator defined by Unquote, an assertion library. You can read the expression as expected must equal actual.

In order to pass this property, you can implement the function in the simplest way that could possibly work:

let scoreWhenAdvantage advantagedPlayer winner = Game advantagedPlayer

Here, I've arbitrarily chosen to return Game advantagedPlayer, but as an alternative, Game winner also passes the test.

Back to deuce #

The above implementation of scoreWhenAdvantage is obviously incorrect, because it always claims that the advantaged player wins the game, regardless of who wins the ball. You'll need to describe the other test case as well, which is slightly more involved, yet still easy:

[<Property>]
let ``Given advantage when other player wins then score is correct``
    (advantagedPlayer : Player) =
 
    let actual = scoreWhenAdvantage advantagedPlayer (other advantagedPlayer)
    Deuce =! actual

The first argument to the scoreWhenAdvantage function describes the current score. The test case is that the other player wins the ball. In order to figure out who the other player is, you can call the other function.

Which other function?

The function you only now create for this express purpose:

let other = function PlayerOne -> PlayerTwo | PlayerTwo -> PlayerOne

As the name suggests, this function returns the other player, for any given player. In the previous article, I promised to avoid point-free style, but here I broke that promise. This function is equivalent to this:

let other player = 
    match player with
    | PlayerOne -> PlayerTwo
    | PlayerTwo -> PlayerOne

I decided to place this function in the same module as the scoreWhenGame function, because it seemed like a generally useful function, more than a test-specific function. It turns out that the tennis score module, indeed, does need this function later.

Since the other function is part of the module being tested, shouldn't you test it as well? For now, I'll leave it uncovered by directed tests, because it's so simple that I'm confident that it works, just by looking at it. Later, I can return to it in order to add some properties.

With the other function in place, the new property fails, so you need to change the implementation of scoreWhenAdvantage in order to pass all tests:

let scoreWhenAdvantage advantagedPlayer winner =
    if advantagedPlayer = winner
    then Game winner
    else Deuce

This implementation deals with all combinations of input.

It turned out that, in this case, two properties are all we need in order to describe which tennis score comes after advantage.

To be continued... #

In this article, you saw how to express the properties associated with the advantage state of a tennis game. These properties were each simple. You can express each of them based on any arbitrary input of the given type, as shown here.

Even when all test input values are guaranteed to be valid, sometimes you need to manipulate an arbitrary test value in order to describe a particular test case. You'll see how to do this in the next article.

If you're interested in learning more about Property-Based Testing, you can watch my introduction to Property-based Testing with F# Pluralsight course.

Specify valid state transitions as properties.

This article is the second in a series of articles that demonstrate how to develop software using types and properties. In the previous article, you saw how to design with types so that illegal states are unrepresentable. In this article, you'll see an example of how to express properties for transitions between legal states.

The source code for this article series is available on GitHub.

This article continues the Tennis Kata example from the previous article. It uses FsCheck to generate test values, and xUnit.net as the overall test framework. It also uses Unquote for assertions.

State transitions #

While the types defined in the previous article make illegal states unrepresentable, they don't enforce any rules about how to transition from one state into another. There's yet no definition of what a state transition is, in the tennis domain. Let's make a definition, then.

A state transition should be a function that takes a current Score and the winner of a ball and returns a new Score. More formally, it should have the type Score -> Player -> Score.

(If you're thinking that all this terminology sounds like we're developing a finite state machine, you're bang on; that's exactly the case.)

For a simple domain like tennis, it'd be possible to define properties directly for such a function, but I often prefer to define a smaller function for each case, and test the properties of each of these functions. When you have all these small functions, you can easily combine them into the desired state transition function. This is the strategy you'll see in use here.

Deuce property #

The tennis types defined in the previous article guarantee that when you ask FsCheck to generate values, you will get only legal values. This makes it easy to express properties for transitions. Let's write the property first, and let's start with the simplest state transition: the transition out of deuce.

[<Property>]
let ``Given deuce when player wins then score is correct``
    (winner : Player) =
 
    let actual : Score = scoreWhenDeuce winner
 
    let expected = Advantage winner
    expected =! actual

This test exercises a transition function called scoreWhenDeuce. The case of deuce is special, because there's no further data associated with the state; when the score is deuce, it's deuce. This means that when calling scoreWhenDeuce, you don't have to supply the current state of the game; it's implied by the function itself.

You do need, however, to pass a Player argument in order to state which player won the ball. Instead of coming up with some hard-coded examples, the test simply requests Player values from FsCheck (by requiring the winner function argument).

Because the Player type makes illegal states unrepresentable, you're guaranteed that only valid Player values will be passed as the winner argument.

(In this particular example, Player can only be the values PlayerOne and PlayerTwo. FsCheck will, because of its default settings, run the property function 100 times, which means that it will generate 100 Player values. With an even distribution, that means that it will generate approximately 50 PlayerOne values, and 50 PlayerTwo values. Wouldn't it be easier, and faster, to use a [<Theory>] that deterministically generates only those two values, without duplication? Yes, in this case it would; This sometimes happens, and it's okay. In this example, though, I'm going to keep using FsCheck, because I think this entire example is a good stand-in for a more complex business problem.)

Regardless of the value of the winner argument, the property should hold that the return value of the scoreWhenDeuce function is that the winner now has the advantage.

The =! operator is a custom operator defined by Unquote. You can read it as a must equal operator: expected must equal actual.

Red phase #

When you apply Test-Driven Development, you should follow the Red/Green/Refactor cycle. In this example, we're doing just that, but at the moment the code doesn't even compile, because there's no scoreWhenDeuce function.

In the Red phase, it's important to observe that the test fails as expected before moving on to the Green phase. In order to make that happen, you can create this temporary implementation of the function:

let scoreWhenDeuce winner = Deuce

With this definition, the code compiles, and when you run the test, you get this test failure:

Test 'Ploeh.Katas.TennisProperties.Given deuce when player wins then score is correct' failed: FsCheck.Xunit.PropertyFailedException : 
Falsifiable, after 1 test (0 shrinks) (StdGen (427100699,296115298)):
Original:
PlayerOne

---- Swensen.Unquote.AssertionFailedException : Test failed:

Advantage PlayerOne = Deuce
false

This test failure is the expected failure, so you should now feel confident that the property is correctly expressed.

Green phase #

With the Red phase properly completed, it's time to move on to the Green phase: make the test(s) pass. For deuce, this is trivial:

let scoreWhenDeuce winner = Advantage winner

This passes 'all' tests:

Output from Ploeh.Katas.TennisProperties.Given deuce when player wins then score is correct:
  Ok, passed 100 tests.

The property holds.

Refactor #

When you follow the Red/Green/Refactor cycle, you should now refactor the implementation, but there's little to do at this point

You could, in fact, perform an eta reduction:

let scoreWhenDeuce = Advantage

This would be idiomatic in Haskell, but not quite so much in F#. In my experience, many people find the point-free style less readable, so I'm not going to pursue this type of refactoring for the rest of this article series.

To be continued... #

In this article, you've seen how to express the single property that when the score is deuce, the winner of the next ball will have the advantage. Because illegal states are unrepresentable, you can declaratively state the type of value(s) the property requires, and FsCheck will have no choice but to give you valid values.

In the next article, you'll see how to express properties for slightly more complex state transitions. In this article, I took care to spell out each step in the process, but in the next article, I promise to increase the pace.

If you're interested in learning more about Property-Based Testing, you can watch my introduction to Property-based Testing with F# Pluralsight course.

Design types so that illegal states are unrepresentable.

This article is the first in a series of articles that demonstrate how to develop software using types and properties. In this article, you'll see an example of how to design with algebraic data types, and in future articles, you'll see how to specify properties that must hold for the system. This example uses F#, but you can design similar types in Haskell.

The source code for this article series is available on GitHub.

Tennis #

The example used in this series of articles is the Tennis Kata. Although a tennis match consists of multiple sets that again are played as several games, in the kata, you only have to implement the scoring system for a single game:

• Each player can have either of these points in one game: Love, 15, 30, 40.
• If you have 40 and you win the ball, you win the game. There are, however, special rules.
• If both have 40, the players are deuce.
• If the game is in deuce, the winner of a ball will have advantage and game ball.
• If the player with advantage wins the ball, (s)he wins the game.
• If the player without advantage wins, they are back at deuce.

This problem is easy enough that it's fun to play with, but difficult enough that it's fun to play with.

You can take on this problem in many different ways, but in this article, you'll see how F#'s type system can be used to make illegal states unrepresentable. Perhaps you think this is overkill for such a simple problem, but think of the Tennis Kata as a stand-in for a more complex domain problem.

Players #

In tennis, there are two players, which we can easily model with a discriminated union:

type Player = PlayerOne | PlayerTwo

When designing with types, I often experiment with values in FSI (the F# REPL) to figure out if they make sense. For such a simple type as Player, that's not strictly necessary, but I'll show you anyway, take illustrate the point:

> PlayerOne;;
val it : Player = PlayerOne
> PlayerTwo;;
val it : Player = PlayerTwo
> PlayerZero;;

  PlayerZero;;
  ^^^^^^^^^^

error FS0039: The value or constructor 'PlayerZero' is not defined
> PlayerThree;;

  PlayerThree;;
  ^^^^^^^^^^^

error FS0039: The value or constructor 'PlayerThree' is not defined

As you can see, both PlayerOne and PlayerTwo are values inferred to be of the type Player, whereas both PlayerZero and PlayerThree are illegal expressions.

Not only is it possible to represent all valid values, but illegal values are unrepresentable. Success.

Naive point attempt with a type alias #

If you're unfamiliar with designing with types, you may briefly consider using a type alias to model players' points:

type Point = int

This easily enables you to model some of the legal point values:

> let p : Point = 15;;
val p : Point = 15

> let p : Point = 30;;
val p : Point = 30

It looks good so far, but how do you model love? It's not really an integer.

Still, both players start with love, so it's intuitive to try to model love as 0:

> let p : Point = 0;;
val p : Point = 0

It's a hack, but it works.

Are illegal values unrepresentable? Hardly:

> let p : Point = 42;;
val p : Point = 42

> let p : Point = -1337;;
val p : Point = -1337

With a type alias, it's possible to assign every value that the 'real' type supports. For a 32-bit integer, this means that we have four legal representations (0, 15, 30, 40), and 4,294,967,291 illegal representations of a tennis point. Clearly this doesn't meet the goal of making illegal states unrepresentable.

Second point attempt with a discriminated Union #

If you think about the problem for a while, you're likely to come to the realisation that love, 15, 30, and 40 aren't numbers, but rather labels. No arithmetic is performed on them. It's easy to constrain the domain of points with a discriminated union:

type Point = Love | Fifteen | Thirty | Forty

You can play around with values of this Point type in FSI if you will, but there should be no surprises.

A Point value isn't a score, though. A score is a representation of a state in the game, with (amongh other options) a point to each player. You can model this with a record:

type PointsData = { PlayerOnePoint : Point; PlayerTwoPoint : Point }

You can experiment with this type in FSI, like you can with the other types:

> { PlayerOnePoint = Love; PlayerTwoPoint = Love };;
val it : PointsData = {PlayerOnePoint = Love;
                       PlayerTwoPoint = Love;}
> { PlayerOnePoint = Love; PlayerTwoPoint = Thirty };;
val it : PointsData = {PlayerOnePoint = Love;
                       PlayerTwoPoint = Thirty;}
> { PlayerOnePoint = Thirty; PlayerTwoPoint = Forty };;
val it : PointsData = {PlayerOnePoint = Thirty;
                       PlayerTwoPoint = Forty;}

That looks promising. What happens if players are evenly matched?

> { PlayerOnePoint = Forty; PlayerTwoPoint = Forty };;
val it : PointsData = {PlayerOnePoint = Forty;
                       PlayerTwoPoint = Forty;}

That works as well, but it shouldn't!

Forty-forty isn't a valid tennis score; it's called deuce.

Does it matter? you may ask. Couldn't we 'just' say that forty-forty 'means' deuce and get on with it?

You could. You should try. I've tried doing this (I've done the Tennis Kata several times, in various languages), and it turns out that it's possible, but it makes the code more complicated. One of the reasons is that deuce is more than a synonym for forty-forty. The score can also be deuce after advantage to one of the players. You can, for example, have a score progression like this:

• ...
• Forty-thirty
• Deuce
• Advantage to player one
• Deuce
• Advantage to player two
• Deuce
• ...

While you may prefer to think of the first occurrence of deuce in that list as forty-forty, the next occurrences clearly don't correspond to forty-forty.

Additionally, if you're into Domain-Driven Design, you prefer using the ubiquitous language of the domain. When the tennis domain language says that it's not called forty-forty, but deuce, the code should reflect that.

Final attempt at a point type #

Fortunately, you don't have to throw away everything you've done so far. The love-love, fifteen-love, etc. values that you can represent with the above PointsData type are all valid. Only when you approach the boundary value of forty do problems appear.

A solution is to remove the offending Forty case from Point. The updated definition of Point is this:

type Point = Love | Fifteen | Thirty

You can still represent the 'early' scores using PointsData:

> { PlayerOnePoint = Love; PlayerTwoPoint = Love };;
val it : PointsData = {PlayerOnePoint = Love;
                       PlayerTwoPoint = Love;}
> { PlayerOnePoint = Love; PlayerTwoPoint = Thirty };;
val it : PointsData = {PlayerOnePoint = Love;
                       PlayerTwoPoint = Thirty;}

Additionally, the illegal forty-forty state is now unrepresentable:

> { PlayerOnePoint = Forty; PlayerTwoPoint = Forty };;

  { PlayerOnePoint = Forty; PlayerTwoPoint = Forty };;
  -------------------^^^^^

error FS0039: The value or constructor 'Forty' is not defined

This is much better, apart from the elephant in the room: you also lost the ability to model valid states where only one of the players have forty points:

> { PlayerOnePoint = Thirty; PlayerTwoPoint = Forty };;

  { PlayerOnePoint = Thirty; PlayerTwoPoint = Forty };;
  --------------------------------------------^^^^^

error FS0039: The value or constructor 'Forty' is not defined

Did we just throw the baby out with the bathwater?

Not really, because we weren't close to being done anyway. While we were making progress on modelling the score as a pair of Point values, remaining work includes modelling deuce, advantage and winning the game.

Life begins at forty #

At this point, it may be helpful to recap what we have:

type Player = PlayerOne | PlayerTwo
type Point = Love | Fifteen | Thirty
 
type PointsData = { PlayerOnePoint : Point; PlayerTwoPoint : Point }

While this enables you to keep track of the score when both players have less than forty points, the following phases of a game still remain:

• One of the players have forty points.
• Deuce.
• Advantage to one of the players.
• One of the players won the game.

You can design the first of these with another record type:

type FortyData = { Player : Player; OtherPlayerPoint : Point }

This is a record that specifically keeps track of the situation where one of the players have forty points. The Player element keeps track of which player has forty points, and the OtherPlayerPoint element keeps track of the other player's score. For instance, this value indicates that PlayerTwo has forty points, and PlayerOne has thirty:

> { Player = PlayerTwo; OtherPlayerPoint = Thirty };;
val it : FortyData = {Player = PlayerTwo;
                      OtherPlayerPoint = Thirty;}

This is a legal score. Other values of this type exist, but none of them are illegal.

Score #

Now you have two distinct types, PointsData and FortyData, that keep track of the score at two different phases of a tennis game. You still need to model the remaining three phases, and somehow turn all of these into a single type. This is an undertaking that can be surprisingly complicated in C# or Java, but is trivial to do with a discriminated union:

type Score =
| Points of PointsData
| Forty of FortyData
| Deuce
| Advantage of Player
| Game of Player

This Score type states that a score is a value in one of these five cases. As an example, the game starts with both players at (not necessarily in) love:

> Points { PlayerOnePoint = Love; PlayerTwoPoint = Love };;
val it : Score = Points {PlayerOnePoint = Love;
                         PlayerTwoPoint = Love;}

If, for example, PlayerOne has forty points, and PlayerTwo has thirty points, you can create this value:

> Forty { Player = PlayerOne; OtherPlayerPoint = Thirty };;
val it : Score = Forty {Player = PlayerOne;
                        OtherPlayerPoint = Thirty;}

Notice how both values are of the same type (Score), even though they don't share the same data structure. Other example of valid values are:

> Deuce;;
val it : Score = Deuce
> Advantage PlayerTwo;;
val it : Score = Advantage PlayerTwo
> Game PlayerOne;;
val it : Score = Game PlayerOne

This model of the tennis score system enables you to express all legal values, while making illegal states unrepresentable.

It's impossible to express that the score is seven-eleven:

> Points { PlayerOnePoint = Seven; PlayerTwoPoint = Eleven };;

  Points { PlayerOnePoint = Seven; PlayerTwoPoint = Eleven };;
  --------------------------^^^^^

error FS0039: The value or constructor 'Seven' is not defined

It's impossible to state that the score is fifteen-thirty-fifteen:

> Points { PlayerOnePoint = Fifteen; PlayerTwoPoint = Thirty; PlayerThreePoint = Fifteen };;

  Points { PlayerOnePoint = Fifteen; PlayerTwoPoint = Thirty; PlayerThreePoint = Fifteen };;
  ------------------------------------------------------------^^^^^^^^^^^^^^^^

error FS1129: The type 'PointsData' does not contain a field 'PlayerThreePoint'

It's impossible to express that both players have forty points:

> Points { PlayerOnePoint = Forty; PlayerTwoPoint = Forty };;

  Points { PlayerOnePoint = Forty; PlayerTwoPoint = Forty };;
  --------------------------^^^^^

error FS0001: This expression was expected to have type
    Point    
but here has type
    FortyData -> Score    
> Forty { Player = PlayerOne; OtherPlayerPoint = Forty };;

  Forty { Player = PlayerOne; OtherPlayerPoint = Forty };;
  -----------------------------------------------^^^^^

error FS0001: This expression was expected to have type
    Point    
but here has type
    FortyData -> Score

In the above example, I even attempted to express forty-forty in two different ways, but none of them work.

Summary #

You now have a model of the domain that enables you to express valid values, but that makes illegal states unrepresentable. This is half the battle won, without any moving parts. These types govern what can be stated in the domain, but they don't provide any rules for how values can transition from one state to another.

This is a task you can take on with Property-Based Testing. Since all values of these types are valid, it's easy to express the properties of a tennis game score. In the next article, you'll see how to start that work.

If you're interested in learning more about designing with types, you can watch my Type-Driven Development with F# Pluralsight course.

Combine a strong type system with Property-Based Testing to specify software.

When Kent Beck rediscovered Test-Driven Development (TDD) some twenty years ago, the original context was SmallTalk programming. When the concept of TDD began to catch on, it seemed to me to proliferate particularly in dynamic language communities like Python and Ruby.

It makes sense that if you can't get fast feedback from a compilation step, you seek another way to get feedback on your work. Unit testing is such a fast feedback mechanism. Watching the NodeJS community from the side, it always seemed to me that TDD is an integral way of working with that stack. This makes sense.

This also explains why e.g. C# programmers were more reluctant to adopt TDD. That your code compiles gives a smidgen of confidence.

C# and Java programmers may joke that if it compiles, it works, but also realise that that's all it is: a joke. Automated testing adds another layer of safety on top of compilation. On the other hand, you may get by with writing fewer tests than in a dynamic language, because the static type system does provide some guarantees.

What if you had a stronger type system than what C# or Java provides? Then you'd have to write even fewer tests.

Type spectrum #

It can be useful to think about typing as a spectrum.

To the left, we have dynamically typed languages like JavaScript and Ruby. Python can be compiled, and Clojure is compiled, so we can think of them as being a little closer to the middle. Purists would want to point out that whether or not a language is compiled and how statically typed it is are two independent concerns, but the point of this spectrum is to illustrate the degree of confidence the type system gives you.

Java and C# are statically typed, compiled languages, but a lot of things can still go wrong at run-time. Just consider all the null pointer exceptions you've encountered over the years.

Further to the right are languages with Hindley–Milner type systems, such as F# and Haskell. These offer more safety from static typing alone. Such types are the subject of this and future articles.

I've put Haskell a bit to the right of F# because it has higher-order types. To the right of Haskell sits dependently-typed languages like Idris. To the far right, we have a hypothetical language with such a strong type system that, indeed, if it compiles, it works. As far as I'm aware, no such language exist.

Creating software with Hindley-Milner type systems #

It turns out that when you shift from a Java/C#-style type system to the stronger type system offered by F# or Haskell, you can further shift your design emphasis towards designing with types. You still need to cover behaviour with automated tests, but fewer are necessary.

With the algebraic data types available in F# or Haskell, you can design your types so that illegal states are unrepresentable. In other words, all values of a particular type are guaranteed to be valid within the domain they model. This makes it much easier to test the behaviour of your system with Property-Based Testing, because you can declaratively state that you want your Property-Based Testing framework (FsCheck, QuickCheck, etc.) to provide random values of a given type. The framework will give you random values, but it can only give you valid values.

In this series of articles, you'll see an example of this in F#:

• Types + Properties = Software: designing with types
• Types + Properties = Software: state transition properties
• Types + Properties = Software: properties for the advantage state
• Types + Properties = Software: properties for the Forties
• Types + Properties = Software: composition
• Types + Properties = Software: initial state
• Types + Properties = Software: finite state machine
• Types + Properties = Software: other properties

If you're interested in learning more, my Type Driven Development article showcases another example of designing with types. My Pluralsight course Type-Driven Development with F# dives even deeper than the article. If you need an introduction to Property-based Testing with F#, that's also available.

Summary #

The stronger a language's type system is, the more you can use static types to model your application's problem domain. With a sufficiently strong type system, you can make illegal states unrepresentable. While states are guaranteed to be legal, transitions between states need not be. You can often use Property-Based Testing to ensure that the state transitions are correct. The combination of types and properties give you a simple, but surprisingly powerful way of specifying the behaviour of the software you create.

Have you ever asked your music player to shuffle all your music, only to wonder: didn't it play that song only yesterday?

When I work, I often listen to music. Sometimes, I make a deliberate choice, but often, I just ask my music player to shuffle my entire music library.

It invariably happens that it plays a song it played only a couple of days before; I often notice when it's a song I don't like, because then it annoys me that it plays that stupid song again. Given that I have more than 16,000 tracks, and approximately 5,000 tracks on my laptop, it seems unlikely that the music player should pick the same track within only a few days.

This is a well-known phenomenon known as frequency illusion, or more colloquially as the Baader-Meinhof Phenomenon. Your brain seeks patterns, even where no patterns exist. This is a really strong feeling, it turns out.

When tracks are played in truly random fashion, it's as unlikely that it should play two tracks far apart as it should play them close together. Therefore, many media players come with shuffle algorithms that are not random, but designed to feel random.

With my thousands of tracks, I couldn't shake the feeling that my player's shuffle algorithm was one of those non-random algorithms, so I decided to analyse my plays.

Getting the data in shape #

Fortunately, I've been scrobbling my plays to Last.fm since 2007, so I had comprehensive statistics to work with.

There's a third-party service where you can download all your Last.fm scrobbles as a CSV file, so I did that; all 53,700 scrobbles.

This file contains all my scrobbles since 2007, but I had to clean it up:

• I haven't used the same music player in all those years, so I decide to only look at the entries since January 1, 2014. I know I've only used one player in that period.
• It often happens that I put on a particular artist, album, or playlist, and I had to remove those, because I wanted to look at only the entries when I was listening in shuffle mode.

Opening the file in Excel, and manually cleaning it up according to the above criteria was easy, and took perhaps 15 minutes. What was left was approximately 8,500 rows in a CSV file.

Analysing with F# #

Next, I created an F# script file, and read in the file's contents:

open System
open System.IO
 
type Track = { Artist : string; Album : string; Name : string }
 
type Scrobble =
    { Track : Track; Time : string }
 
let parse (line : string) =
    match line.Split '|' with
    | [| artist; album; track; time |] ->
        Some {
            Track = { Artist = artist; Album = album; Name = track }
            Time = time }
    | _ -> None
 
let scrobbles =
    File.ReadAllLines @"Last.fm_ploeh_shuffled.csv"
    |> Array.map parse

This script reads the file, with each line an element in an array. It then parses each line into Scrobble values. There may be parse errors, if a line contains the wrong number of elements, but this turned out to not be the case:

> let hasParseErrors = scrobbles |> Array.exists (Option.isNone);;
val hasParseErrors : bool = false

The next step was to group the scrobbles into distinct tracks, with a count of each track:

let counts =
    scrobbles
    |> Array.choose id
    |> Array.countBy (fun s -> s.Track)
    |> Array.sortByDescending snd

This gave me a sorted 'hit list', showing me the songs played the most in the top of the list. Here's the top 10:

DJ Zen, Peace Therapy, Anamatha (Intro)                                : .......
Abakus, That Much Closer to the Sun, Igmatik                           : .......
Yoji Biomehanika, Technicolor Nrg Show, seduction (sleep tonight remix): ......
Mindsphere, Patience for Heaven. CD 2: Inner Cyclone, inner cyclone    : ......
Massive Attack, Mezzanine, Black Milk                                  : ......
Dimension 5, TransAddendum, Strange Phenomena                          : ......
Dire Straits, Brothers in Arms, Your Latest Trick                      : ......
Digicult, Out Of This World, Star Travel                               : ......
Infected Mushroom, Classical Mushroom, Bust A Move                     : ......
Brother Brown feat. Frank'ee, Under The Water, Under The Water (Or[...]: ......

None of these, with the exception of Under The Water, are particular favourites of mine, so I don't think these were tracks I'd definitely selected; remember: I'd made a deliberate effort to remove such tracks before starting the analysis.

This list tells me something, because I know what I like and don't like, but it doesn't tell me much about the distribution of tracks. The two most 'popular' tracks had been played 7 times over the last two years, and the remaining tracks 6 times. How about the other 5,155 entries in counts? How were they distributed?

It's easy to count how many tracks were played 7 times, how many were played 6 times, 5 times, etc.:

> let frequencyCounts = counts |> Array.countBy snd;;

val frequencyCounts : (int * int) [] =
  [|(7, 2); (6, 9); (5, 43); (4, 159); (3, 561); (2, 1475); (1, 2916)|]

It looks as though the 'popular' tracks are rare occurrences. Most tracks (2,916) were played only once, and 1,475 only twice. This is perhaps easier to understand when visualised.

Visualisation #

While there are great visualisation packages for F#, for this ad-hoc task, I found it easier to use Excel. After all, I only had 7 observations to plot:

This figure shows that almost 3,000 tracks were scrobbled only once, approximately 1,500 were scrobbled twice, 500 or so were scrobbled thrice, and so on.

Even if we expect the distribution to be entirely uniform, we should expect to see duplicates. While I have more than 16,000 tracks on my home system, I only have some 5,000 tracks on my laptop, and these are the tracks for which I have data. Since I had 8,500 scrobbles to analyse, there must be duplicates, but we shouldn't expect to see two plays being more common than one, because even with an even distribution, you can't play all tracks twice when you have 5,000 tracks, but 'only' 8,500 plays.

That there are some 500 tracks that have been played three times don't seem unlikely in this light. Furthermore, outliers are to be expected as well; while they're there, the figure also shows that they promptly taper off to insignificance.

Although I took theoretical statistics in university (I had to), I never liked it, and got the lowest passing grade. In other words: don't trust any of this. I haven't formally analysed it with proper statistical tools.

Conclusion #

Still, based on this little Friday exercise, I now feel renewed confidence that my music player does, indeed, pick tracks at random when I tell it to play all songs shuffled.

Pre-conditions are important in Property-Based Tests.

Last week, I was giving a workshop on Property-Based Testing, and we were looking at this test:

[<Property>]
let ``Validate.reservation returns right result on invalid date``
    (rendition : ReservationRendition) =
    
    let actual = Validate.reservation rendition
 
    let expected : Result<Reservation, Error> =
        Failure(ValidationError("Invalid date."))
    test <@ expected = actual @>

The test case being exercised by this test is to verify what happens when the input (essentially a representation of an incoming JSON document) is invalid.

The System Under Test is this function:

module Validate =
    let reservation (rendition : ReservationRendition) =
        match rendition.Date |> DateTimeOffset.TryParse with
        | (true, date) -> Success {
            Date = date
            Name = rendition.Name
            Email = rendition.Email
            Quantity = rendition.Quantity }
        | _ -> Failure(ValidationError "Invalid date.")

The validation rule is simple: if the rendition.Date string can be parsed into a DateTimeOffset value, then the input is valid; otherwise, it's not.

If you run the test, if passes:

Output from Ploeh.Samples.BookingApi.UnitTests.ValidatorTests.Validate.reservation returns right result on invalid date:
  Ok, passed 100 tests.

Only, this test isn't guaranteed to pass. Can you spot the problem?

There's a tiny, but real, risk that the randomly generated rendition.Date string can be parsed as a DateTimeOffset value. While it's not particularly likely, it will happen once in a blue moon. This can lead to spurious false positives.

In order to see this, you can increase the number of test cases generated by FsCheck:

[<Property(MaxTest = 100000)>]
let ``Validate.reservation returns right result on invalid date``
    (rendition : ReservationRendition) =
    
    let actual = Validate.reservation rendition
 
    let expected : Result<Reservation, Error> =
        Failure(ValidationError("Invalid date."))
    test <@ expected = actual @>

In my experience, when you ask for 100,000 test cases, the property usually fails:

Test 'Ploeh.Samples.BookingApi.UnitTests.ValidatorTests.Validate.reservation returns right result on invalid date' failed:
	FsCheck.Xunit.PropertyFailedException : 
Falsifiable, after 9719 tests (11 shrinks) (StdGen (1054829489,296106988)):
Original:
{Date = "7am";
 Name = "6WUx;";
 Email = "W";
 Quantity = -5;}
Shrunk:
{Date = "7am";
 Name = "";
 Email = "";
 Quantity = 0;}

---- Swensen.Unquote.AssertionFailedException : Test failed:

Failure (ValidationError "Invalid date.") = Success {Date = 15.01.2016 07:00:00 +00:00;
         Name = "";
         Email = "";
         Quantity = 0;}
false

The problem is that the generated date "7am" can be parsed as a DateTimeOffset value:

> open System;;
> DateTimeOffset.Now;;
val it : DateTimeOffset =
  15.01.2016 21:09:25 +00:00
> "7am" |> DateTimeOffset.TryParse;;
val it : bool * DateTimeOffset =
  (true, 15.01.2016 07:00:00 +00:00)

The above test is written with the implicit assumption that the generated value for rendition.Date will always be an invalidly formatted string. As the Zen of Python reminds us, explicit is better than implicit. You should make that assumption explicit:

[<Property>]
let ``Validate.reservation returns right result on invalid date``
    (rendition : ReservationRendition) =
    not(fst(DateTimeOffset.TryParse rendition.Date)) ==> lazy
    
    let actual = Validate.reservation rendition
 
    let expected : Result<Reservation, Error> =
        Failure(ValidationError("Invalid date."))
    test <@ expected = actual @>

This version of the test uses FsCheck's built-in custom operator ==>. This operator will only evaluate the expression on the right-hand side if the boolean expression on the left-hand side evaluates to true. In the unlikely event that the above condition evaluates to false, FsCheck is going to ignore that randomly generated value, and try with a new one.

This version of the test succeeds, even if you set MaxTest to 1,000,000.

The ==> operator effectively discards candidate values that don't match the 'guard' condition. You shouldn't always use this feature to constrain the input, as it can be wasteful. If the condition isn't satisfied, FsCheck will attempt to generate a new value that satisfies the condition. In this particular example, only in extremely rare cases will FsCheck be forced to discard a candidate value, so this use of the feature is appropriate.

In other cases, you should consider other options. Imagine that you want only even numbers. While you could write a 'guard' condition that ensures that only even numbers are used, that would cause FsCheck to throw away half of the generated candidates. In such cases, you should instead consider defining a custom Arbitrary, using FsCheck's API.

Another discussion entirely is whether the current behaviour is a good idea. If we consider tests as a feedback mechanism about software design, then perhaps we should explicitly specify the expected format. At the moment, the implementation is an extremely Tolerant Reader (because DateTimeOffset.TryParse is a Tolerant Reader). Perhaps it'd make sense to instead use TryParseExact. That's an API modelling decision, though, and might have to involve various other stakeholders than only programmers.

If you wish to learn more about Property-Based Testing with FsCheck, consider watching my Pluralsight course.

Tips on refactoring recursive functions to tail-recursive functions.

In a recent article, I described how to refactor an imperative loop to a recursive function. If you're coming from C# or Java, however, you may have learned to avoid recursion, since it leads to stack overflows when the recursion is too deep.

In some Functional languages, like F# and Haskell, such stack overflows can be prevented with tail recursion. If the last function call being made is a recursive call to the function itself, the current stack frame can be eliminated because execution is effectively completed. This allows a tail-recursive function to keep recursing without ever overflowing.

When you have a recursive function that's not tail recursive, however, it can sometimes be difficult to figure out how to refactor it so that it becomes tail recursive. In this article, I'll outline some techniques I've found to be effective.

Introduce an accumulator #

It seems as though the universal trick related to recursion is to introduce an accumulator argument. This is how you refactor an imperative loop to a recursive function, but it can also be used to make a non-tail-recursive function tail recursive. This will also require you to introduce an 'implementation function' that does the actual work.

Example: discarding candidate points when finding a convex hull #

In previous articles I've described various problems I had when implementing the Graham Scan algorithm to find the convex hull of a set of points.

One of my functions examined the three last points in a sequence of points in order to determine if the next-to-last point is in the interior of the set, or if that point could potentially be on the hull. If the point is positively known to be in the interior of the set, it should be discarded. At one stage, the function was implemented this way:

let tryDiscard points =
    let rec tryDiscardImp = function
        | [p1; p2; p3] when turn p1 p2 p3 = Direction.Right -> [p1; p3]
        | [p1; p2; p3] -> [p1; p2; p3]
        | p :: ps -> p :: tryDiscardImp ps
        | [] -> []
    let newPoints = tryDiscardImp points
    if newPoints.Length <> points.Length
    then Some newPoints
    else None

This function was earlier called check, which is the name used in the article about refactoring to recursion. The tryDiscard function is actually an inner function in a more complex function that's defined with the inline keyword, so the type of tryDiscard is somewhat complicated, but think of it as having the type (int * int) list -> (int * int) list option. If a point was discarded, the new, reduced list of points is returned in a Some case; otherwise, None is returned.

The tryDiscard function already has an 'implementation function' called tryDiscardImp, but while tryDiscardImp is recursive, it isn't tail recursive. The problem is that in the p :: ps case, the recursive call to tryDiscardImp isn't the tail call. Rather, the stack frame has to wait for the recursive call tryDiscardImp ps to complete, because only then can it cons p onto its return value.

Since an 'implementation function' already exists, you can make it tail recursive by adding an accumulator argument to tryDiscardImp:

let tryDiscard points =
    let rec tryDiscardImp acc = function
        | [p1; p2; p3] when turn p1 p2 p3 = Direction.Right ->
            acc @ [p1; p3]
        | [p1; p2; p3] -> acc @ [p1; p2; p3]
        | p :: ps -> tryDiscardImp (acc @ [p]) ps
        | [] -> acc
    let newPoints = tryDiscardImp [] points
    if newPoints.Length <> points.Length
    then Some newPoints
    else None

As you can see, I added the acc argument to tryDiscardImp; it has the type (int * int) list (again: not really, but close enough). Instead of returning from each case, the tryDiscardImp function now appends points to acc until it reaches the end of the list, which is when it returns the accumulator. The p :: ps case now first appends the point in consideration to the accumulator (acc @ [p]), and only then recursively calls tryDiscardImp. This puts the call to tryDiscardImp in the tail position.

The repeated use of the append operator (@) is terribly inefficient, though, but I'll return to this issue later in this article. For now, let's take a step back.

Example: implementing map with recursion #

A common exercise for people new to Functional Programming is to implement a map function (C# developers will know it as Select) using recursion. This function already exists in the List module, but it can be enlightening to do the exercise.

An easy, but naive implementation is only two lines of code, using pattern matching:

let rec mapNaive f = function
    | [] -> []
    | h::t -> f h :: mapNaive f t

Is mapNaive tail recursive? No, it isn't. The last operation happening is that f h is consed unto the return value of mapNaive f t. While mapNaive f t is a recursive call, it's not in the tail position. For long lists, this will create a stack overflow.

How can you create a tail-recursive map implementation?

Example: inefficient tail-recursive map implementation #

According to my introduction, adding an accumulator and an 'implementation' function should do the trick. Here's the straightforward application of that technique:

let mapTailRecursiveUsingAppend f xs =
    let rec mapImp f acc = function
        | [] -> acc
        | h::t -> mapImp f (acc @ [f h]) t
    mapImp f [] xs

The mapImp function does the actual work, and it's tail recursive. It appends the result of mapping the head of the list unto the accumulator: acc @ [f h]. Only then does it recursively call itself with the new accumulator and the tail of the list.

While this version is tail recursive, it's horribly inefficient, because appending to the tail of a (linked) list is inefficient. In theory, this implementation would never result in a stack overflow, but the question is whether anyone has the patience to wait for that to happen?

> mapTailRecursiveUsingAppend ((*) 2) [1..100000];;
Real: 00:02:46.104, CPU: 00:02:44.750, GC gen0: 13068, gen1: 6380, gen2: 1
val it : int list =
  [2; 4; 6; 8; 10; 12; 14; 16; 18; 20; 22; 24; 26; 28; 30; 32; 34; 36; ...]

Doubling 100,000 integers this way takes nearly 3 minutes on my (admittedly mediocre) laptop. A better approach is required.

Example: efficient tail-recursive map implementation #

The problem with mapTailRecursiveUsingAppend is that appending to a list is slow when the left-hand list is long. This is because lists are linked lists, so the append operation has to traverse the entire list and copy all the element to link to the right-hand list.

Consing a single item unto an existing list, on the other hand, is efficient:

let mapTailRecursiveUsingRev f xs =
    let rec mapImp f acc = function
        | [] -> acc
        | h::t -> mapImp f (f h :: acc) t
    mapImp f [] xs |> List.rev

This function conses unto the accumulator (f h :: acc) instead of appending to the accumulator. The only problem with this is that acc is in reverse order compared to the input, so the final step must be to reverse the output of mapImp. While there's a cost to reversing a list, you pay it only once. In practice, it turns out to be efficient:

> mapTailRecursiveUsingRev ((*) 2) [1..100000];;
Real: 00:00:00.017, CPU: 00:00:00.015, GC gen0: 1, gen1: 0, gen2: 0
val it : int list =
  [2; 4; 6; 8; 10; 12; 14; 16; 18; 20; 22; 24; 26; 28; 30; 32; 34; 36; ...]

From nearly three minutes to 17 milliseconds! That's a nice performance improvement.

The only problem, from a point of view where learning is in focus, is that it feels a bit like cheating: we've delegated an important step in the algorithm to List.rev. If we think it's OK to use the library functions, we could have directly used List.map. The whole point of this exercise, however, is to learn something about how to write tail-recursive functions.

At this point, we have two options:

• Learn how to write an efficient, tail-recursive implementation of rev.
• Consider alternatives.

Ultimately, it turns out that List.rev is implemented in a fashion similar to above, using an 'implementation function' and an accumulator. Let us, therefore, turn our attention to another alternative.

Example: efficient tail-recursive map using a difference list #

The mapTailRecursiveUsingAppend function is attractive because of its simplicity. If only there was an efficient way to append a single item to the tail of a (long) list, like acc appendSingle (f h)! (appendSingle is a hypothetical function that we wish existed.)

So far, we've treated data as data, and functions as functions, but in Functional Programming, functions are data as well!

What if we could partially apply a cons operation?

Unfortunately, the cons operator (::) can't be used as a function, so you'll have to introduce a little helper function:

// 'a -> 'a list -> 'a list
let cons x xs = x :: xs

This enables you to partially apply a cons operation:

> cons 1;;
val it : (int list -> int list) = <fun:it@4-5>

The expression cons 1 is a function that awaits an int list argument. You can, for example, call it with the empty list, or another list:

> (cons 1) [];;
val it : int list = [1]
> (cons 1) [2];;
val it : int list = [1; 2]

That hardly seems useful, but what happens if you start composing such partially applied functions?

> cons 1 >> cons 2;;
val it : (int list -> int list) = <fun:it@7-8>

Notice that the result is another function with the same signature as cons 1. A way to read it is: cons 1 is a function that takes a list as input, appends the list after 1, and returns that new list. The return value of cons 1 is passed to cons 2, which takes that input, appends that list after 2, and returns that list. Got it? Try it out:

> (cons 1 >> cons 2) [];;
val it : int list = [2; 1]

Not what you expected? Try going through the data flow again. The input is the empty list ([]), which, when applied to cons 1 produces [1]. That value is then passed to cons 2, which puts 2 at the head of [1], yielding the final result of [2; 1].

This still doesn't seem to help, because it still reverses the list. True, but you can reverse the composition:

> (cons 2 >> cons 1) [];;
val it : int list = [1; 2]
> (cons 1 << cons 2) [];;
val it : int list = [1; 2]

Notice that in the first line, I reversed the composition by changing the order of partially applied functions. This, however, is equivalent to keeping the order, but using the reverse composition operator (<<).

You can repeat this composition:

> (cons 1 << cons 2 << cons 3 << cons 4) [];;
val it : int list = [1; 2; 3; 4]

That's exactly what you need, enabling you to write acc << (cons (f h)) in order to efficiently append a single element to the tail of a list!

let mapTailRecursiveUsingDifferenceList f xs =
    let cons x xs = x :: xs
    let rec mapImp f acc = function
        | [] -> acc []
        | h::t -> mapImp f (acc << (cons (f h))) t
    mapImp f id xs

This implementation of map uses this technique, introduced by John Hughes in 1985. Real World Haskell calls the technique a difference list, without explaining why.

This mapImp function's accumulator is no longer a list, but a function. For every item, it composes a new accumulator function from the old one, effectively appending the mapped item to the tail of the accumulated list. Yet, because acc isn't a list, but rather a function, the 'append' operation doesn't trigger a list traversal.

When the recursive function finally reaches the end of the list (the [] case), it invokes the acc function with the empty list ([]) as the initial input.

This implementation is also tail recursive, because the accumulator is being completely composed (acc << (cons (f h))) before mapImp is recursively invoked.

Is it efficient, then?

> mapTailRecursiveUsingDifferenceList ((*) 2) [1..100000];;
Real: 00:00:00.024, CPU: 00:00:00.031, GC gen0: 1, gen1: 0, gen2: 0
val it : int list =
  [2; 4; 6; 8; 10; 12; 14; 16; 18; 20; 22; 24; 26; 28; 30; 32; 34; 36; ...]

24 milliseconds is decent. It's not as good as mapTailRecursiveUsingRev (17 milliseconds), but it's close.

In practice, you'll probably find that mapTailRecursiveUsingRev is not only more efficient, but also easier to understand. The advantage of using the difference list technique, however, is that now mapImp has a shape that almost screams to be refactored to a fold.

Example: implementing map with fold #

The mapImp function in mapTailRecursiveUsingDifferenceList almost has the shape required by the accumulator function in List.fold. This enables you to rewrite mapImp using fold:

let mapUsingFold f xs =
    let cons x xs = x :: xs
    let mapImp = List.fold (fun acc h -> acc << (cons (f h))) id
    mapImp xs []

As usual in Functional Programming, the ultimate goal seems to be to avoid writing recursive functions after all!

The mapUsingFold function is as efficient as mapTailRecursiveUsingDifferenceList:

> mapUsingFold ((*) 2) [1..100000];;
Real: 00:00:00.025, CPU: 00:00:00.031, GC gen0: 2, gen1: 1, gen2: 1
val it : int list =
  [2; 4; 6; 8; 10; 12; 14; 16; 18; 20; 22; 24; 26; 28; 30; 32; 34; 36; ...]

Not only does 25 milliseconds seem fast, but it's also comparable with the performance of the built-in map function:

> List.map ((*) 2) [1..100000];;
Real: 00:00:00.011, CPU: 00:00:00.015, GC gen0: 0, gen1: 0, gen2: 0
val it : int list =
  [2; 4; 6; 8; 10; 12; 14; 16; 18; 20; 22; 24; 26; 28; 30; 32; 34; 36; ...]

Granted, List.map seems to be twice as fast, but it's also been the subject of more scrutiny than the above fun exercise.

Summary #

In Functional Programming, recursive functions take the place of imperative loops. In order to be efficient, they must be tail recursive.

You can make a function tail recursive by introducing an accumulator argument to an 'implementation function'. This also tends to put you in a position where you can ultimately refactor the implementation to use a fold instead of explicit recursion.

---

Comments

When you build a system from small functions that you subsequently compose, how do you know that the composition works? Integration testing is one option.

Despite its reputation as a niche language for scientific or finance computing, F# is a wonderful language for 'mainstream' software development. You can compose applications from small, inherently testable functions.

Composition #

Once you have your functions as building blocks, you compose them. This is best done in an application's Composition Root - no different from Dependency Injection in Object-Oriented Programming.

In my (free) Build Stuff talk on Functional TDD with F# (expanded version available on Pluralsight), I demonstrate how to compose such a function:

let imp =
    Validate.reservation
    >> bind (Capacity.check 10 (SqlGateway.getReservedSeats connectionString))
    >> map (SqlGateway.saveReservation connectionString)

How can you be sure that this composition is correct?

Integration Testing #

The answer to that question isn't different from its Object-Oriented counterpart. When you implement small building blocks, you can test them. Call these small building blocks units, and it should be clear that such tests are unit tests. It doesn't matter if units are (small) classes or functions.

Unit testing ought to give you confidence that each unit behaves correctly, but unit tests don't tell you how they integrate. Are there issue that only surface when units interact? Are units correctly composed?

In my experience, you can develop entire systems based exclusively on unit tests, and the final application can be stable and sturdy without the need for further testing. This depends on circumstances, though. In other cases, you need further testing to gain confidence that the application is correctly composed from its building blocks.

You can use a small set of integration tests for that.

Example #

In my Outside-In Test-Driven Development Pluralsight course, I demonstrate how to apply the GOOS approach to an HTTP API built with ASP.NET Web API. One of the techniques I describe is how to integration test the API against its HTTP boundary.

In that course, you learn how to test an API implemented in C#, but since the tests are made against the HTTP boundary, the implementation language doesn't matter. Even so, you can also write the tests themselves in F#. Here's an example that exercises the Controller that uses the above imp function:

[<Fact; UseDatabase>]
let ``Post returns success`` () =
    use client = createClient()
 
    let json =
        ReservationJson.Root("2014-10-21", "Mark Seemann", "x@example.com", 4)
    let response = client.PostAsJsonAsync("reservations", json).Result
 
    test <@ response.IsSuccessStatusCode @>

This test creates a new HttpClient object called client. It then creates a JSON document with some reservation data, and POSTs it to the reservations resource. Finally, it verifies that the response indicated a success.

The ReservationJson type was created from a sample JSON document using the JSON Type Provider. The createClient function is a bit more involved, but follows the same recipe I describe in my course:

let createClient () =
    let baseAddress = Uri "http://localhost:8765"
    let config = new HttpSelfHostConfiguration(baseAddress)
    configure connStr config
    config.IncludeErrorDetailPolicy <- IncludeErrorDetailPolicy.Always
    let server = new HttpSelfHostServer(config)
    let client = new HttpClient(server)
    client.BaseAddress <- baseAddress
    client

The (impure) configure function is a function defined by the application implementation. Among many other things, it creates the above imp composition. When the test passes, you can trust that imp is correctly composed.

Smoke Testing #

You may already have noticed that the ``Post returns success`` test is course-grained and vague. It doesn't attempt to make strong assertions about the posterior state of the system; if the response indicates success, the test passes.

The reason for this is that all important behaviour is already covered by unit tests.

• Is the response specifically a 201 (Created) response? Covered by unit tests.
• Does the response have a Location header indicating the address of a newly created resource? Covered by unit test.
• What happens if the input is malformed? Covered by unit tests.
• What happens if the system can't accept the request due to business rules? Covered by unit tests.
• ...and so on.

The purpose of the integration test isn't to instil confidence in the implementation; the purpose is to give you confidence that the application is correctly integrated (hence the name). In my experience, a few Smoke Tests are enough to achieve that goal.

Specifically, it has been my experience that the most common integration issues are related to various configuration errors:

• Missing configuration values
• Wrong configuration values
• Network errors
• Security errors
• ... etc.

Common to most of such errors is that they tend to manifest themselves uniformly. For example, in a database-driven application, if the database server is unreachable, nothing works. Therefore, only a single Smoke Test is required in order to tell you whether the application can reach the server or not.

In other words: you should have a legion of unit tests covering specific behaviour, and a few integration tests covering common integration issues. You may already have recognised this principle as the Test Pyramid.

Summary #

In this article, you saw an example of an integration test against an HTTP API, written in F#. The principle is universal, though. You can compose applications from units. These units can be functions written in F#, or Haskell, or Scala, or they can be classes written in C#, Java, Python, and so on. Composition can be done on functions, or on objects using Dependency Injection.

In all of these cases, you can cover the units with unit tests. Issues with composition can be screened by a few smoke tests at the integration level.