List Traversal with Discriminated Unions in Swift

… by decoupling how a function recurses over data from what the function actually does, we reduce cognitive overhead and can focus entirely on the core behavior of our recursive functions. No matter the structures in question—lists, directory hierarchies, control flow graphs, database records—recursion schemes bring us an orderly and predictable way to traverse them.
Link

Swift supports Discriminated Unions as first class citizens within the language. This creates interesting possibilities especially with respect to pattern matching. Here is an example of recursive traversal of a native Array with a discriminated union:

let list = [1,2,3,4,5]

func sum( l : Array<Int> ) -> Int {
  switch( l as Structure ) {
  case let .Cons(head, tail) : return head + sum(tail)
  case .Empty: return 0
  }
}

println(sum(list))  //Output: 15

Here the enum Structure is representation of contents of the list as a head::tail structure.

enum Structure<T>{
  case Cons( T, Array<T> )
  case Empty
}

The enumeration has two cases:

  • Empty: represents a list with no elements.
  • Cons: represents a list as two parts: a head element for the first element in the list and a tail list comprising the remaining list elements.

Finally, an Array extension provides type conversion between a list and its corresponding Structure representation:

extension Array {
  func __conversion() -> Structure<T> {
    switch(count) {
    case 0: return Structure.Empty
    case 1: return Structure.Cons(head, [])
    default: return Structure.Cons(head, tail)
    }
  }

  //Returns the tail of this list using copy semantics
  var tail : Array<T> {
  var t = Array<T>()
    for x in self[1..count] { t.append(x) }
    return t
  }

  //Returns the head element of the list (count must be >=1)  
  var head : T { return self[0] }
}

2 thoughts on “List Traversal with Discriminated Unions in Swift

  1. What would be the difference between constructing a list as above (via an enum) versus as entirely as a class? (1) If done in a class then we probably wouldn’t need an array as a backing store but could use a more ‘natural’ linked list like structure. (2) My question arises from my interest in the lack of recursive enum support in Swift…but if you can achieve a recursive enum-like construct via classes then what does it matter?

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s