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] }
}
  • var tail : Array {
    return Array(self[1..count])
    }

  • Sam Isaacson

    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?