Sum Types in Other Languages

Readme.md

Just a quick blog about how to represent discriminated unions, also called sum types.

What are they?

A union type allows you to store one of N distinct types in the same variable. What makes it discriminated is that, if the types overlap, you should still be able to tell the cases apart.

So for example maybe we want to define a variable context which might store either a FooContext or a BarContext or a BazContext, all of which are nullable types (for other reasons in our code, let's say). When we store a null FooContext in context, we want context to still be able to tell us that it's holding a FooContext, just the null version of that. That makes it a discriminated union.

These are called "sum types" because this lack of overlap means that if there were two valid values for FooContext (the null one and some global one, say), three for BarContext, and four for BazContext, the number of valid values for context would be 2+3+4. It could have been less than this if they were allowed to "overlap", but we forbade any overlap and so you get the direct sum. A conventional Union[Int32, Int32] would have 2³² possibilities as you can't tell the integers apart, but a Discriminated[Int32, Int32] has 2³³ possibilities because you know whether it's the first sort of integer or the second sort of integer.

Every datatype exists in a one-to-one correspondence with the control logic that would properly consume it. The proper consumption of a sum type is by a case dispatch, go through each possibility for what the sum type can be, and handle each one of them. So whenever you see a case dispatch, you know that in the abstract, a sum type is hiding somewhere underneath the logic. We might not get much from actually refactoring it that way, but we can recognize it as a possible refactoring even if it's not useful.

In languages that have them

This is kind of the most boring section, but for completeness, some languages just have these. Kotlin,

sealed class Context {
    data class Foo(val value: FooContext) : Context()
    data class Bar(val value: BarContext) : Context()
    data class Baz(val value: BazContext) : Context()
}
// consuming logic
when (context) {
  is Context.Foo -> ...
  is Context.Bar -> ...
  is Context.Baz -> ...
}

Haskell,

data Context = Foo FooContext | Bar BarContext | Baz BazContext

-- consuming logic
case context of
  Foo fooContext -> ...
  Bar barContext -> ...
  Baz bazContext -> ...

TypeScript,

type Context =
 | {type: 'foo', value: FooContext}
 | {type: 'bar', value: BarContext}
 | {type: 'baz', value: BazContext}
 
// consuming logic
switch (context.type) {
  case 'foo':
    ...
  case 'bar':
    ...
  case 'baz':
    ...
  default:
    assertNever(context.type)
}

(TypeScript requires you to write an explicit exhaustiveness check function for a case dispatch, but it still counts in my book.)

In SQL, also seen in Golang, Node.js, and some other places

If you needed to store one of these in a relational database, probably the simplest way that respects the relational integrity of your data involves separate foreign keys from nullable fields, plus a check constraint to make sure that too many of them aren't being set:

CREATE TABLE contexts {
   context_id SERIAL PRIMARY KEY,
   context_type SMALLINT NOT NULL,
   foo_context_id INTEGER REFERENCES foo_contexts(foo_context_id),
   bar_context_id INTEGER REFERENCES bar_contexts(bar_context_id),
   baz_context_id INTEGER REFERENCES baz_contexts(baz_context_id),
   CONSTRAINT context_case_dispatch CHECK(
     (context_type = 0 AND foo_context_id IS NOT NULL AND bar_context_id IS NULL AND baz_context_id IS NULL) OR
     (context_type = 1 AND foo_context_id IS NULL AND bar_context_id IS NOT NULL AND baz_context_id IS NULL) OR
     (context_type = 2 AND foo_context_id IS NULL AND bar_context_id IS NULL AND baz_context_id IS NOT NULL))
};

(Note that the context_type is just a convenience here, but it helps.) Storing properties next to each other like this, in type mathematics, is called a product type for much the same reason that sum types are called sum types. Meanwhile, making a type nullable, adds 1 to the number of cases that it makes. So this can very much be looked at as creating,

(1 + X)(1 + Y)(1 + Z) = 1 + X + Y + Z + XY + YZ + XZ + XYZ

and the CHECK CONSTRAINT here is basically subtracting off 1 + XY + YZ + XZ + XYZ to leave just X + Y + Z. This approach always more or less creates ambiguity when multiple fields are set simultaneoustly.

Now, product types occur in several other cases. For example if your language allows returning multiple values from a function, that's a product type. Or when a function takes multiple arguments, that's basically like taking those arguments as a tuple, which is another product type.

For a non-database example, old-school Node.js callbacks for asynchronous operations looked like this SQL example in how they returned errors:

fs.readdir(directory_name, (err, file_names) => {
  if (err) {
    // handle error if say the directory doesn't exist; return
    console.error(err);
    process.exit(1);
  }
  for (const file of file_names) {
    const subpath = path.join(directory_name, file)
    fs.stat(subpath, (err, entry) => {
      if (err) {
        // handle e.g. the race condition where file X is removed between the readdir() and the stat() call
        console.error(err);
        return;
      }
      if (entry.isFile()) {
        // handle files
      }
      if (entry.isDirectory()) {
        // maybe recurse into subdirectories
      }
    })
  }
})

This is two case-dispatches -- these are sum types!

Let's talk about the main way that this is suboptimal: by using a product-of-nullables to handle a sum type, you encourage peoples' brains to be on autopilot. Here's a different example from Node.js's filesystem library:

function streamDataToHandleWithRetry(handle, data, done) {
  fs.write(handle, data, (err, byteCount) => {
    if (err) {
      // sleep 0.5s, then retry
      setTimeout(() => streamDataToHandleWithRetry(handle, data, done), 500)
      return
    }
    if (data.length < byteCount) {
      data = data.slice(byteCount);
      // sleep 0.1s, then retry
      setTimeout(() => streamDataToHandleWithRetry(handle, data, done), 100)
      return
    }
    done()
  }

What's the bug? Hint, I said it's not a sum type, so case dispatch is not the right control structure here.

That's right: in if (err) we forgot to check how many bytes had been written, and we forgot to advance the data slice accordingly. So when errors occur we'll rewrite the same chunk twice, potentially.

The use of val, err := f(...) is idiomatic Golang; this has similar problems where the code that "looks right" handles the error by ignoring the return value, but every once in a while you do need to handle it and the API contract doesn't tell you when that is.

In OOP

Languages without discriminated unions often have generics and function types, which can be used to build discriminated unions with Church encodings:

// more idiomatic TypeScript, as per above
type Optional<x, y> = {type: 'absent', detail: x} | {type: 'present', value: y}

// The Church-encoded version of Optional<x, y>
type Either<x, y> = <z>(ifLeft: (x: x) => z, ifRight: (y: y) => z) => z
//        notice:    ^--- this generic allows a great deal of type safety

// converting between those two
function church<x, y>(opt: Optional<x, y>): Either<x, y> {
  return (ifLeft, ifRight) => opt.type === 'absent'? ifLeft(opt.detail) : ifRight(opt.value)
}
function unchurch<x, y>(opt: Either<x, y>): Optional<x, y> {
  return opt<Optional<x,y>>(x => ({type: 'absent', detail: x}), y => ({type: 'present', value: y}))
}

What was the Church encoding, here? It was a function that took N handler functions and called the appropriate one for the case that the data type was in. So in church() we take these functions ifLeft and ifRight and decide which to call; in unchurch() we provide two functions that will return values back in our idiomatic Optional type. Because you can freely convert between them without losing anything, any language where you can't write the first one, you might be able to write the second.

But let's also meditate on this idea of "N handler functions, call the appropriate one." With a little squinting, this is the Visitor pattern.

interface LeftRightVisitor<X, Y, Z> {
  visit(x: Left<X>): Z
  visit(y: Right<Y>): Z
}
interface LeftRight<X, Y> {
  accept<Z>(visitor: LeftRightVisitor<X, Y, Z>): Z;
}
class Left<X> implements LeftRight<X, any> {
  constructor(public readonly x: X) {}
  accept<Z>(visitor: LeftRightVisitor<X, any, Z>) {
    return visitor.visit(this)
  }
}
class Right<Y> implements LeftRight<any, Y> {
  constructor(public readonly y: Y) {}
  accept<Z>(visitor: LeftRightVisitor<any, Y, Z>) {
    return visitor.visit(this)
  }
}
// isomorphism
function visitify<X, Y>(opt: Optional<X, Y>): LeftRight<X, Y> {
  return opt.type === 'absent' ? new Left(opt.detail) : new Right(opt.value)
}
function unvisitify<X, Y>(opt: LeftRight<X, Y>): Optional<X, Y> {
  return opt.accept({
    visit(value: Left<X> | Right<Y>) {
      return value instanceof Left? {type: 'absent', detail: value.x} : {type: 'present', value: value.y}
    }
  })
}

The main difference with the usual visitor pattern is that the usual visitor pattern doesn't return anything (it expects you to be holding some mutable state and the visitor will mutate it), you can do that too if you don't have access to a suitable generic for the Z parameter.

So, lots of different ways to do the same thing. Some languages make this very ergonomic; some do not.