The Tennis kata revisited by Mark Seemann

When you need discriminated unions, but all you have are objects.

After I learned that the Visitor design pattern is isomorphic to sum types (AKA discriminated unions), I wanted to try how easy it is to carry out a translation in practice. For that reason, I decided to translate my go-to F# implementation of the Tennis kata to C#, using the Visitor design pattern everywhere I'd use a discriminated union in F#.

The resulting C# code shows that it is, indeed, possible to 'mechanically' translate discriminated unions to the Visitor design pattern. Given that the Visitor pattern requires multiple interfaces and classes to model just a single discriminated union, it's no surprise that the resulting code is much more complex. As a solution to the Tennis kata itself, all this complexity is unwarranted. On the other hand, as an exercise in getting by with the available tools, it's quite illustrative. If all you have is C# (or a similar language), but you really need discriminated unions, the solution is ready at hand. It'll be complex, but not complicated.

The main insight of this exercise is that translating any discriminated union to a Visitor is, indeed, possible. You can best internalise such insights, however, if you actually do the work yourself. Thus, in this article, I'll only show a few highlights from my own exercise. I highly recommend that you try it yourself.

Typical F# solution #

You can see my typical F# solution in great detail in my article series Types + Properties = Software. To be clear, there are many ways to implement the Tennis kata, even in F#, and the one shown in the articles is neither overly clever nor too boring. As implementations go, this one is quite pedestrian.

My emphasis with that kind of solution to the Tennis kata is on readability, correctness, and testability. Going for a functional architecture automatically addresses the testability concern. In F#, I endeavour to use the excellent type system to make illegal states unrepresentable. Discriminated unions are essential ingredients in that kind of design.

In F#, I'd typically model a Tennis game score as a discriminated union like this:

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

That's not the only discriminated union involved in the implementation. Player is also a discriminated union, and both PointsData and FortyData compose a third discriminated union called Point:

type Point = Love | Fifteen | Thirty

Please refer to the older article for full details of the F# 'domain model'.

This was the sort of design I wanted to try to translate to C#, using the Visitor design pattern in place of discriminated unions.

Player #

In F# you must declare all types and functions before you can use them. To newcomers, this often looks like a constraint, but is actually one of F#'s greatest strengths. Since other types transitively use the Player discriminated union, this is the first type you have to define in an F# code file:

type Player = PlayerOne | PlayerTwo

This one is fairly straightforward to translate to C#. You might reach for an enum, but those aren't really type-safe in C#, since they're little more than glorified integers. Using a discriminated union is safer, so define a Visitor:

public interface IPlayerVisitor<T>
{
    T VisitPlayerOne();
 
    T VisitPlayerTwo();
}

A Visitor interface is where you enumerate the cases of the discriminated union - in this example player one and player two. You can idiomatically prefix each method with Visit as I've done here, but that's optional.

Once you've defined the Visitor, you can declare the 'actual' type you're modelling: the player:

public interface IPlayer
{
    T Accept<T>(IPlayerVisitor<T> visitor);
}

Those are only the polymorphic types required to model the discriminated union. You also need to add concrete classes for each of the cases. Here's PlayerOne:

public struct PlayerOne : IPlayer
{
    public T Accept<T>(IPlayerVisitor<T> visitor)
    {
        return visitor.VisitPlayerOne();
    }
}

This is an example of the Visitor pattern's central double dispatch mechanism. Clients of the IPlayer interface will dispatch execution to the Accept method, which again dispatches execution to the visitor.

I decided to make PlayerOne a struct because it holds no data. Perhaps I also ought to have sealed it, or, as Design Patterns likes to suggest, make it a Singleton.

Hardly surprising, PlayerTwo looks almost identical to PlayerOne.

Apart from a single-case discriminated union (which is degenerate), a discriminated union doesn't get any simpler than Player. It has only two cases and carries no data. Even so, it takes four types to translate it to a Visitor: two interfaces and two concrete classes. This highlights how the Visitor pattern adds significant complexity.

And it only gets worse with more complex discriminated unions.

Score #

I'm going to leave the translation of Point as an exercise. It's similar to the translation of Player, but instead of two cases, it enumerates three cases. Instead, consider how to enumerate the cases of Score. First, add a Visitor:

public interface IScoreVisitor<T>
{
    T VisitPoints(IPoint playerOnePoint, IPoint playerTwoPoint);
 
    T VisitForty(IPlayer player, IPoint otherPlayerPoint);
 
    T VisitDeuce();
 
    T VisitAdvantage(IPlayer advantagedPlayer);
 
    T VisitGame(IPlayer playerWhoWonGame);
}

Notice that these methods take arguments, apart from VisitDeuce. I could have made that member a read-only property instead, but for consistency's sake, I kept it as a method.

All the other methods take arguments that are, in their own right, Visitors.

In addition to the Visitor interface, you also need an interface to model the score itself:

public interface IScore
{
    T Accept<T>(IScoreVisitor<T> visitor);
}

This one defines, as usual, just a single Accept method.

Since IScoreVisitor enumerates five distinct cases, you must also add five concrete implementations of IScore. Here's Forty:

public struct Forty : IScore
{
    private readonly IPlayer player;
    private readonly IPoint otherPlayerPoint;
 
    public Forty(IPlayer player, IPoint otherPlayerPoint)
    {
        this.player = player;
        this.otherPlayerPoint = otherPlayerPoint;
    }
 
    public T Accept<T>(IScoreVisitor<T> visitor)
    {
        return visitor.VisitForty(player, otherPlayerPoint);
    }
}

I'm leaving other concrete classes as an exercise to the reader. All of them are similar, though, in that they all implement IScore and unconditionally dispatch to 'their' method on IScoreVisitor - Forty calls VisitForty, Points calls VisitPoints, and so on. Each concrete implementation has a distinct constructor, though, since what they need to dispatch to the Visitor differs.

Deuce, being degenerate, doesn't have to explicitly define a constructor:

public struct Deuce : IScore
{
    public T Accept<T>(IScoreVisitor<T> visitor)
    {
        return visitor.VisitDeuce();
    }
}

The C# compiler automatically adds a parameterless constructor when none is defined. An alternative implementation would, again, be to make Deuce a Singleton.

In all, it takes seven types (two interfaces and five concrete classes) to model Score - a type that requires only a few lines of code in F# (six lines in my code, but you could format it more densely if you want to compromise readability).

Keeping score #

In order to calculate the score of a game, I also translated the score function. I put that in an extension method so as to not 'pollute' the IScore interface:

public static IScore BallTo(this IScore score, IPlayer playerWhoWinsBall)
{
    return score.Accept(new ScoreVisitor(playerWhoWinsBall));
}

Given an IScore value, there's little you can do with it, apart from calling its Accept method. In order to do that, you'll need an IScoreVisitor, which I defined as a private nested class:

private class ScoreVisitor : IScoreVisitor<IScore>
{
    private readonly IPlayer playerWhoWinsBall;
 
    public ScoreVisitor(IPlayer playerWhoWinsBall)
    {
        this.playerWhoWinsBall = playerWhoWinsBall;
    }
 
    // Implementation goes here...

Some of the methods are trivial to implement, like VisitDeuce:

public IScore VisitDeuce()
{
    return new Advantage(playerWhoWinsBall);
}

Most others are more complicated. Keep in mind that the method arguments (IPlayer, IPoint) are Visitors in their own right, so in order to do anything useful with them, you'll have to call their Accept methods with a corresponding, specialised Visitor.

Pattern matching #

I quickly realised that this would become too tedious, even for an exercise, so I leveraged my knowledge that the Visitor pattern is isomorphic to a Church encoding. Instead of defining umpteen specialised Visitors, I just defined a generic Match method for each Visitor-based object. I put those in extension methods as well. Here's the Match method for IPlayer:

public static T Match<T>(this IPlayer player, T playerOne, T playerTwo)
{
    return player.Accept(new MatchVisitor<T>(playerOne, playerTwo));
}

The implementation is based on a private nested MatchVisitor:

private class MatchVisitor<T> : IPlayerVisitor<T>
{
    private readonly T playerOneValue;
    private readonly T playerTwoValue;
 
    public MatchVisitor(T playerOneValue, T playerTwoValue)
    {
        this.playerOneValue = playerOneValue;
        this.playerTwoValue = playerTwoValue;
    }
 
    public T VisitPlayerOne()
    {
        return playerOneValue;
    }
 
    public T VisitPlayerTwo()
    {
        return playerTwoValue;
    }
}

This enables pattern matching, upon which you can implement other reusable methods, such as Other:

public static IPlayer Other(this IPlayer player)
{
    return player.Match<IPlayer>(
        playerOne: new PlayerTwo(),
        playerTwo: new PlayerOne());
}

It's also useful to be able to compare two players and return two alternative values depending on the result:

public static T Equals<T>(
    this IPlayer p1,
    IPlayer p2,
    T same,
    T different)
{
    return p1.Match(
        playerOne: p2.Match(
            playerOne: same,
            playerTwo: different),
        playerTwo: p2.Match(
            playerOne: different,
            playerTwo: same));
}

You can add similar Match and Equals extension methods for IPoint, which enables you to implement all the methods of the ScoreVisitor class. Here's VisitForty as an example:

public IScore VisitForty(IPlayer player, IPoint otherPlayerPoint)
{
    return playerWhoWinsBall.Equals(player,
        same: new Game(player),
        different: otherPlayerPoint.Match<IScore>(
            love: new Forty(player, new Fifteen()),
            fifteen: new Forty(player, new Thirty()),
            thirty: new Deuce()));
}

If playerWhoWinsBall.Equals(player the implementation matches on same, and returns new Game(player). Otherwise, it matches on different, in which case it then has to Match on otherPlayerPoint to figure out what to return.

Again, I'll leave the remaining code as an exercise to the reader.

Tests #

While all this code is written in C#, it's all pure functions. Thus, it's intrinsically testable. Knowing that, I could have added tests after writing the 'production code', but that's so boring, so I still developed this code base using test-driven development. Here's an example of a test:

[Theory, MemberData(nameof(Player))]
public void TransitionFromDeuce(IPlayer player)
{
    var sut = new Deuce();
 
    var actual = sut.BallTo(player);
 
    var expected = new Advantage(player);
    Assert.Equal(expected, actual);
}

I wrote all tests as properties for all. The above test uses xUnit.net 2.4.0. The Player data source is a private MemberData defined as a read-only property:

public static IEnumerable<object[]> Player
{
    get
    {
        yield return new object[] { new PlayerOne() };
        yield return new object[] { new PlayerTwo() };
    }
}

Other tests are defined in a likewise manner.

Conclusion #

Once you've tried to solve problems with algebraic data types it can be frustrating to return to languages that don't have sum types (discriminated unions). There's no need to despair, though. Sum types are isomorphic to the Visitor design pattern, so it is possible to solve problems in the same way.

The resulting code can easily seem complex because a simple discriminated union translates to multiple C# files. Another option is to use Church encoding, but many developers who consider themselves object-oriented often balk at such constructs. When it comes to policy, the Visitor design pattern offers the advantage that it's described in Design Patterns. While it may be a bit of an underhanded tactic, it effectively deals with some teams' resistance to ideas originating in functional programming.

The exercise outlined in this article demonstrates that translating from algebraic data types to patterns-based object-oriented code is not only possible, but (once you get the hang of it) unthinking and routine. It's entirely automatable, so you could even imagine defining a DSL for defining sum types and transpiling them to C#.

But really, you don't have to, because such a DSL already exists.

Comments

// type Bool = True | False
interface IBoolVisitor<R>
{
    R True();
    R False();
}

static class BoolUtils
{
    public static Func<IBoolVisitor<R>, R> True<R>() => sym => sym.True();
    public static Func<IBoolVisitor<R>, R> False<R>() => sym => sym.False();

    private class BoolMatcher<R> : IBoolVisitor<R>
    {
        Func<R> OnTrue { get; }
        Func<R> OnFalse { get; }

        public BoolMatcher(Func<R> onTrue, Func<R> onFalse)
        {
            OnTrue = onTrue;
            OnFalse = onFalse;
        }

        public R True() => OnTrue();
        public R False() => OnFalse();
    }

    public static R Match<R>(this Func<IBoolVisitor<R>, R> value, Func<R> onTrue, Func<R> onFalse) => value(new BoolMatcher<R>(onTrue, onFalse));
}

static class FunctionsAttempt1
{
    public static string ShowBool(Func<IBoolVisitor<string>, string> value)
    {
        return value.Match(() => "True", () => "False");
    }

    public static int BoolToInt(Func<IBoolVisitor<int>, int> value)
    {
        return value.Match(() => 1, () => 0);
    }

    public static string CombineBoolFunctions<R>(Func<IBoolVisitor<R>, R> value)
    {
        return ShowBool(value) + ": " + BoolToInt(value).ToString();
    }
}

static class FunctionsAttempt2
{
    public static string ShowBool(Func<>, R> value)
    {
        return value.Match(() => "True", () => "False");
    }

    public static int BoolToInt(Func<>, R> value)
    {
        return value.Match(() => 1, () => 0);
    }

    public static string CombineBoolFunctions(Func<>, R> value)
    {
        return ShowBool(value) + ": " + BoolToInt(value).ToString();
    }
}

public abstract record Player
{
	private Player() {}
	
	public sealed record One : Player;
	public sealed record Two : Player;
}

public abstract record Point
{
	private Point() {}
	
	public sealed record Love: Point;
	public sealed record Fifteen: Point;
	public sealed record Thirty: Point;
}

public abstract record Score
{
	private Score() {}
	
	public sealed record Points(Point PlayerOnePoints, Point PlayerTwoPoints);
	public sealed record Forty(Player Player, Point OtherPlayersPoint);
	public sealed record Deuce;
	public sealed record Advantage(Player Player);
	public sealed record Game(Player Player);
}
			

• ← Previous
• Archive
• Next →