Adding Either type to the Standard Library

Evolution Discussion
52

What follows is a bunch of examples that show how anonymous sum types can be not only useful in Swift, but could also push the language ahead in the competition space of current general purpose programming languages, and attract potential users that want a more powerful type system, without renouncing simplicity and accessibility.

A possible design

To show the examples, I need to come up with a preliminary design and syntax for the feature. First of all, with "anonymous sum types" I mean "non nominal" types similar to tuples, with same (but dual) features, and the same semantics of enums. These types could be defined as follows:

  • (A | B | C) means "either A or B or C", and each case can be accessed with the patterns case .0(let a), case .1(let b) and case .2(let c), and constructed in a similar way, with .0(a), .1(b) and .2(c);
  • optionally, each case can have a label, like (first: A | B), that would be accessed via case .first(let a) and case .1(let b), and constructed via .first(a) and .1(b);
  • if a case has no associated type, it could be written as just the label, without the type, like (some: A | none:), would be accessed with case .some(let a) and case .none, and constructed via .some(a) and .none;

This is just a possibile syntax, to show the examples: the specifics should be discussed, but the base features are there. Also, let's invent some name: let's call them union tuples.

Notice that we could achieve some of the results highlighted in this post with a weaker addition to Swift, that is, a bunch of Either<A, B, ...> types in the standard library, but it would be a lot less useful, for not being able to define case labels on the fly, and for the awkwardness in handling cases with no associated types.

How to come up with examples? It's simple. Just consider every case where a regular tuple is used, or could be used, replace it with a union tuple, and examine what you got there. This forms the basis of the "dual construction procedure" where I take an available construction, produce (or more appropriately, "discover") the dual one, and examine the result. I'm pointing this out because many people are probably not familiar with what duality means when dealing with abstract mathematical concepts (for example, type systems). In very simple terms, "dual", for a concept or structure, means "translated into a similar concept or structure where relationships are reversed". The dual transformation doesn't mean anything in itself, nor proves anything other than the fact that something "exists": it just allows to "discover" stuff. But, in some cases, what we discover turns out to be extremely useful.

A prime example is the structural duality between structs and enums: both are extremely useful when modeling domains, because they allow for a correct representation of entities for which two or more things could be grouped together (structs) or alternative and mutually exclusive states (enums) could be defined. For a better understanding of the reason why structs and enums are dual to each other, I suggest to read the "Bonus Theory" section of this old post of mine.

Union tuples would be the structural dual of regular tuples, so we can try and consider examples of tuple usage, replace with union tuple, and examine what we end up with.

Heterogeneous sequences

The zip function, in Swift, takes two sequences, respectively of A and B, and produces a single sequence of (A, B). A sequence of tuples is a sequence in which each element consists of two distinct things: if we had no first-class tuples in Swift, the zip function would probably produce a sequence of some Tuple<A, B> struct, that would be much more awkward to work with.

What's the structural dual of a sequence of (A, B)? It's a sequence of (A | B), of course. And what does it mean? Well, each element of this sequence is either A or B: this is the exact definition of an heterogeneous sequence, that is, a sequence where elements could be different from each other. I'm sure many of us needed at least once to represent this kind of sequence: there are "dynamic" ways of doing it, of course, like defining a sequence of Any, or putting all possible types under an umbrella protocol, but we like to be precise, and take advantage of the type system (not to mention, dynamic solutions are slow).

Consider for example a Swift library for defining forms. There could be different types of fields, like TextField, RadioButtonField and SubsectionField. If we wanted to define a collection of fields, in order to work on all our fields together (for extracting some information, for example), a precise way to do this could be to define a specific FieldKind enum, like the following:

enum FieldKind {
  case text(TextField)
  case radioButton(RadioButtonField)
  case subsection(SubsectionField)
}

Then, we would work with some [FieldKind] array. But the only reason we defined this enum is to be able to work with such heterogenous collection. Also, if we had the specific collections of single fields, to "merge" them into an heterogeneous collection, we would need to tediously do the work by hand, without the option to generically define an algorithm to merge collections of A, B or C into a single collection of (A | B | C). With union tuples, we could generically define a function like the following:

func merge<S1, S2>(_ s1: S1, _ s2: S2) -> Merge2Sequence<S1, S2> where S1: Sequence, S2: Sequence { ... }

/// Merge2Sequence<S1, S2>.Element == (S1.Element | S2.Element)

Then, from a Sequence of (A | B), we could define generic methods like:

extension Sequence {
func partition() -> ([A], [B]) { ... } where Element == (A | B)

func collapse() -> ([(A, B)], discarded: [(A | B)]) { ... }  where Element == (A | B)

Heterogeneous streams

Many things that we can say for sequences, we could also say for streams (observables). In the various FRP frameworks we sometimes deal with streams of tuples, like Observable<(A, B)>: that's the case when we want to move more than 1 thing at a time further into the signal chain (for example, some kind of context). What's an Observable<(A | B)>? It's a signal where each event can be of either one of 2 types. This naturally occurs many times when using FRP, when an observable chain "splits" in 2. For example, given a user's behavior, we could produce Cake or Broccoli:

let food = Observable<User>.getFromServer()
  .map { /// Swift should be able to infer the type here
    $0.didBehave 
      ? .0(Cake())
      : .1(Broccoli())
  }

What you would normally do, here, is to produce 2 distinct observables, handle them separately, then merge them: the problem here, other than being forced to juggle many observables and having to instantiate more stuff, could be one of sharing the subscription between the 2 observables, in order to avoid duplication of emissions.

With an Observable<(Cake | Broccoli)>, we could handle all in a single chain:

let ingredients = food
  .flatMap0 { cake in
    getIngredientsFromServer(for: cake)
  }
  .map1 { broccoli in 
    [Ingredient(broccoli)]
  }
  .merge() /// Observable<[Ingredient]>

In general, when there's some kind of sequence, stream, stack, dictionary of heterogeneous things, if we want to model it precisely, we need to use enums: the problem is, there's no reason to define specific, nominal types for this use case, and the possibility to define anonymous enums on the fly, and to talk generically about them (like an enum of A or B) unlocks great conveniency and powerful algorithms.

Functions: alternative return types

Tuples allow for one of the most requested programming language features of all time: returning "more than one thing" from a function. A function like the following

extension Collection {
  var destructured: (head: Element, tail: SubSequence)? {
    first.map {
      (head: $0, tail: dropFirst())
    }
  }
}

returns (optionally) 2 things: the product of those things doesn't make a "thing" in itself (hence, it doesn't need a named type, like a struct), and it's more than enough to use a purely structural type like a tuple.

What's with a function returning a union tuple? We actually already have something very similar in functions that return the Result type:

extension String: Error {}

extension Dictionary where Value == Any {
  func get<A>(_ type: A.Type, at key: Key) -> Result<A, String> {
    guard let value = self[key] else {
      return .failure("No value at \(key)")
    }

    guard let typedValue = value as? A else {
      return .failure("Value at \(key) is not of proper type: required \(A.self); found \(value)")
    }

    return .success(typedValue)
  }
}

But Result is only for a very specific subset of all cases where we might want to return a sum type: in particular, it's for "failable" functions, that either return a value, or an Error. With Result, the secondary type must be an Error, and there is no third option.

A common case where we might want to have a third option is for computations that can fail but that can also be canceled. Instead of adding another specific named type in our toolbox, we could simply use a union tuple:

func executeFailableCancelableOperation() -> (succeeded: Value | failed: Error | canceled:) { ... }

Notice that the canceled: case has no associated type. One could express a similar idea with an optional Result<Value, Error>?, but the nil case wouldn't be clear. In fact, another important feature of union tuples is exactly the added clarity. Consider the differences between the following definitions:

func executeFailableCancelableOperation() -> Result<Value, Error>? { ... }

func executeFailableCancelableOperation() -> (completed: Result<Value, Error> | canceled:) { ... }

In general, a union tuple can be used to clearly signal alternative states even when there's no associated type, like for replacing a Bool where more informative labels can add the appropriate context:

/// This a classic code smell, where we're returning a value, from a function, that describes something about what the function did, but with the inappropriate type, even if there's only 2 options: the execution started, or it didn't.
func startExecution() -> Bool { ... }

/// With an union tuple, we can use labels to represent the alternative states, and the function signature becomes much more clear.
func startExection() -> (started: | cannotStart:) { ... }

I actually still didn't consider the prime example for using union tuples in function return types: when we're simply returning either a certain thing, or another, without any of them being the "main" one.

var foodRequirement: (
  Milk |
  Cookies
) { ... }

Even better, the two tuple types could be combined for defining more sophisticated structures:

var foodRequirement: (
  Milk |
  Cookies |
  (Milk, Cookies)
) { ... }

That's it: we can easily discover that Result is a very special case of a more general thing that union tuples model very well.

Functions: alternative inputs

What about function inputs/arguments? Do we use tuples in function arguments? Not really, and that's because functions can be defined as accepting more than one argument. A function accepting 2 arguments A and B is essentially the same as a function accepting a single argument of type (A, B); I wrote essentially the same because they're not completely the same: function arguments can be @escaping or not, can have default values, can be inout or @autoclosure, so there are differences. But if we esclude these cases we can say that, in essence, func foo(_ a: A, _ b: B) and func foo(_ ab: (A, B)) have basically the same semantics. So, dually, what does it mean func foo(_ ab: (A | B))? Well, it's a function that can be called with A or B: not both of them together, but either one works fine.

A function that can be called with 2 different arguments is, essentially, a pair of overloaded functions:

func foo(_ a: A) { ... }

func foo(_ b: B) { ... }

/// The pair is equivalent to:

func func(_ ab: (A | B))

We could introduce argument labels to avoid overloading, but if the base name is the same (and argument labels don't qualify the name any further) it should mean that's we're probably dealing with the same operation, just applied to different things:

func foo(a: A) { ... }

func foo(b: B) { ... }

/// The pair is equivalent to:

func func(_ ab: (a: A | b: B))

Is there a particular advantage in defining a function with a union tuple instead of 2 or more overloaded/base-homonym functions? I can think of a few:

  • overloaded/base-homonym functions can be confusing to use and understand, because to actually be aware that the same function could be called with different arguments I need to read all definitions (for example in autocompletion), so the lone signature in itself is not enough;
  • in cases like these, it's frequent to have some code that's shared among the functions, and that requires a definition of an additional private function for the common part, that's called from all the specific functions;
  • if I'm writing a library, each new public function of this kind extends the library surface.

Consider for example a function to handle and process some kind of "event":

struct Action {}
struct Change {}

enum Event {
  case action(Action)
  case change(Change)
}

func handle(_ event: Event) { ... }

The enum Event is really there just for defining a single function to handle everything. It has no methods, and cases' names are the same as the associated types, so there's no special semantics attached to the type, but without it, we would need to define two separate functions:

func handle(action: Action) { ... }
func handle(change: Change) { ... }

which could make us incur in the problems I listed earlier. With union tuples, we could have both simplicity and expressive power:

func handle(
  _ event: (
    action: Action |
    change: Change
  )
) { ... }

Also, if we needed to add a SideEffect event, it would be as easy as modifying the function signature (in a backwards-compatible way):

func handle(
  _ event: (
    action: Action |
    change: Change |
    sideEffect: SideEffect
  )
) { ... }

Interestingly, if this was a public function in a library, we wouldn't need to expose a public Event enum, to which adding a case wouldn't be, semantically, backwards compatible! Even if it wouldn't be breaking (if no @frozen), in cases where one cares about what they're publicly exposing, defining a public enum for mere structural purposes exposes a nominal type to the users that really shouldn't be.

It can be also really useful to use union tuples without associated types as function parameters dedicated to select some kind of option, like for example:

func compute(_ strategy: (statically: | dynamically:)) -> Int { ... }

let x = compute(.statically)

Also, adding cases would be simple and expressive.

Conclusion

Everyone loves examples, and they're certainly useful to explain something. But I think that the case for union tuples can really stand on its own just from the basic theory, thanks to dual relationship with regular tuples: this very relationship is the actual argument here. Examples are not arguments, in deductive reasoning. Examples are arguments only in inductive proofs, something that's basically impossible in software development, because there's potentially an infinite number of cases, and an huge number of ways in which any possible thing could be done. I'm sure that many people don't care about anonymous sum types, but that could simply be because they're not used to think in generic terms about sum types, or because they don't care about algebraic data types in general (I can say they would be missing a lot). But if one does, I don't see how they could not perceive the potential of these union tuples, given the already visible power of regular tuples.

14 Likes