DEV Community: Brian Berns

Solving the NY Times "Pips" game with F#

Brian Berns — Thu, 23 Oct 2025 15:18:37 +0000

Introduction

        ┌───────┐
        │     = │
    ┌───┴───┬───┴───┬───┬───┬───┐
    │     6 │    12 │ 5 │   │   │
    ├───┬───┼───┬───┴───┤   │   ├───┐
    │   │   │ * │     ≠ │   │10 │ * │
┌───┘   │   ├───┼───────┤   ├───┴───┤
│    18 │   │ * │    10 │ 6 │       │
└───────┘   ├───┴───┬───┴───┤       │
            │       │       │     0 │
            │       │       ├───┬───┤
            │     4 │       │<3 │<2 │
            └───────┘       └───┴───┘

Dominoes:

0-1   0-2   1-1   1-2   1-5   2-4   3-0
3-4   3-6   4-0   4-5   5-2   6-2   6-4
6-5   6-6

Found a solution in 00:00:01.0045242:

        ┌───┬───┐
        │ 4 │ 4 │
    ┌───┤   │   ├───────┬───────┐
    │ 3 │ 3 │ 6 │ 6   5 │ 2   6 │
    │   ├───┼───┴───┬───┴───┬───┼───┐
    │ 6 │   │ 4   5 │ 4   2 │ 4 │ 3 │
┌───┴───┤   ├───┬───┼───────┤   │   │
│ 6   6 │   │ 2 │ 5 │ 5   2 │ 0 │ 0 │
└───────┘   │   │   ├───────┼───┼───┤
            │ 1 │ 1 │       │ 0 │ 0 │
            ├───┴───┤       │   │   │
            │ 1   1 │       │ 2 │ 1 │
            └───────┘       └───┴───┘

Pips is a new puzzle game from the New York Times. The object is to cover a shape made from square cells with a set of dominoes, subject to some constraints, such as that the number of pips in a region of the puzzle must sum to a specific number. The Times publishes three puzzles every day, labeled "easy", "medium", and "hard". (In fact, as of this writing, they publish the puzzle data well ahead of time, if you're willing to read JSON.)

Solving Pips is a good programming challenge because the number of possible solutions increases quickly as the board gets larger. Some of the hard-level Pips games can take a very long time to solve by a brute force search, so we'll have to be clever to get the time under, say, a few seconds in the worst case.

Backtracking

To solve Pips, we'll use a backtracking algorithm, which is essentially a rigorous version of "trial and error". The idea is to place one domino at a time on the board. If, after placing a domino, the resulting state of the puzzle is still valid (i.e. conforms to all the constraints), then we repeat the procedure with another domino in another location, etc. If the placement is invalid, we pick up that domino and try another one in that spot. In this way, we will eventually find all solutions to the puzzle, or we can stop after we find the first one. Most of the hard Pips puzzles have a single solution, but a few have more than 100 distinct solutions, and one has 2,764,800!

We'll use F# to implement this algorithm because functional programming is a good choice for "black box" problems like this that have no side-effects, and .NET is an easy, fast platform to work with. (F# is actually a great all-purpose language for just about anything, but I digress.)

In order to speed up the search for solutions, we'll make two improvements over vanilla backtracking:

Use geometric information about possible tilings to guide the search.
Prune the search tree aggressively to avoid investigating dead ends.

More on both of these enhancements below.

Tiling

One key observation is that there are only so many ways to tile a given shape with dominoes. For example, there are just three ways to tile a 2×3 rectangle:

┌───┬───┬───┐      ┌───┬───────┐      ┌───────┬───┐
│ ■ │ ■ │ ■ │      │ ■ │ ■   ■ │      │ ■   ■ │ ■ │
│   │   │   │      │   ├───────┤      ├───────┤   │
│ ■ │ ■ │ ■ │      │ ■ │ ■   ■ │      │ ■   ■ │ ■ │
└───┴───┴───┘      └───┴───────┘      └───────┴───┘

So a tiling that starts off like this:

┌───┬───────┐
│   │ ■   ■ │
├───┴───┬───┤
│ ■   ■ │   │
└───────┴───┘

is bound to fail because we've left two unconnected 1x1 areas, and there's no way to tile an odd number of cells with dominoes.

We can use this knowledge to reduce the number of configurations we have to examine when searching for Pips solutions. For example, if we start by placing a domino horizontally in the top-left corner of the 2×3 rectangle, we know where the other two dominoes have to go:

 ┌───────┬───┐     ┌───────┬───┐
 │ ■   ■ │   │     │ ■   ■ │ ■ │
 ├───────┘   │  →  ├───────┤   │ 
 │           │     │ ■   ■ │ ■ │
 └───────────┘     └───────┴───┘

To guide our backtracking algorithm, we can organize the tilings of a given shape into a "forest" of trees. Each node in a tree shows the placement of a domino in the tiling, and its child nodes show how the rest of the dominoes are placed, until we get each of the complete tilings as leaf nodes. For example, here are the five distinct tilings of a 2x4 rectangle arranged step-by-step in trees:

(Side note: Gemini is quite good at generating SVG images, if you coax it along. But PNGs, not so much.)

With this in mind, our backtracking algorithm is:

Given: A Pips puzzle in some state of completion, and a collection of tiling trees that indicate where the next domino might be placed.
If there are no more dominoes to place, the puzzle is solved.
Otherwise, for each given tiling tree:
- Get the next domino location from the root of the tree.
- Try placing each remaining domino in that location. If that is a valid placement, recursively apply the algorithm to the child trees. (Don't forget to try placing the domino in both orientations, if it is not a double.)

Pruning

If we wait until all dominoes have been placed to check whether the constraints of the puzzle have been met, it can take too long to find a solution. Instead, we aggressively check the constraints as we go along, and backtrack as soon as we know that a solution isn't possible along the current path. This process is called "pruning" the search tree.

Note that placing a domino in one region of the puzzle can affect the validity of another region, because dominoes can't be used twice. This means that we have to check the validity of all the regions of the puzzle after each domino is placed.

"Equal" region

All cells in an "equal" region must have the same value, although the value itself is not specified by the constraint. We use two rules to validate these regions:

The number of distinct pip counts in the region cannot exceed one.
There must be enough matching values available among the remaining dominoes to fill the region, For example, if the region has four cells, and one of them is covered by a domino with 2 pips on that side, are there at least three more domino sides with 2 pips among the remaining dominoes?

"Unequal" region

All cell values in an "unequal" region must be different. Again, we use two rules to validate these regions:

The number of distinct pip counts in the region cannot be less than the number of filled cells.
There must be enough distinct values available among the remaining dominoes to fill the region.

"Sum less than" region

The sum of all cell values in this type of region must be less than the specified target. There are two ways to validate these regions:

The sum of all filled cells in the region must always be less than the specified target.
There must be enough small values available among the remaining dominoes to fill the region without exceeding the target. For example, if a values in a three-cell region must sum to less than 15, and two of the cells are already filled with 5 and 6 pips, then there must be at least one domino side with 3 or fewer pips among the unused dominoes.

"Sum greater than" region

The sum of all cell values in this type of region must be greater than the specified target. In this case, we can't invalidate the region just because the filled cells don't yet exceed the target. However, we can still prune the search tree using this rule:

There must be enough large values available among the remaining dominoes to fill the region and exceed the target.

"Sum exact" region

The sum of all cell values in this type of region must equal the specified target. This is the most complex region type to validate, because we have to consider both upper and lower bounds:

The sum of all cell values in the region must never exceed the target. (Assuming there are no negative pip counts!)
If the region is completely filled, the sum must equal the target.
Otherwise, there must be enough small values among the remaining dominoes to fill the region without exceeding the target, and there must also be enough large values among them to reach the target.
Lastly, we can use a knapsack algorithm to determine whether it is possible to reach the specified sum with the remaining dominoes. This is an expensive check, so we only perform it if the other checks pass.

Results

As of this writing, there have been 88 hard Pips puzzles published by the New York Times, from August 18 to November 13, 2025. Using the above algorithm, I was able to find a solution to all of them in a total of about 1.8 seconds on my development machine (a Dell XPS with an Intel i9-12900 CPU). The hardest by far was the elephant-shaped puzzle from October 14 (top illustration), which took just over one second to solve.

Finding all the solutions to each puzzle took longer, especially for the monster from September 15, which took 130 seconds:

Date	# solutions	Time (sec.)
2025-08-18	2	0.020516
2025-08-19	4	0.004657
2025-08-20	1	0.000388
2025-08-21	2	0.002529
2025-08-22	1	0.000714
2025-08-23	80	0.020296
2025-08-24	2	0.001438
2025-08-25	1	0.001183
2025-08-26	2	0.001423
2025-08-27	1	0.000157
2025-08-28	32	0.007514
2025-08-29	1	0.003335
2025-08-30	1	0.000615
2025-08-31	3	0.004327
2025-09-01	12	0.001288
2025-09-02	4	0.000553
2025-09-03	1	0.000794
2025-09-04	86	0.011203
2025-09-05	1	0.127658
2025-09-06	1	0.021797
2025-09-07	1	0.053257
2025-09-08	1	0.001378
2025-09-09	1	0.006709
2025-09-10	1	0.000691
2025-09-11	1	0.009167
2025-09-12	1	0.001099
2025-09-13	1	0.021063
2025-09-14	1	0.006007
2025-09-15	2,764,800	130.3538
2025-09-16	4	0.001434
2025-09-17	48	0.075455
2025-09-18	1	0.000655
2025-09-19	3	0.0009
2025-09-20	3	0.009523
2025-09-21	1	0.004005
2025-09-22	1	0.009006
2025-09-23	4	0.00091
2025-09-24	1	0.002811
2025-09-25	1	0.00264
2025-09-26	1	0.003948
2025-09-27	1	0.298655
2025-09-28	2	0.001466
2025-09-29	1	0.004621
2025-09-30	110	0.013435
2025-10-01	2	0.001635
2025-10-02	1	0.002285
2025-10-03	1	0.005445
2025-10-04	2	0.001824
2025-10-05	344	0.005926
2025-10-06	1	0.000169
2025-10-07	4	0.001755
2025-10-08	1	0.013341
2025-10-09	1	0.004663
2025-10-10	1	0.033275
2025-10-11	1	0.000261
2025-10-12	1	0.001663
2025-10-13	1	0.000392
2025-10-14	1	2.195293
2025-10-15	1	0.003404
2025-10-16	4	0.002392
2025-10-17	1	0.004691
2025-10-18	10,464	1.029367
2025-10-19	1	0.006375
2025-10-20	1,920	0.020453
2025-10-21	1	0.002274
2025-10-22	5	0.010035
2025-10-23	1	0.010968
2025-10-24	1	0.202118
2025-10-25	1	0.276247
2025-10-26	1	0.000799
2025-10-27	16	0.003998
2025-10-28	166,724	49.59692
2025-10-29	134	0.008858
2025-10-30	96	0.022475
2025-10-31	32	0.003738
2025-11-01	1	0.031238
2025-11-02	1	0.000932
2025-11-03	1	0.001732
2025-11-04	1	0.003039
2025-11-05	2	0.000727
2025-11-06	1	0.003653
2025-11-07	12	0.001552
2025-11-08	10	0.001804
2025-11-09	1	0.010293
2025-11-10	1	0.004396
2025-11-11	4	0.002176
2025-11-12	2	0.000907
2025-11-13	34	0.003914

Implementation

We're finally ready to turn these ideas into code!

Domino

True to the name of the game, the dots on a domino are called "pips", and each side of a domino has between 0 and 6 pips. For example, this is the 6-5 domino:

┌───────┬───────┐
│ o o o │ o   o │
│       │   o   │
│ o o o │ o   o │
└───────┴───────┘

The corresponding F# types:

/// Number of pips on one side of a domino.
type PipCount = int

/// The two sides of a domino.
type Domino =
    {
        /// Left side of the domino.
        Left : PipCount

        /// Right side of the domino.
        Right : PipCount
    }

The code actually makes no assumption that 6 is the largest pip count on a domino, although this is the convention in all NY Times puzzles.

A domino is a "double" if the pip count is the same on both sides:

module Domino =

    /// Is the given domino a "double", such as 6-6?
    let isDouble domino =
        domino.Left = domino.Right

Doubles are special because they only have one distinct orientation, while other dominoes have two.

Note that, according to this definition, the 6-4 domino is different from the 4-6 domino. We could implement custom equality and comparison to make them equal, but it would slow down the solver for little benefit. By convention, there are no duplicate dominoes in a Pips puzzle, so checking for them is not necessary.

Cell

Each cell on the board has (row, column) coordinates:

/// A cell in a grid.
type Cell =
    {
        /// Row coordinate (0-based).
        Row : int

        /// Column coordinate (0-based).
        Column : int
    }

And in order to place dominoes correctly, we need to define what it means for two cells to be adjacent:

module Cell =

    /// Gets all possible cells adjacent to the given cell.
    /// Some of these cells might not actually exist, though.
    let getAdjacent cell =
        [|
            { cell with Row = cell.Row - 1 }
            { cell with Row = cell.Row + 1 }
            { cell with Column = cell.Column - 1 }
            { cell with Column = cell.Column + 1 }
        |]

Edge

A pair of adjacent cells is an "edge" (in the graph theory sense):

/// A pair of adjacent cells.
type Edge = Cell * Cell

When we place a domino on an edge, the left side of the domino always goes on the first cell in the edge, and the right side of the domino goes on the second cell. To get both possible orientations (assuming the domino is not a double), we could either flip the domino around or reverse the cells in the edge. We choose the latter convention in order to avoid changing a puzzle's dominoes:

module Edge =

    /// Reverses the given edge.
    let reverse ((cellA, cellB) : Edge) : Edge =
        cellB, cellA

Board

A board is a rectangular grid on which dominoes are placed. In addition to storing the location of each domino, we also need a quick way to look up the value at any cell on the board:

type Board =
    {
        /// Location of each domino placed on the board.
        DominoPlaces : List<Domino * Edge>

        /// Value in each cell.
        Cells : PipCount[(*row*), (*column*)]
    }

We store a special pip count of -1 in the array to indicate an empty cell, and copy the entire array every time we place a domino on the board in order to maintain immutability:

module Board =

    /// Places the given domino in the given location on the
    /// board.
    let place domino ((cellLeft, cellRight) as edge : Edge) board =

            // copy on write
        let cells = Array2D.copy board.Cells
        cells[cellLeft.Row, cellLeft.Column] <- domino.Left
        cells[cellRight.Row, cellRight.Column] <- domino.Right

        {
            Cells = cells
            DominoPlaces =
                (domino, edge) :: board.DominoPlaces
        }

Region

Regions tell us where we are allowed to place dominoes on a board and impose constraints that must be met by those dominoes:

/// A region of cells on a board.
type Region =
    {
        /// Cells in the region.
        Cells : Cell[]

        /// Constraint on the cells in the region.
        Type : RegionType
    }

Tiling

A tiling is a set of edges:

type Tiling = Set<Edge>

And we need a way to obtain all possible tilings for a given shape, as defined by a set of cells:

module Tiling =

    /// Gets all tilings for the given set of cells.
    let getAll (cells : Set<Cell>) : Tiling[] =
        ...   // implementation omitted for brevity

Puzzle

A Pips puzzle contains:

A set of unplaced dominoes
An array of regions
A board of cells, some of which may be covered with dominoes

When a puzzle is created, the board is empty. When it is solved, all the cells in the puzzle's regions are covered by dominoes, and the set of unplaced dominoes is empty. The initial puzzle, its solution, and all the states in between are represented by the same type:

/// A Pips puzzle in some state of being solved.
type Puzzle =
    {
        /// Available dominoes that have not yet been placed
        /// on the board.
        UnplacedDominoes : Set<Domino>   // assume no duplicates

        /// Regions of cells that impose constraints on the
        /// dominoes placed there.
        Regions : Region[]

        /// A board of cells, some of which may be covered
        /// with dominoes.
        Board : Board
    }

Backtrack

We can use our backtracking algorithm to find all solutions to a Pips puzzle, or stop after finding one solution:

module Backtrack =

    /// Finds all solutions for the given puzzle by back-
    /// tracking.
    let solve (puzzle : Puzzle) : Puzzle[] =
        ...   // implementation omitted for brevity

    /// Finds an arbitrary solution for the given puzzle by
    /// backtracking, if at least one exists.
    let trySolve (puzzle : Puzzle) : Option<Puzzle> =
        ...   // implementation omitted for brevity

The implementations of these functions are essentially the same, except that solve uses an array comprehension to collect all the solutions, while trySolve uses Seq.tryPick to stop after finding the first solution.

The reverse state monad in F#

Brian Berns — Sun, 03 Apr 2022 04:15:11 +0000

State monad recap

We've seen previously that the state monad can be used to create computations in which each step produces a result and also updates a running state. For example, we can create a computation that maintains state on a stack, like this:

let comp =
    state {
        let! a = popC
        do! pushC 5
        do! pushC 8
        let! b = popC
        return a - b
    }

In English, here's what this computation does:

Pops the top value off the stack and saves the result in a variable called a.
Pushes 5 onto the stack.
Pushes 8 onto the stack.
Pops the top value off the stack (which we know is 8) and saves the result in a variable called b.
Returns the value of a - b as the final result of the computation.

We can run the computation on a particular stack like this:

let stack = [9; 0; 2; 1; 0] |> Stack.ofList
Stateful.run stack comp

The result is 9 - 8 = 1 and the final state of the stack is [5; 0; 2; 1; 0].

Reverse state monad

It turns out that we can create a similar monad in which the results (i.e. named values within the computation) continue to flow as expected, but changes to the state occur in reverse order, almost as if they are traveling backwards in time! I don't think there are many practical uses for such a computation - it's just interesting to think about.

Let's start out by reversing the same computation we walked through above:

let rcomp =
    rstate {
        let! a = popC
        do! pushC 5
        do! pushC 8
        let! b = popC
        return lazy (a.Value - b.Value)
    }

This looks almost identical, except we're using a computation builder for the reverse state monad (rstate) instead of the state builder. However, one very important difference is that all of the results are lazy values. This is crucial for avoiding infinite regress. For example, the results a and b are both ints in the original example, but here they both have type Lazy<int> instead. We're free to use these results lazily within the computation, but we can't do anything that would trigger their evaluation prematurely. This is why the return value is carefully written to compute a - b lazily. The complete computation has type RStateful<Stack<int>, Lazy<int>>, which means that it's a reverse state computation that works on a stack of integers and returns a lazy integer as a final result.

Here's what happens when we execute this computation:

Since state flows in reverse order, first the top value is popped off the stack and assigned to b.
Moving backwards, 8 is pushed on the stack.
Then 5 is pushed on the stack.
The top value is popped off the stack (which must be 5) and assigned to a.
Lastly, we return a - b lazily.

Remember: Results flow down, but state flows up.

We can run this computation on the same input stack as before:

let stack = [9; 0; 2; 1; 0] |> Stack.ofList
RStateful.run stack rcomp   // reverse state monad

The result is 5 - 9 = -4 and the final state of the stack is [8; 0; 2; 1; 0].

How!?

This seems ridiculous, but it works fine. The key, as usual, is in the bind method:

let bind binder rstateful =
    RStateful (fun state ->
        let rec resultAfinal = lazy (run intermediate.Value rstateful)
        and resultA = lazy (fst resultAfinal.Value)
        and final = lazy (snd resultAfinal.Value)
        and resultBintermediate = lazy (run state (binder resultA))   // lazy result passed to binder
        and resultB = lazy (fst resultBintermediate.Value)
        and intermediate : Lazy<_> = lazy (snd resultBintermediate.Value)
        resultB.Value, final.Value)

This is considerably more complex than the corresponding bind for the normal state monad, so I'm not going to walk through it in detail. The important thing to notice is the initial state is passed to the second step (binder), and then the intermediate state is passed to the first step (rstateful). This is the reverse of how the normal state monad works. However, the result of the first step (resultA) is still passed to the second step, albeit lazily, and then the result of that step (resultB) is returned.

Again, I want to emphasize that there's not much practical reason to do this. It exists because it can be done, and that's enough for me. :)

References

Crazy functional programming ideas usually come out of Haskell, and this one is no exception. There's not a lot of information about it, but here are some links that might be useful:

Applicatives in F#

Brian Berns — Thu, 13 May 2021 17:58:31 +0000

Background

Previously, we learned about applicative functors, which are souped-up functors that support multi-argument mapping functions. In this post, I'd like to dive deeper into the practical usage of applicatives in F#.

We described an applicative as a type that:

Is a functor, which means that it has a unary (i.e. single-argument) map function (and, thus, an infix version of the same function, called <!>).
Provides a way to apply arguments one at a time, via a <*> function.
Provides a way to "lift" values into the applicative.

Example

F#'s Option<'t> type is an applicative:

let (<!>) = Option.map

let (<*>) fOpt xOpt =
    match fOpt, xOpt with
        | Some f, Some x -> Some (f x)
        | _ -> None

let lift x = Some x

This allows us, for example, to use multiplication to "map" over two options at once:

let mult = (*)

// functor: times3 takes one argument
let times3 = mult 3
Option.map times3 (Some 4)   // Some 12
Option.map times3 None       // None

// applicative: mult takes two arguments
mult <!> Some 3 <*> Some 4   // Some 12
mult <!> None   <*> Some 4   // None
mult <!> Some 3 <*> None     // None

Pipes

Applying arguments one at a time with <*> is certainly a legitimate way to think about applicatives, but (IMHO) it's not the most intuitive, nor is it used often in F#. I think it's easier to conceptualize applicatives with the lifted function (e.g. mult) at the end of a computation, instead of the beginning. Following the FParsec library, we'll call this "pipes" style:

let pipe2 a b f = f <!> a <*> b

In the case of options, pipe2 has the following signature:¹

Option<'a> -> Option<'b> -> ('a -> 'b -> 'c) -> Option<'c>

So pipe2 is a function that sends the result of computations a and b to function f, producing a new computation. We can see it in action with options here:

pipe2 (Some 3) (Some 4) mult   // Some 12
pipe2 None (Some 4) mult       // None

We can define pipe3, pipe4, etc. similarly.

Using pipes style, we can think of applicatives as performing computations in parallel at the same time, with no dependencies between them. For example, consider:

let runMult getOptA getOptB =
    pipe2
        (getOptA ())
        (getOptB ())
        mult

Note that getOptB is executed even if getOptA returns None. There's no way to short-circuit the computation before getOptB is invoked.

Monad-lite

Contrast this with monads, which are a way of performing computations in series, so that the result of one computation flows into the next. In fact, instead of thinking of applicatives as souped-up functors, it's often easier to think of them as a "lite" version of monads.² Let's see where this notion takes us, starting with a basic computation builder for options:

type OptionBuilder() =
    member __.Return(x) = Some x
    member __.Bind(opt, binder) = Option.bind binder opt

let option = OptionBuilder()

Using this builder, we can create monadic computation expressions, such as:

option {
    let! a = optA
    let! b = optB
    return a * b
}

Note that the computation of b does not depend in any way on the value of a, so a monad is overkill for this computation - it is merely applicative. We can enforce this limitation by removing the Bind method from the computation builder, but then the expression doesn't compile at all.

F# 5 enhancements

Fortunately, F# now supports applicative computation expressions directly. There are two new core builder methods:

BindReturn: Corresponds to <!>, which is just map.
MergeSources: Similar to <*> and pipe2, except that it always produces a 2-tuple (instead of calling a function).

For our option builder, their implementation looks like this:

member __.BindReturn(opt, f) =
    Option.map f opt

member __.MergeSources(optA, optB) =
    match optA, optB with
        | Some a, Some b -> Some (a, b)
        | _ -> None

Now that these two methods are present in the builder, and! can be used instead of let! to create an applicative expression:

option {
    let! a = optA
    and! b = optB   // OK because b does not depend on a
    return a * b
}

Because the applicative computations are independent, they can potentially be parallelized by the compiler, resulting in more efficient code. So be on the lookout for opportunities to use and! instead of let! in your F# code!

References

Haskell calls this function liftA2 instead of pipe2, where the A stands for "applicative". ↩
So, just as every applicative is also a functor, every monad is also an applicative. However, not every applicative is a monad, which is what makes the applicative pattern useful on its own, situated between its two better-known cousins. ↩

How to avoid the Visitor pattern in C#

Brian Berns — Fri, 29 May 2020 19:19:21 +0000

Arithmetic expressions

Let's say we want to represent a simple arithmetic expression in C#, and then evaluate it. For example, evaluating 1 + (2 + 3) would produce 6. What's the best way to do this?

The obvious approach is to define a class hierarchy. We start with a base interface that represents all expressions:

interface IExpr
{
    int Eval();
}

The Eval method is what we'll use to evaluate an expression. For our simple case, we have two concrete implementations of this interface. The first represents a literal integer value (e.g. 5):

class Literal : IExpr
{
    public Literal(int n)
    {
        N = n;
    }

    public int N { get; }

    public int Eval() => N;
}

Evaluating a literal is trivial: we simply return the value of the literal itself.

Next, we can represent addition like this:

class Add : IExpr
{
    public Add(IExpr a, IExpr b)
    {
        A = a;
        B = b;
    }

    public IExpr A { get; }
    public IExpr B { get; }

    public int Eval() => A.Eval() + B.Eval();
}

To evaluate an addition expression, we recursively evaluate both of its subexpressions and then add those two values together.

We're ready to try it out:

// 1 + (2 + 3)
public static IExpr CreateTestExpr()
    => new Add(
        new Literal(1),
        new Add(
            new Literal(2),
            new Literal(3)));

public static void Test()
{
    var expr = CreateTestExpr();
    Console.WriteLine(expr.Eval());
}

This creates our 1 + (2 + 3) test expression and then evaluates it, writing 6 to the console.

Extensibility

That's great, but what if we want to extend our system? For example, let's add a new expression type that represents multiplication. This is easy - all we need is a new concrete implementation of IExpr:

class Mult : IExpr
{
    public Mult(IExpr a, IExpr b)
    {
        A = a;
        B = b;
    }

    public IExpr A { get; }
    public IExpr B { get; }

    public int Eval()
        => A.Eval() * B.Eval();
}

But what if we want to add new behavior to our expressions instead? Let's say we want to be able to print an arbitrary expression by converting it to a string. For example, printing the expression 1 + (2 + 3) would result in the string "(1 + (2 + 3))". To make this work, we have to add a new Print method to the base IExpr interface:

interface IExpr
{
    int Eval();
    string Print();   // NEW
}

But that means that we'd have to modify all the existing expression types (Literal, Add, etc.) to support printing. Our requirement instantly cascades through the entire code base. We might not even own all the code that has to change, in which case we'd be stuck. Is there any way to add printing ability without modifying existing code?

The Visitor pattern

The typical way to solve this problem is with the Visitor pattern. To make this work, we have to start over with a different IExpr interface:

interface IExpr
{
    TResult Accept<TResult>(IVisitor<TResult> visitor);
}

Instead of exposing an explicit Eval method, this new interface now exposes a generic Accept method that supports any "visitor" that implements a separate interface called IVisitor:

interface IVisitor<TResult>
{
    TResult VisitLiteral(Literal literal);
    TResult VisitAdd(Add add);
}

Each concrete IExpr subtype then invokes the corresponding visitor method inside its Accept method:

class Literal : IExpr
{
    public Literal(int n)
    {
        N = n;
    }

    public int N { get;  }

    public TResult Accept<TResult>(IVisitor<TResult> visitor)
        => visitor.VisitLiteral(this);
}

class Add : IExpr
{
    public Add(IExpr a, IExpr b)
    {
        A = a;
        B = b;
    }

    public IExpr A { get; }
    public IExpr B { get; }

    public TResult Accept<TResult>(IVisitor<TResult> visitor)
        => visitor.VisitAdd(this);
}

Using this approach, different visitor implementations can implement different behavior. For example, here are two visitors - one that evaluates an expression, and a different one that prints an expression to a string:

class EvalVisitor : IVisitor<int>
{
    public int VisitLiteral(Literal literal)
        => literal.N;

    public int VisitAdd(Add add)
        => add.A.Accept(this) + add.B.Accept(this);
}

class PrintVisitor : IVisitor<string>
{
    public string VisitLiteral(Literal literal)
        => literal.N.ToString();

    public string VisitAdd(Add add)
        => String.Format($"({add.A.Accept(this)} + {add.B.Accept(this)})");
}

That's terrific - we can now add behavior to our system without modifying existing code. But... what if we still want to be add a new expression type like Mult as well? In order to support that, we have to add it to the base IVisitor interface:

interface IVisitor<TResult>
{
    TResult VisitLiteral(Literal literal);
    TResult VisitAdd(Add add);
    TResult VisitMult(Mult mult);   // NEW
}

But that means that we'd have to modify all the existing visitors (evaluation, printing, etc.) to support multiplication. Our requirement instantly cascades through the entire code base. We might not even own all the code that has to change, in which case we'd be stuck. Does this sound familiar?

The expression problem

This conundrum is called the "expression problem". Is there a good way to design a system so that it's easy to both a) add new subtypes, and b) add new behaviors, without modifying existing code?

It turns out that there is a rather nifty way to accomplish this, called "object algebras". We start with an "object algebra interface" that looks similar to the Visitor pattern:

interface IExprAlgebra<T>
{
    T Literal(int n);
    T Add(T a, T b);
}

We're going to use this interface more like a Factory pattern than a visitor, though. For example, we can create the expression 1 + (2 + 3) like this:

public static T CreateTestExpr<T>(IExprAlgebra<T> factory)
    => factory.Add(
        factory.Literal(1),
        factory.Add(
            factory.Literal(2),
            factory.Literal(3)));

To create an expression we take a "factory" that implements our expression algebra, and ask it to construct an object of arbitrary type T that represents 1 + (2 + 3). This type can be whatever the factory wants it to be.

For example, to create an algebra that can evaluate expressions we define an IEvalExpr interface that represents any evaluable object:

interface IEvalExpr
{
    int Eval();
}

class EvalExpr : IEvalExpr
{
    public EvalExpr(Func<int> eval)
    {
        _eval = eval;
    }
    Func<int> _eval;

    public int Eval()
        => _eval();
}

The EvalExpr class implements this interface by wrapping an arbitrary function. We can then use these to create a concrete algebra:

class EvalAlgebra : IExprAlgebra<IEvalExpr>
{
    public IEvalExpr Literal(int n)
        => new EvalExpr(() => n);

    public IEvalExpr Add(IEvalExpr a, IEvalExpr b)
        => new EvalExpr(() => a.Eval() + b.Eval());
}

Note that each method returns an evaluable object of type IEvalExpr. We can then test this approach, as follows:

IEvalExpr expr = CreateTestExpr(new EvalAlgebra());
Console.WriteLine(expr.Eval());

The first line creates an evaluation algebra and uses that as a factory to represent the expression as an evaluable object. The second line evaluates that object and writes the result to the console (6, as before).

Extensibility, again

So far, so good. But how extensible is this approach? Can we implement printing without changing any of the existing code? Yes. As before, we first define an interface for printable objects:

interface IPrintExpr
{
    string Print();
}

class PrintExpr : IPrintExpr
{
    public PrintExpr(Func<string> print)
    {
        _print = print;
    }
    Func<string> _print;

    public string Print()
        => _print();
}

And then implement a new print algebra that returns printable objects:

class PrintAlgebra : IExprAlgebra<IPrintExpr>
{
    public IPrintExpr Literal(int n)
        => new PrintExpr(() => n.ToString());

    public IPrintExpr Add(IPrintExpr a, IPrintExpr b)
        => new PrintExpr(() => $"{a.Print()} + {b.Print()}");
}

And can we also create a new expression type, like multiplication, without modifying existing code? Again, the answer is yes. To handle this, we first extend our algebraic interface:

interface IExprAlgebraExt<T> : IExprAlgebra<T>
{
    T Mult(T a, T b);
}

class EvalAlgebraExt : EvalAlgebra, IExprAlgebraExt<IEvalExpr>
{
    public IEvalExpr Mult(IEvalExpr a, IEvalExpr b)
        => new EvalExpr(() => a.Eval() * b.Eval());
}

This defines a new interface called IExprAlgebraExt that includes all of IExprAlgebra (i.e. Literal and Add) and also defines a new method called Mult that follows the same pattern. The implementation of this interface is EvalAlgebraExt, which similarly inherits from our existing EvalAlgebra while also implementing the new Mult requirement.

We can test it out on an expression like 4 * (5 + 6) that contains literals, addition, and multiplication:

public static T CreateTestExprExt<T>(IExprAlgebraExt<T> factory)
    => factory.Mult(
        factory.Literal(4),
        factory.Add(
            factory.Literal(5),
            factory.Literal(6)));

public static void Test()
{
    IEvalExpr expr =
        CreateTestExprExt(new EvalAlgebraExt());
    Console.WriteLine(expr.Eval());
}

Note that CreateTestExprExt takes the extended version of the algebraic interface, which ensures that it can handle multiplication, but still returns a plain old evaluable object of type IEvalExpr. We can expose this new interface to our entire system, or we can keep it local only - it's up to us. There's no cascade of changes that we're forced to make.

So, we've successfully solved the expression problem! This approach is more flexible than visitors, but doesn't add significant additional overhead or complexity. I'd call that a win!

References

For more information:

The original paper that introduced object algebras: Extensibility for the Masses: Practical Extensibility with Object Algebras
From Object Algebras to Finally Tagless Interpreters, which walks through this approach in Java and Haskell. I used this article as a basis for my post.
My GitHub repository containing the code from this post.

Why algebraic effects matter in F#

Brian Berns — Fri, 15 May 2020 20:08:09 +0000

Side effects

Side effects are impossible to avoid in imperative code, but they can make reasoning about the behavior of a program very difficult. F# allows us to use imperative side effects, but it's often better not to. How can we avoid side effects while still implementing effectful requirements?

As an example, let's take a very simple and common effectful example: logging. Say we're writing a function that computes the length of the hypotenuse of a right triangle from the lengths of the other two sides:

let hypotenuse a b =
    printfn "Side a: %g" a
    printfn "Side b: %g" b
    let c = sqrt <| (a*a + b*b)
    printfn "Side c: %g" c
    c

Every time this function is called, we log the input and output to the console as a side effect. This is fine in a single-threaded application, but what happens if hypotenuse is called simultaneously from two different threads? That's trouble.

A common approach in the imperative/OO world is to use dependency injection (or plain old interfaces) to separate the logging API from its implementation. However, the resulting code still causes side effects. Is it possible to define an effectful hypotenuse function that doesn't have any side effects? It sounds almost like a contradiction in terms, but it can be done, and the solution is very interesting.

Algebraic effects

The approach is to explicitly declare effects using an Effect type:

type Effect<'result> =
    | Log of string * (unit -> Effect<'result>)
    | Result of 'result

In this simple example, there are only two effects:

Log is what we use to write a string to a logger. This constructor takes an additional continuation function that is to be executed after the string is logged.
Result simply holds a value and doesn't cause an effect.

Note that this type is an example of the free monad. Log corresponds to the Free constructor and Result corresponds to Pure. The free monad is useful here because it can chain effects together. For example, we could rewrite our calculation like this:

let hypotenuse a b =
    Log ((sprintf "Side a: %g" a), fun () ->
        Log ((sprintf "Side b: %g" b), fun () ->
            let c = sqrt <| (a*a + b*b)
            Log ((sprintf "Side c: %g" c), fun () ->
                Result c)))

It's important to understand that this version of the function returns an Effect<float> rather than a float itself. You can think of this type as an "effectful" computation that will return a float when it is executed. However, until it is executed it does nothing - in particular, it has no side effects. It simply defines a computation.

Handling effects

In order to actually compute a result, we need some additional code that can "handle" our effects, just like an exception handler handles exceptions (which are also a kind of effect). Let's write a handler that accumulates log messages in a list while performing a calculation:

let handle effect =

    let rec loop log = function
        | Log (str, cont) ->
            let log' = str :: log
            loop log' (cont ())
        | Result result -> result, log

    let result, log = loop [] effect
    result, log |> List.rev

When we pass an effectful computation to handle, we get two things back: the final result of the computation, and a list of all the log messages that were written during the computation:

let c, log =
    hypotenuse a b
        |> handle

Note that handle is also a pure function - it doesn't write anything to the console or perform any other side effect. If we want, we could then write the resulting log to the console, but we'd have to be careful at that point to consider the actual side effects involved. The important thing is that we've successfully separated a pure functional calculation from the impure side effects of writing a log to the console. By solving those two problems separately, we've made it much easier to understand how our program behaves.

Syntactic sugar

Of course, no one wants to write ugly nested Log invocations like this because they completely distract from the logic of the computation itself. Fortunately, we know that the free monad can help us here by providing a workflow:

let rec bind f = function
    | Log (str, cont) ->
        Log (str, fun () ->
            cont () |> bind f)
    | Result result -> f result

type EffectBuilder() =
    member __.Return(value) = Result value
    member __.Bind(effect, f) = bind f effect

let effect = EffectBuilder()

This is the standard bind implementation for the free monad: it simply passes the binding function down the chain until the end, at which time the two effects are bound together by applying the function.

We also need some helper functions that "lift" a log string into the monad:

let log str = Log (str, fun () -> Result ())
let logf fmt = Printf.ksprintf log fmt

Again, this follows the same pattern we've seen before with the free monad. With these tools in hand, we can rewrite our computation much more elegantly:

let hypotenuse a b =
    effect {
        do! logf "Side a: %g" a
        do! logf "Side b: %g" b
        let c = sqrt <| (a*a + b*b)
        do! logf "Side c: %g" c
        return c
    }

This version of the function produces an Effect<float> that is identical to the previous one. It's just much easier to understand, and is essentially no more complex than the original version of hypotenuse that wrote directly to the console.

Limitations

We can easily support additional effects by adding union cases to our Effect type. However, this sort of master list of all effects in a system isn't very practical. Ideally, we'd like to modularize effects so that they can be composed together. For example, we'd like to be able to handle log effects separately from exception effects and separately from stateful effects. Unfortunately, this isn't particularly easy to do in F# yet, but there is a library called Eff that serves as a proof of concept. (I wouldn't use it in production, though, because the handlers are rather ugly.)

In the future, I expect that algebraic effects will become mainstream, and support for explicit effect types will be baked into both functional and imperative languages. That's still several years away, though, but at least now you know it's (probably) coming.

The state monad in F#

Brian Berns — Sun, 03 May 2020 07:26:48 +0000

This is a primer on implementing stateful computations in F# without violating functional purity. Wait, side effects? Is that really possible in a functional language? Yes, but not in the way you might be used to from imperative programming.

Stacks

Let's define a basic immutable stack type based on lists:

type Stack<'t> = private Stack of List<'t>

module Stack =

    let ofList list = Stack list

    /// 'a -> Stack<'a> -> Stack<'a>
    let push item (Stack items) =
        Stack (item :: items)

    /// Stack<'a> -> 'a * Stack<'a>
    let pop = function
        | Stack (head :: tail) -> head, Stack tail
        | Stack [] -> failwith "Empty stack"

Note that push and pop are pure functions: they both return a new, updated stack, rather than modifying the given stack directly. Using a stack this way can get a little tedious, because we have to explicitly track the state of the stack with a different variable at every step:

let stack = Stack.ofList [1; 2]
let item, stack' = stack |> Stack.pop
let stack'' = stack' |> Stack.push 3

/// Output: 1, Stack [3; 2]
printfn "%A, %A" item stack''

Those stack variables are exhausting and distract from the purpose of the code. Fortunately, it's possible to eliminate them entirely, while still honoring the immutability of Stack.

Stateful computations

The general pattern here is that a stateful operation takes the current state as input, performs some action on it, and returns a result along with a new, updated state: 'state -> 'result * 'state¹. Let's put that signature into a type that represents a stateful computation:

/// A stateful computation.
type Stateful<'state, 'result> =
    Stateful of ('state -> 'result * 'state)

Note that this type represents a computation, but doesn't actually execute it. In order to run a computation, we need to invoke the wrapped function with a given state:

/// 'state -> Stateful<'state, 'result> -> ('result * 'state)
let run state (Stateful f) =
    f state

The state monad

Our Stateful type is a monad, which means that it supports return and bind functions. The first one creates a stateful computation that simply returns a given value without altering the current state:

/// 'result -> Stateful<'state, 'result>
let ret result =
    Stateful (fun state -> (result, state))

Binding two stateful computations together is more complex, but quite elegant:

/// ('a -> Stateful<'state, 'b>) -> Stateful<'state, 'a> -> Stateful<'state, 'b>
let bind binder stateful =
    Stateful (fun state ->
        let result, state' = stateful |> run state
        binder result |> run state')

As usual, bind is the most important part of the state monad, so let's make sure we understand what's going on. First, take a look at the signature: the two computations we're binding must work with the same type of state (e.g. Stack). The only thing that can vary between them is their result types. So, how does the combined computation work? It starts by running the first computation on the incoming state, producing a result and a new state (state'). It then passes that result to the given binder function, giving us the second computation. Lastly, it runs that computation using the updated state. Again, keep in mind that neither of the bound computations are actually executed within bind. We're simply defining a new computation that will run them both in sequence when called upon to do so.

With that out of the way, it's easy to define a builder:

type StatefulBuilder() =
    let (>>=) stateful binder = Stateful.bind binder stateful
    member __.Return(result) = Stateful.ret result
    member __.ReturnFrom(stateful) = stateful
    member __.Bind(stateful, binder) = stateful >>= binder
    member __.Zero() = Stateful.ret ()
    member __.Combine(statefulA, statefulB) =
        statefulA >>= (fun _ -> statefulB)
    member __.Delay(f) = f ()

let state = StatefulBuilder()

Stack computations

Let's create stateful computations for our stack operations, push and pop. pop is easy because its signature is exactly what we need:

/// Stateful<Stack<'a>, 'a>
let popC = Stateful Stack.pop

We call this popC to emphasize that it defines a computation. push is nearly as easy - we just need to explicitly return () as a result:

/// 'a -> Stateful<Stack<'a>, unit>
let pushC item =
    Stateful (fun stack ->
        (), Stack.push item stack)

Note that pushC 2 is a computation that pushes 2 on a stack, while pushC 9 is a different computation that pushes 9 on a stack. The arguments to push are baked directly into the computations, so running a computation takes no input other than the state.

We're ready to define a complex stateful computation using stacks:

/// Stateful<Stack<int>, int>
let comp =
    state {
        let! a = popC
        if a = 5 then
            do! pushC 7
        else
            do! pushC 3
            do! pushC 8
        return a
    }

This is a computation that works on state of type Stack<int> and returns an int. Note that the computation doesn't explicitly refer to the stack at any point - the state monad takes care of managing it for us! Instead, we've just combined a bunch of low-level computations into a single high-level computation, step by step.

Let's run this computation to see if it works:

// Output: (9, Stack [8; 3; 0; 2; 1; 0])
let stack = [9; 0; 2; 1; 0] |> Stack.ofList
printfn "%A" (Stateful.run stack comp)

// Output: (5, Stack [7; 1])
let stack = [5; 1] |> Stack.ofList
printfn "%A" (Stateful.run stack comp)

Success!

For more information on the state monad, the following articles are helpful (both use Haskell):

To be clear, this is the same as 'state -> ('result * 'state), not ('state -> 'result) * 'state. ↩

Monads for free in F#

Brian Berns — Fri, 01 May 2020 05:57:16 +0000

If you dabble in Haskell or category theory, you might have heard of "free monads". But what exactly is a free monad, and can the concept be translated to F#? I'm going to answer those questions by creating a simple free monad, step by step. The resulting code won't actually be useful for much itself, but it provides a foundation that we can build on later.

I'm going to assume that you're already familiar with two important concepts in functional programming:

Functors. A functor is a type that can be "mapped" over. In F#, this usually means that the corresponding module contains a map function, like List.map or Array.map.
Monads. A monad is a type that can be used to build computations (a.k.a. workflows). This means that the type supports some sort of bind function, although it doesn't always go by that name.

Every monad is a functor, but not every functor is a monad. However, it turns out that if you have a functor type, you can always create a corresponding monad type, regardless of the details of how your functor works. It's a free monad!

The Option type

F# options are functors, as witnessed by the Option.map function:

// ('a -> 'b) -> Option<'a> -> Option<'b>
let map f opt = function
    | Some x -> Some (f x)
    | None -> None

This works by applying the given mapping function f to the value contained by the option (if there is one). In other words, if we have a function that maps type 'a to type 'b, then we can use it to map type Option<'a> to type Option<'b>.

You are probably aware that Option is also a monad, as witnessed by its handy Option.bind function. However, in this article, we are not going to use that function. Instead, we're going to create an entirely separate Option monad (with very different behavior) using only Option.map.

Nested functors

Because Option is a functor, it can be nested. For example, we can create values of type Option<Option<int>> or Option<Option<Option<string>>>. Any functor type can be nested in the same way. For example, List<List<int>> or Array<Array<Array<string>>>. Note that the concrete type depends on the number of nested levels. Option<int> is not the same type as Option<Option<int>>.

We would like to create a separate type that contains nested options, so that the concrete type is the same regardless of how many levels it contains. This sounds a bit like F#'s List type:

type List<'t> =
    | Cons of 't * List<'t>
    | Nil

Note that a list of integers always has type List<int>, regardless of its length:

let intListA : List<int> = Cons (1, Nil)             // [1]
let intListB : List<int> = Cons (2, Cons (3, Nil))   // [2; 3]

Let's use the same pattern to create a "nest" of options:

/// Free monad of Option<'t>.
type Nest<'t> =

    /// Nested options.
    | Free of Option<Nest<'t>>

    /// Lifts a value directly into the monad.
    | Pure of 't

Notice that Nest is a lot like List: Free corresponds to a cons cell, and Pure corresponds to the list terminator. The main difference in this case is that a nest of options can hold at most only a single value of t, in the Pure cell at the very end - unlike a list, which holds a value in every cons cell (and none at the end).

Also notice that this type refers to Option only once, in the recursive definition of the Free constructor. It would be nice if we could generalize Nest so that it didn't depend on Option at all, but F#'s type system is not strong enough for that (unlike Haskell's). Such a generic type might look something like this:

/// Free monad of 'functor<'t>.
type FreeMonad<'functor, 't> =

    /// Nested functors.
    | Free of 'functor<FreeMonad<'functor, 't>>   // oops - not legal F#

    /// Lifts a value directly into the monad.
    | Pure of 't

Since this isn't possible in F#, every time you want to create a free monad for a functor type, you'll have to write the whole thing out with at least one hardcoded reference to the functor type.¹

Anyway, we can use our new Nest type to create option nests like this:

let nestA = Pure 1
let nestB = Free (Some (Pure 2))
let nestC = Free (Some (Free (Some (Pure 3))))
let nestD = Free None
let nestE = Free (Some (Free None))

All of these have (or can have) the same type, Nest<int>.

The free monad

We now have a type that represents nested options, so next we need to show that it actually is a monad. This means creating a bind function that can connect two nests using only the fact that Option is a functor:

/// ('a -> Nest<'b>) -> Nest<'a> -> Nest<'b>
let rec bind f = function
    | Free opt ->
        opt
            |> Option.map (bind f)
            |> Free
    | Pure value -> f value

This is the heart of the free monad, so it's worth walking through what's happening in detail. The important thing to understand about the Free case is that bind f is a function of type Nest<'a> -> Nest<'b>, which is a mapping function for nests. The only thing we're allowed to know about Option is that it's a functor, so the only thing we can really do here is recursively pass the mapping function to the Free cell's contained option via Option.map. All we're really doing is handing off responsibility for the binding to the next nested level, which in turn hands it off to the next level, and so on, until we get to the bottom, which is either a Pure cell or a None option. We then construct a new Free cell from the resulting nest option. The Pure case at the end of the chain is the only place where we actually apply the binder function.

Note that bind depends on Option in only one way: the call to Option.map. We could change the implementation to work for another functor by simply invoking that functor's map function instead at the same location. None of the rest of bind's code would have to change at all (although we should also rename the opt variable to something more appropriate for our other functor).

Now that we have a bind function, we can create a workflow builder:

type NestBuilder() =
    member __.Bind(nest, func) = nest |> Nest.bind func
    member __.Return(value) = Pure value
    member __.ReturnFrom(nest) = nest

let nest = NestBuilder()

To make computation expressions easy to write, we use a small utility function that lifts a given value into the monad as a two-level nest:

/// e.g. some "A' -> Free (Some (Pure "A"))
let some value =
    value |> Pure |> Some |> Free

We can use the builder to nest values as deeply as we want, without needing multiple levels of nested parentheses:

/// Free (Some (Free (Some (Free (Some (Pure "ABC"))))))
let example1 =
    nest {
        let! a = some "A"
        let! b = some (a + "B")
        return! some (b + "C")
    }

In this example, I've chosen to concatenate strings in the binder function, but we could do anything else we want instead.

If we run into a None option at any point, the nesting process simply stops (because Option.map (bind f) returns None without recursively invoking bind):

/// Free (Some (Free (Some (Free None))))
let example2 =
    nest {
        let! a = some "A"
        let! b = some (a + "B")
        do! Free None
        return! some (b + "C")   // b + "C" never happens
    }

Conclusion

So what's the point of creating nested options this way? There's really no practical value at all, because we don't have any need to conceptualize nested options as a kind of list. I only chose Option because it is one of the simplest non-trivial functors. However, there are other functors where nesting can usefully be thought of as representing a list, and that's where free monads shine.

For more information on the free monad, you might find these articles useful:

Why free monads matter (Haskell)
F# free monad recipe

In practice, you'll often want additional constructors, and multiple type parameters, all of which follow the same general pattern. We're not going to cover that here. ↩

Existential types in C# - Part 3

Brian Berns — Thu, 19 Mar 2020 04:54:41 +0000

Recap

In a previous article, we saw how to emulate first-class polymorphism by encapsulating a generic type in a non-generic interface. This technique allows us to control the scope of a universally quantified type variable.

We then saw an example of emulating an existential type in C# using generics. There are two steps:

Use the encapsulation technique described above to wrap the hidden type in a "carton". In our example, we created IListCarton to hide IList<TItem>.
Create a callback interface then allows access to the value hidden inside the existential ("inversion of control"). We called this callback an "operation". For example, IListOperation<TReturn> allows operations on hidden instances of IList<TItem>.

In this article, I'd like to walk through the type theory that establishes the equivalence between this emulation technique and a true existential type. This is purely background information, and is not at all necessary for anyone who wants to use the technique.

Continuation passing style

We've talked before about a programming technique called continuation passing style (CPS), which is akin to logical double-negation via the Curry-Howard correspondence. If you have a value of type T that you don't want to expose directly, you can instead convert to CPS by implementing a function of type (T -> TRet) -> TRet¹, where T -> TRet is a continuation (i.e. a callback function). In English, this means that if you have a hidden instance of T and you are given a T -> TRet continuation, you can produce a TRet.

If we make the universal quantification explicit, we get the following approximate equivalence:

T ≅ ∀TRet.((T -> TRet) -> TRet)

This just says that we can emulate a given type, T, if, for any continuation returning type TRet, we can actually produce a TRet. Next, let's see what happens when we plug in an existential type, such as ∃TItem.IList<TItem>, for T:

∃TItem.IList<TItem> ≅ ∀TRet.(((∃TItem.IList<TItem>) -> TRet) -> TRet)

First-order logic

We can use the Curry-Howard correspondence to think about this as a logical expression, rather than as a type.

There's a neat logical equivalence that comes in handy at this point:

∃x.A(x) → B ≡ ∀x.(A(x) → B)

The left side says that the existence of an x that makes proposition A(x) true also implies that proposition B is true. The right side says that any x that makes A(x) true also makes B true. Intuitively, I think this is fairly clear, but it can also be rigorously proved.

We can use this equivalence to convert our existential quantifier to a universal quantifier:

∃TItem.IList<TItem> ≅ ∀TRet.(((∃TItem.IList<TItem>) -> TRet) -> TRet)
∃TItem.IList<TItem> ≅ ∀TRet.((∀TItem.(IList<TItem> -> TRet)) -> TRet)

For clarity, the universal quantifiers can omitted (but are still implied):

∃TItem.IList<TItem> ≅ (IList<TItem> -> TRet) -> TRet

This means that we can emulate an existential type using CPS, the same we can emulate any other type. This makes intuitive sense: Since CPS can be used to hide any type, we can use it to hide the type contained inside an existentially quantified type.

Since we have two inner types, TItem and TRet, we need a separate interface for each one in turn: IListCrate allows a caller to specify TRet and then IListOperation<TRet> allows a caller to specify TItem for any TRet. This gives us the full C# implementation.

Additional resources

For anyone wanting to dig deeper, here's a list of articles that I used in preparing this series on universal and existential types in C#:

F# (G-Research):
Universally quantified types:
- First-class polymorphism
Stack Exchange questions:
Haskell, first-order logic, and C-H correspondence:
- Existential type-curry
- Existential types and data abstraction

I've converted to F# syntax here because it's easier to understand than C#. (T -> TRet) -> TRet is the same as Func<Func<T, TRet>, TRet>. ↩

Existentially quantified types in C# - Part 2

Brian Berns — Mon, 16 Mar 2020 15:18:17 +0000

As we discussed last time, an existentially quantified type is one that contains a hidden implementation type that is not available to the external world at compile-time.

C# doesn't support existential types directly, but we can emulate them using generics. For the purposes of this article, I'm going to call such a type a "carton", because it contains a type that can't be seen from the outside.¹ So for example, a list carton is a list of items of an unknown type. How do we implement and use this carton type?

List operations

Let's start by defining an interface that describes a single operation on an IList<T>:

interface IListOperation<TReturn>
{
    TReturn ApplyTo<TItem>(IList<TItem> items);
}

Note that this interface is generic in the type returned by the operation. So, for example, an IListOperation<string> is a list operation that returns a string. The interface contains a single method, which applies the operation to any given generic list.

Here are two example list operations that implement this interface - one that returns the number of items in a list, and another that returns the runtime type of the items in a list:

class GetCount : IListOperation<int>
{
    public int ApplyTo<TItem>(IList<TItem> items)
        => items.Count;
}

class GetItemType : IListOperation<Type>
{
    public Type ApplyTo<TItem>(IList<TItem> items)
        => typeof(TItem);
}

static IListOperation<int> getCount = new GetCount();
static IListOperation<Type> getItemType = new GetItemType();

We've also created singleton instances of each class - getCount and getItemType.

List cartons

Now that we've defined operations on a list, we can define the list carton interface itself:

interface IListCarton
{
    TReturn ApplyOp<TReturn>(IListOperation<TReturn> listOp);
}

This interface is all that's exposed to the outside world about a list carton. Note that it follows the same pattern we saw previously when emulating first-class polymorphism: The interface itself is not generic, but contains a generic method that applies the given list operation to the carton's contents.

We can define a pair of small utility classes that make it easy to implement this interface:

class ListCartonImpl<TItem> : IListCarton
{
    public ListCartonImpl(IList<TItem> items)
    {
        _items = items;
    }
    private IList<TItem> _items;

    public TReturn ApplyOp<TReturn>(IListOperation<TReturn> listOp)
        => listOp.ApplyTo(_items);
}

static class ListCartonImpl
{
    public static IListCarton Create<TItem>(IList<TItem> items)
        => new ListCartonImpl<TItem>(items);
}

The key here is that ListCartonImpl<TItem> holds the actual list of items without exposing their type, TItem.

Using cartons

We're finally ready to take our faux-existential carton type out for a test drive. Creating cartons is easy:

var intCarton = ListCartonImpl.Create(new[] { 1, 2, 3 });
var strCarton = ListCartonImpl.Create(new[] { "moo", "baa" });

The cool thing here is that intCarton and strCarton have exactly the same type, IListCarton, even though one contains integers and the other contains strings. Consumers can rely on the fact that all items in a given list carton will have the same type without having to use runtime tricks like reflection or casting. It's all totally type-safe.

We can test these cartons as follows:

void Test(IListCarton listCarton)
{
    var count = listCarton.ApplyOp(getCount);
    Console.WriteLine(count);
    var type = listCarton.ApplyOp(getItemType);
    Console.WriteLine(type);
}
Test(intCarton);
Test(strCarton);

// output:
// 3
// System.Int32
// 2
// System.String

The folks at G-Research who invented this technique call it a "crate", but I'm avoiding that term because it's already associated with another concept in the Rust world. I've also renamed other terms in their version, but the overall concept and credit is all theirs. ↩

Existentially quantified types in C#

Brian Berns — Sun, 15 Mar 2020 15:57:43 +0000

Emulating first-class polymorphism

Last time, we talked about universally quantified types and the challenge of passing a generic function to a non-generic function. The best way to do this is with a non-generic interface that contains one or more generic methods. This allows us to limit the scope of the type variables to each method. In our case, we can define an interface that represents operations on generic lists:

interface IListOperations
{
    int GetWeight<T>(IList<T> items);   // scope of T is limited to GetWeight
    // ... other methods with other type variables
}

At the moment, we only have one such operation, GetWeight, but we could add more in the future. We can then modify our SumWeights function to take an IListOperations:

static int SumWeights(
    IList<int> ints,
    IList<string> strs,
    IListOperations listOps)
    => listOps.GetWeight(ints) + listOps.GetWeight(strs);

This technique is a bit more verbose than a plain function, but it effectively supports universally quantified function types. (Shout out to @costinmanda for digging into this problem in the comments!)

Deserialization challenge

Now let's switch to a different, more unusual, problem. Imagine that we have a file that contains a list of serialized objects, all of the same type. For example, we might store a list of circles like this:

MyNamespace.Shapes.Circle
Origin=(3,4), Radius=5
Origin=(-2,3), Radius=7
...

And we might store rectangles like this:

MyNamespace.Shapes.Rectangle
TopLeft=(0,3), BottomRight=(3,0)
TopLeft=(1,1), BottomRight=(4,-3)
...

The file format itself doesn't really matter, so don't get hung up on why it's not CSV, JSON, or XML. What's important is that we can use the format to store a list of values of any relevant type.¹

How would you design an API to deserialize the contents of such a file? You might start with something like this:

static IList<T> DeserializeList<T>(string path)
{
   // implementation
}

var circles = DeserializeList<Circle>("Circles.txt);
var rectangles = DeserializeList<Rectangle>("Rectangles.txt");

This works great, but only if you know the type contained in each file ahead of time. What if you need to be able to deserialize an arbitrary file without knowing the type of objects it contains at compile-time?

var values = DeserializeList<???>("Arbitrary.txt");

We could potentially use obj as the type variable, so that values is of type IList<obj>:

IList<obj> values = DeserializeList<obj>("Arbitrary.txt");

The problem with this approach is that an IList<obj> (or a non-generic IList) could contain a mixture of different types of objects. We don't want to lose the fact that all the values in a given file are in fact of the same type. Is there a way to represent this in C#?

Existentially quantified types

Ideally, we'd want to write the signature of DeserializeList like this:

static ∃T.IList<T> DeserializeList(string path)   // not legal C#
{
   // implementation
}

We've introduced ∃T., which means "there exists a type T", so ∃T.IList<T> is a generic list containing items of some unspecified type. We call ∃T.IList<T> an existentially quantified type. Note that we no longer pass a type parameter to DeserializeList at all, since there's no way to know the actual type that T represents at compile-time.

Obviously, existential types are not directly supported by C#. But is there a way to emulate them using universal types instead? The answer is yes, but the solution is not at all obvious. We'll cover it next time.

Note that the first line of the file contains the name of the stored type. We can use this metadata to dynamically instantiate the type at runtime (via reflection or some other mechanism). ↩

Universally quantified types in C#

Brian Berns — Sat, 14 Mar 2020 03:13:52 +0000

Generic types

Generic types in C# are universally quantified. That means, for example, that List<T> can contain elements of type T for any type T. To make the universal quantification explicit, we could imagine defining this type as:

public class ∀T.List<T> : IList<T>, ...   // not legal C#
{
   ...
}

C# leaves out the ∀T. part (which means "for all T"), but it's implied.

You can think of a universally quantified type such as List<T> as a type-level function that takes a type as input (e.g. int) and returns a type as output (e.g. List<int>). T is called a "type variable", since it represents an arbitrary type.

Parametric polymorphism

Generic types in C# are an example of what functional programming calls parametric polymorphism. Interestingly, C# generics implement let-polymorphism, which is somewhat more limited than full-blown first-class polymorphism.

Imagine that we're implementing an algorithm that has to work with generic lists. We need to be able to compute the "weight" of such a list, where the weight is an integer that is calculated somehow from a list. There might be multiple different ways of calculating a list's weight, so we have to be prepared to work with any of them. In particular, our job is to implement the following function:

// fix this so it compiles and runs successfully
static int SumWeights(
    IList<int> ints,
    IList<string> strs,
    /*some type*/ getWeight)
    => getWeight(ints) + getWeight(strs);

As you can see, this function is passed two lists and has to sum their weights, as calculated by the given getWeight function. Our only problem is that we have to specify a type for getWeight. Since it's a function that converts a list to an integer, we can try to define the type as Func<IList<T>, int>:

static int SumWeights(   // compiler error
    IList<int> ints,
    IList<string> strs,
    Func<IList<T>, int> getWeight)
    => getWeight(ints) + getWeight(strs);

The compiler doesn't accept this, though, because type variable T isn't defined anywhere. That should be easy enough to fix, right? We just have to declare T next to the SumWeights name itself:

static int SumWeights<T>(   // compiler error
    IList<int> ints,
    IList<string> strs,
    Func<IList<T>, int> getWeight)
    => getWeight(ints) + getWeight(strs);

But that doesn't work either! The compiler says it can't convert an IList<int> or an IList<string> to an IList<T>. This makes sense, though, because by changing SumWeights to SumWeights<T> we made it generic, and the type represented by T is now determined by the caller of the function. The compiler is telling us that we can't assume that T is either int or string (and it's certainly not both at once).

What's going on here? The problem is that we want to control the scope of the type variable T so that it applies only to getWeight, not to the entire SumWeights function. Ideally, we'd like to write the type of getWeight like this:

static int SumWeights(   // compiler error
    IList<int> ints,
    IList<string> strs,
    ∀T.Func<IList<T>, int> getWeight)
    => getWeight(ints) + getWeight(strs);

We've added ∀T. here to declare the type variable T and show the compiler that its scope should be limited to type of getWeight. Of course, however, this isn't legal C#.

What's the best way to work around this limitation of generic types in C#? How would you implement the SumWeights function so it compiles and successfully adds the weights of the two given lists, using a function supplied by the caller to determine the weight of any given generic list? If you have an idea, suggest it in the comments!

Credit for this idea goes to Nicholas Cowle.

Avoiding mutable classes in C#

Brian Berns — Mon, 17 Feb 2020 03:45:22 +0000

GeoPoint

Consider a class that represents a point on the surface of the earth, with the following invariants:¹

Latitude is always between -90° and 90°.
Longitude is always between -180° and 180°.

Let's implement this class, focusing on construction first:

using Degrees = System.Double;

class GeoPoint
{
    public GeoPoint(Degrees latitude, Degrees longitude)
    {
        _latitude = latitude;
        _longitude = longitude;
        Normalize();
    }
    private Degrees _latitude;
    private Degrees _longitude;

    private void Normalize()
    {
        _latitude = Math.Max(Math.Min(_latitude, 90), -90);
        while (_longitude <= -180) _longitude += 360;   // inefficient, but clear
        while (_longitude > 180) _longitude -= 360;     // inefficient, but clear

        Debug.Assert(_latitude >= -90 && _latitude <= 90);
        Debug.Assert(_longitude > -180 && _longitude <= 180);
    }

    public override string ToString()
        => string.Format($"{_latitude}, {_longitude}");
}

The main thing to notice here is the Normalize method, which enforces the class invariants. If we try to create a geopoint with non-standard coordinates, normalization will bring them in bounds:

var pt = new GeoPoint(100, -300);
Console.WriteLine(pt);

// output:
// 90, 60

Globetrotting

Next, let's add a way to move a geopoint:

public void Move(Degrees latitudeChange, Degrees longitudeChange)
{
    _latitude += latitudeChange;
    _longitude += longitudeChange;
    Normalize();
}

We can try it out like this:

var pt = new GeoPoint(0, 0);
for (var i = 0; i < 10; ++i)
{
    pt.Move(5, 30);
    Console.WriteLine(pt);
}

// output:
// 5, 30
// 10, 60
// 15, 90
// 20, 120
// 25, 150
// 30, 180
// 35, -150
// 40, -120
// 45, -90
// 50, -60

What do you think of this class so far? Is it ready for use, or does it need more work?

Immutability

One issue that jumps out at me is that Move mutates the object's fields. This is a potential problem because two different threads attempting to move the same point simultaneously could corrupt it - one thread could read the object at the same time the other is in the middle of updating it. That's a bug waiting to happen. We could protect against this with careful use of lock statements, but that's tricky and could even become a performance bottleneck.

Fortunately, there is a better way: immutability. The first thing we have to do is make our class's fields read-only:

private readonly Degrees _latitude;
private readonly Degrees _longitude;

With this change in place, we can be certain that the class is thread-safe, because race conditions are no longer possible. I'd go as far as to say that any time you declare a variable in C#, it's good practice to at least consider making it readonly. You can save yourself a lot of grief that way.

We now have to revise the class's implementation, since both Move and Normalize are mutating. Can we turn them into pure functions instead? To start with, let's change Normalize into a static function that takes a pair of arbitrary coordinates as input and returns normalized coordinates as output:

private static (Degrees, Degrees) Normalize(Degrees latitude, Degrees longitude)
{
    latitude = Math.Max(Math.Min(latitude, 90), -90);
    while (longitude <= -180) longitude += 360;   // inefficient, but clear
    while (longitude > 180) longitude -= 360;     // inefficient, but clear

    Debug.Assert(latitude >= -90 && latitude <= 90);
    Debug.Assert(longitude > -180 && longitude <= 180);

    return (latitude, longitude);
}

Even though Normalize continues to mutate variables internally, there are no side-effects visible to the caller, so it is now a pure function. (Exercise for the reader: Rewrite the function body to eliminate internal mutation as well.)

Initialization in the constructor can then be simplified to a single line:

public GeoPoint(Degrees latitude, Degrees longitude)
{
    (_latitude, _longitude) = Normalize(latitude, longitude);
}

Next, we have to change the semantics of moving a geopoint. Instead of modifying the point's coordinates in place, we create and return a separate point that represents the new location:

public GeoPoint Move(Degrees latitudeChange, Degrees longitudeChange)
    => new GeoPoint(_latitude + latitudeChange, _longitude + longitudeChange);

Both geopoints remain valid, as "before" and "after" snapshots. This can actually be a very helpful way to maintain history.

Our test code now looks like this:

var pt = new GeoPoint(0, 0);
for (var i = 0; i < 10; ++i)
{
    pt = pt.Move(5, 30);
    Console.WriteLine(pt);
}

The output is the same as before.

Wrap up

By making the class immutable, we've not just eliminated a possible bug - we've also made the class easier to reason about, because we no longer have to worry about how the state of an object might change over time. Instead, a geopoint now represents a single fixed value, much like a .NET string or an integer does. Immutability and value semantics are key principles of functional programming.

But wait. This actually raises a second problem, which is that the class doesn't quite behave the way we expect when we compare two values:

var a = new GeoPoint(0, 0);
var b = new GeoPoint(0, 0);
Console.WriteLine(Object.Equals(a, b));

// output:
// False

Fixing this isn't too hard, but can be a bit subtle. Maybe someone will take a shot at it in the comments!

This example is adapted from the Wikipedia page on class invariants. ↩