What? and Why?

What's an algebraic data type you may ask. Sure you know some algebra like 5 + x = 7. But what has this to do with data types? An algebraic data type is based more on the idea of algebraic structures, which are a set of possible values and one ore more operators to combine a finite number of these values to a single one. A well known structure for example is (ℤ, +, -), the set of all integers with the plus and minus operations on them.

So an algebraic data type is a data type, that is created by algebraic operations. Specifically by sum and product as our operations. See the following example in Haskell for it.

-- product means a combination of values. In this case two Ints
data Point = Point Int Int

-- sum means an alternation between values. True or False, but not both
data Bool = True | False 

-- and of course you can mix them 
-- and make them more generel with type parameters
data Either a b = Left a | Right b  

Algebraic data types are really great in Haskell, they let you construct complicated data types like Lists and Trees very easily. You can use type parameters to make them more generel and most importantly they are always distinguishable from one another. So you can use pattern matching to make decisions and bind variables.

-- We implemented both geometric points and complex numbers
-- as type aliases of a (Double, Double)-Tuple. The problem with
-- that is, we can have a function that is doing computation with
-- complex numbers and can feed it geometric points without any trouble
-- cause they are actually both 
-- just (Double, Double)-Types
type Point = (Double, Double)  
type Complex = (Double, Double)

-- The same with algebraic types 
-- gives us two distinguishable types
-- Because the different type constructers
-- are giving context to the values
data Point = Point Double Double  
data Complex = Complex Double Double

-- And we can define a type safe function on complex numbers
addComp :: Complex -> Complex -> Complex  
addComp (Complex r1, i1) (Complex r2, i2) = Complex (r1 + r2) (i1 + i2)  

Implementation in Swift

If you already have experience with Swift I guess you think quit intuitively about implementing them with enums. And you're right. They have all it takes to implement algebraic data types, but there are a few problems with them, which I will explain. But first let's see how well they're doing without any tricks. We have alternation with case and we have combination with associated values. Let's have a look.

enum Either {  
    case Left(String)
    case Right(Int)
}

// We have two distinguishable constructors 
// and can pattern match, just like in Haskell
let result = Either.Left("My Horse is amazing!")

switch result {  
    case .Left(let a): print(a)
    case .Right(let b): print("There was an error with code: \(b)")
}

So where is the problem? The problems lies in the nature of enums being value types, so their size must be known at compile time. Therefore we can not have generics and recursive structures.

Let's plant a tree

Let's challenge ourselves by implementing a tree with enums in Swift and wipe out all the problems along the way. But first let's see how our intended goal looks like in Haskell. Just for the sake of beauty.

data Tree a = Leaf a | Node (Tree a) (Tree a)

inTree :: Eq a => a -> Tree a -> Bool  
inTree x (Leaf a) = a == x  
inTree x (Node r l) = (inTree x r) || (inTree x l)  

Recursion

Every node in a tree contains two subtrees a left and a right one. So we need recursion in our data structure.

enum Tree {  
    Leaf(Int)
    Node(Tree, Tree)
}

The problem with value types like enum is, that the compiler must know its size at compile time. Because associated values in an enum are part of the enum itself, the compiler, while trying to calculate the size of a recursive enum, will encounter the same enum inside of it and tries to calculate its size and there it will find another enum and so on, till infinity.

And because our machines are finite we can't have infinite data structures (except in Haskell of course). So we need to make our enum inside the enum a reference type. Then our associated value would just be a pointer of a fixed size. We can to do this in one of two ways which are both adding a level of indirection. Either by an array-type or through a protocol.

// with an array-type
enum Tree {  
    Leaf(Int)
    Node([Tree], [Tree])
}

// with a protocol
protocol TreeLike {}  
enum Tree : TreeLike {  
    Leaf(Int)
    Node(TreeLike, TreeLike)
}

I really like the solution with a protocol a lot more. It brings its own tradeoffs, especially with type inference, but we come to that later. The first solution is bad in the premise that we need to wrap and unwrap the subtrees in an array every time we construct them or access them and in the fact that a node could actually have more than two subtrees.

Generics

Like I explained above an enum is a value type, so the compiler must know its exact size, therefore we can't use generic types for our associated values. That means if we want a tree of int and a tree of string we have to create two different types.

The solution for this is yet another layer of indirection. We wrap the value in a closure. Like the pointer in the previous solution for recursion, a closure has a fixed size no matter what its contents are. And we're doing it with a really cool feature called @autoclosure. @autoclosure enables us to just pass an expression which will then be automagically wrapped in a closure. Let's see an example.

func foo(cond: @autoclosure () -> Bool) {  
    if (cond()) {
        print("Seems true to me.")
    }
}

foo(2 < 4) // Will print the message.  

But we have to be carefull though, because the closure will be evaluated everytime we access its value. Which means we have to make sure our expression doesn't have any side effects. An example for side effects would be the following.

enum Wrapper<T> {  
    case Value(@autoclosure () -> T)

    internal var value: T? {
        switch self {
        case .Value(let value):
            return value()

        default:
            return nil
        }
    }
}

var v: Int = 0  
let wrapper = Wrapper.Value(++v)

wrapper.value // 1  
wrapper.value // 2  
wrapper.value // 3  

Just keep this in mind, when using @autclosure. But except for this flaw, we have a really cool trick to build our generic tree now.

protocol TreeLike {}

enum Tree<T> : TreeLike {  
    Leaf(@autoclosure () -> T)
    Node(TreeLike, TreeLike)
}

Screw you type inference

The only problem left is the construction of trees. Because our TreeLike type can't carry the generic type down the tree, the type inference is confused with types of leafs inside nodes. This is no problem with one node, we can tell the compiler the type like so.

let tree : Tree<Int> = Tree.Node(.Leaf(2), .Leaf(3))  

But it gets a problem with more nodes.

let tree : Tree<Int> = Tree.Node(Tree.Leaf(2), Tree.Node(Tree.Leaf(3), Tree.Leaf(5)))  
// Cannot convert the expression's type
// '(Tree<T>, Tree<T>)' to type 'IntegerLiteralConvertible'

The simple solution is a function with a return type of Tree<T> for constructing our nodes.

func node<T>(left: Tree<T>, right: Tree<T>) -> Tree<T> {  
    return Tree.Node(left, right)
}

let tree : Tree<Int> = node(node(.Leaf(2), .Leaf(3)), node(.Leaf(5), .Leaf(7)))  

The final solution will look like this.

protocol TreeLike {}

enum Tree<T> : TreeLike {  
    case Leaf(@autoclosure () -> T)
    case Node(TreeLike, TreeLike)
}

func node<T>(left: Tree<T>, right: Tree<T>) -> Tree<T> {  
    return Tree.Node(left, right)
}

let tree : Tree<Int> = node(node(.Leaf(2), .Leaf(3)), node(.Leaf(5), .Leaf(7)))


func searchInTree<T: Equatable>(search: T, tree: Tree<T>) -> Bool {  
    switch tree {
    case .Leaf(let x):
        return x() == search
    case .Node(let l as Tree<T>, let r as Tree<T>):
        return searchInTree(search, l) || searchInTree(search, r)
    default:
        return false
    }
}

searchInTree(5, tree) // will return true  

Conclusion

When it's done you can implement complex data structures like trees very easily and enjoy all the convenience of processing them with pattern matching. But it's not very straightforward to get there. So I hope the Swift team will implement some indirection under the hood to make recursive, generic enums a thing in Swift.


  1. Gist of final solution
  2. https://wiki.haskell.org/Algebraicdatatype
  3. Stackoverflow: Strange Behaviour for Recursive Enum
  4. Fixed Enum Layout
  5. Stackoverflow: How to use Swift Autoclosure
  6. Apple Documentation: Enums