Railroad Junction Photo

Sum Algebraic Data Types in Haskell and Swift

"Grove Park Traincare Depot and sidings" (CC BY-SA 2.0) by train_photos

Engineers at Metal Toad participate in a variety of continuing education such as the Hackathon, dedicated time for professional development, and various interest groups for a variety of topics like machine learning and iOS/Android development.

Haskell

I recently joined the interest group on functional programming in Haskell. We start with an introduction to Algebraic Data Types.

Algebraic Data Types are types formed by combining other types. There are product types, which is a combination of two types (like a struct or tuple), and there are sum types, which can be only one of a possible set of options, but not two at the same time.

The canonical example of a sum type is a List. Here is a definition in Haskell:

data List a = Nil | Cons a (List a)

The possible list of options for this list is either that it will be empty, or it will be a construction of a head element followed by another List a. From this simple definition we can construct a list of any size.

For an empty list, List a will simply be the empty list. For a list with one element, List a will be a construction of the single head element and an empty list. From this we have enough to construct a list of any size simply by defining what options we are constructing List a from. In other words, a list of any size is just the starting head element followed by the rest of the elements, or an empty list.

Another example of a sum type is the following type to represent expressions involving addition and multiplication of integers. (operations over integers could include many more that are omitted here for simplicity)

data Expr = Add Expr Expr
          | Mult Expr Expr
          | Value Int

Here, type Expr is defined as either the integer value, the addition of two Expr types or the multiplication of two Expr types.

Swift

In Swift, sum types are expressed as enumerations. Let's express the sum type of addition and multiplication over integers in Swift.

enum Expr {
    indirect case add(Expr, Expr)
    indirect case mult(Expr, Expr)
    case number(Int)
}

The indirect keyword here is used to indicate that the enumerated case is recursive. In this case, both addition and multiplication is recursively defined as an operation over a pair of Expr. This allows us to perform compound arithmetic operations.

To define a value for each operation let's create a computed property for the enumeration:

extension Expr {
    var value: Int {
        switch self {
        case .add(let x, let y): return x.value + y.value
        case .mult(let x, let y): return x.value * y.value
        case .number(let x): return x
        }
    }
}

We have now defined the possible options for a sum type and a way to derive its value. Let's try it out.

We can represent a single number:

Expr.number(5).value    // Returns 5

We can add two numbers:

Expr.add(Expr.number(1), Expr.number(2))    // Returns 3

Since the operations for addition and multiplication is defined recursively, we can have compound expressions:

let three = Expr.add(Expr.number(1), Expr.number(2))
 
Expr.mult(three, Expr.number(3)).value      // Returns 9

Conclusion

In Haskell, data is modeled by Algebraic Data Types. They can be of product types or sum types. In Swift, product types can be expressed through structs while sum types can be expressed through enumerations. In Swift, just like in Haskell, these types use value semantics, which provides a guarantee that once created they are immutable.

Modeling Data in Swift can be thought in terms of how they are modeled in Haskell, whether we are thinking of a list of possible states or a collection of records.

Filed under:

Add new comment

Restricted HTML

  • Allowed HTML tags: <a href hreflang> <em> <strong> <cite> <blockquote cite> <code> <ul type> <ol start type> <li> <dl> <dt> <dd> <h2 id> <h3 id> <h4 id> <h5 id> <h6 id>
  • You can enable syntax highlighting of source code with the following tags: <code>, <blockcode>, <cpp>, <java>, <php>. The supported tag styles are: <foo>, [foo].
  • Web page addresses and email addresses turn into links automatically.
  • Lines and paragraphs break automatically.

About the Author

Phil Tseng, Software Engineer

Living by the adage: "You can do anything with a law degree," and decades of experience providing tech support to family and friends, Phil Tseng changed his career from Attorney to Software Engineer and received a degree in Computer Science from Portland State University in 2015. Phil is looking forward to refining his craft at Metal Toad.

Outside of work, Phil enjoys downhill skateboarding during the warmer months, downhill skiing during the colder ones, and yoga all year round to keep him zen and centered.

Ready for transformation?