Pranav Kasetti

This blog post is about how to write a recursive Either enum Haskell-style in Swift. Swift 2 introduced support for recursive enums (source), enabled using the indirect keyword.

Either enums are very common for Functional Reactive Programming applications, and are commonly used in languages such as Haskell.

Introduction

Swift has a very robust type system and this makes it hard to define type erased values not just for enums but throughout the language. While we could use @dynamicMemberLookup to enable dynamic type resoution, dynamic type resolution isn't encouraged because the paradigm fights against Swift's type safety for ensuring robust code.

Let's imagine a recursive stack, where we want to create a nested tree of values. This is hard to express using the Collection set of types. Thus, I wanted to see how far I could get working with the type system to create a generic Either enum with associated values.

What we want to write

We want to be able to declare an enum, which has a deepest left node value of 3:

let value = RecursiveEither<Int, Int>.left(.left(.left(.left(.value(3)))))

We will be able to nest values and enums within the enum through custom associated values.

Creating the associated value

An associated value typically can't contain another either enum, especially a generic nested enum or value! Thus, we model the problem using another enum with types for the value, left tree and right tree.

enum ValueOrLeftOrRight<Value, Left, Right> {
  case value(Value)
  indirect case left(ValueOrLeftOrRight<Left, Left, Right>)
  indirect case right(ValueOrLeftOrRight<Right, Left, Right>)
  
  var left: Left? {
    switch self {
    case .value(let left): return left as? Left
    case .left(let content): return content.left
    default: return nil
    }
  }

  var right: Right? {
    switch self {
    case .value(let right): return right as? Right
    case .right(let content): return content.right
    default: return nil
    }
  }
}

In order to wrap enums within associated values, I have used the indirect case syntax. The Swift Language guide explains why the enum is thus made recursive:

A recursive enumeration is an enumeration that has another instance of the enumeration as the associated value for one or more of the enumeration cases. You indicate that an enumeration case is recursive by writing indirect before it, which tells the compiler to insert the necessary layer of indirection. ~ The Swift Language Guide, Enumerations

We have used generic types for Value, Left and Right. This enables us to nest the same type of values for every Right node, and the same type of value for every Left node. Value represents a leaf node, that is one with no subtree nodes. Left and Right have children though.

The computed property .left enables us to traverse the current enum case. We return nil for nodes which don't have a .left value or subtree. We do the same technique for traversing the .right nodes.

Write the actual Either enum?

enum RecursiveEither<Left, Right> {
  case left(ValueOrLeftOrRight<Left, Left, Right>)
  case right(ValueOrLeftOrRight<Right, Left, Right>)
  
  var left: Left? {
    guard case .left(let leftie) = self else { return nil }
    return leftie.left
  }

  var right: Right? {
    guard case .right(let rightie) = self else { return nil }
    return rightie.right
  }
}

We can see that we can now unwrap values using .left and also use the the special enum wrapper declared above for the associated values . Notice how we've handled the case where we call .left on a .right enum case and vice versa elegantly using optionals. We could also throw an error in this scenario. I have kept things simple for this demo.

We've declared this as an enum so we need to use recursive computed properties to traverse the tree. We can also cleanly make a computed property to declare rightie.right upto a certain recursion depth (call stack depth) but I haven't included this function because YAGNI.

The end result

let e = RecursiveEither<Int, Int>.left(.left(.left(.left(.value(3)))))
let f = RecursiveEither<Int, Int>.right(.right(.right(.right(.value(9)))))

print(e.left as Any)
print(e.right as Any)
print(f.left as Any)
print(f.right as Any)

// Optional(3)
// nil
// nil
// Optional(9)

You're now ready to write Recursive Either enums! 👏

This is a good step forward for understanding functional programs. Unfortunately Swift is not purely functional like other languages such as Haskell, however SwiftUI and Combine do bridge the gap.

Resources

1. Recursive Enums in Swift, Apple
2. Haskell Either enums
3. My related SO post

TIP: Check out Pointfree for great FRP related tutorials in SwiftUI and Combine.