Ye old linked list

List.swift

class Box<T> {
  let unbox:T
  init(unbox:T) { self.unbox = unbox }
}

/*

Boxing is necessary because Swift does not allow recursive enum types.

However, AFAICT, is it also desirable here because it enables structural
sharing, which is safe for this persistent data structure.

The assignment `let newCell = oldCell` copies the struct oldCell to newCell,
copying
- the bytes in oldCell.value (representing an Int)
- the ptr in oldCell.tail (referring to a Box class)

Suppose the list is 1M cells long. Then `let newCell = oldCell` copies one 
Int and one reference, instead of 1M of anything.

*/

enum List {
  case Empty
  case Cell(value:Int,tail:Box<List>)
}

extension List : Equatable {}

func ==(lhs:List,rhs:List) -> Bool {
  switch (lhs,rhs) {
  case (.Empty,.Empty): return true
  case (.Cell(let lhsValue, let lhsTail),.Cell(let rhsValue, let rhsTail)):
    return lhsValue == rhsValue && lhsTail.unbox == rhsTail.unbox
  default:
    return false
  }
}

extension List : Printable {
  var description : String {
    switch self {
    case .Empty: return "[]"
    case .Cell(let val, let boxTail):
      let tail : List = boxTail.unbox
      let d = tail.description
      return "[\(val), \(d)]"
    }
  }
}

// ctors

func isEmpty(list:List) -> Bool {
  return list == List.Empty
}

func emptyList() -> List {
  // returns a fresh empty list
  return List.Empty
}

func cons(value:Int,list:List) -> List {
  return List.Cell(value: value, tail: Box(unbox: list))
}

func tail(list:List) -> List {
  switch list {
  case .Cell(_,let boxTail):
    return boxTail.unbox
  default:
    assertionFailure("called tail() on an empty list")
  }
}

func head(list:List) -> Int {
  switch list {
  case .Cell(let v,_): return v
  default:
    assertionFailure("called head() on an empty list")
  }
}