Experimenting with functional data structures

FunctionalDataStructures.swift

enum Tree<A> {
  indirect case node(A, left: Tree<A>, right: Tree<A>)
  case empty
}

extension Tree {
  static func singleton(_ a: A) -> Tree {
    return .node(a, left: .empty, right: .empty)
  }
}

extension Tree: Equatable where A: Comparable {

  func insert(_ a: A) -> Tree {
    switch self {
      case .empty:
        return Tree.singleton(a)
      case let .node(b, left, right):
        switch a {
          case _ where a == b: return .node(b, left: left,           right: right)
          case _ where a < b:  return .node(b, left: left.insert(a), right: right)
          case _ where a > b:  return .node(b, left: left,           right: right.insert(a))
          default: fatalError("Impossible")
        }
    }
  }
  
  func elem(_ a: A) -> Bool {
    switch self {
      case .empty: return false
      case let .node(b, left, right):
        switch a {
          case _ where a == b: return true
          case _ where a < b:  return left.elem(a)
          case _ where a > b:  return right.elem(a)
          default: fatalError("Impossible")
        }
    }
  }
}

extension Tree: CustomStringConvertible where A: Comparable {
  var description: String {
    switch self {
      case .empty:
        return "Empty"
      case let .node(a, left, right):
        let appendLeft: String = left != .empty ? "\n" : ""
        let appendRight: String = right != .empty ? "\n" : ""
        return "Node \(a) \(appendLeft)\(left) \(appendRight)\(right)"
    }
  }
}

let nums = [8, 6, 4, 1, 7, 3, 5]
let numsTree = nums.reversed()
  .reduce(into: Tree<Int>.empty) { partialResult, value in
    partialResult = partialResult.insert(value)
  }

print(numsTree)

numsTree.elem(8)
numsTree.elem(100)
numsTree.elem(1)
numsTree.elem(10)


enum List<A> {
  indirect case cons(a: A, list: List<A>)
  case empty
}

extension List: Equatable where A: Equatable {}

extension List {
  
  func head() -> Optional<A> {
    switch self {
      case .empty:          return .none
      case let .cons(a, _): return a
    }
  }
  
  func tail() -> List<A> {
    switch self {
      case .empty:             return .empty
      case let .cons(_, next): return next
    }
  }
  
  func last() -> Optional<A> {
    switch self {
      case .empty:               return .none
      case let .cons(a, .empty): return a
      case let .cons(_, l):      return l.last()
    }
  }
  
  func index(_ index: Int) -> Optional<A> {
    func indexTail(i: Int, xs: List) -> List {
      switch i {
        case 0:  return xs
        default: return indexTail(i: i - 1, xs: xs.tail())
      }
    }
    switch index {
      case 0:  return self.head()
      default: return indexTail(i: index, xs: self).head()
    }
  }
  
  
  func length() -> Int {
    switch self {
      case .empty: return 0
      default:     return 1 + self.tail().length()
    }
  }
  
  func insert(_ a: A) -> List {
    List.cons(a: a, list: self)
  }
  
  func append(_ a: A) -> List {
    switch self {
      case .empty:                return .cons(a: a, list: .empty)
      case let .cons(head, list): return list.append(a).insert(head)
    }
  }
  
  func concat(_ list: List) -> List {
    switch self {
      case .empty:               return list
      case let .cons(a, .empty): return .cons(a: a, list: list)
      case let .cons(a, l):      return l.concat(list).insert(a)
    }
  }
  
  func map(_ f: (A) -> A) -> List {
    switch self {
      case .empty:               return .empty
      case let .cons(a, .empty): return .cons(a: f(a), list: .empty)
      case let .cons(a, l):      return .cons(a: f(a), list: l.map(f))
    }
  }
}

extension List: CustomStringConvertible {
  var description: String {
    switch self {
      case .empty:
        return ""
      case let .cons(a, list):
        return "\(a) \(list)"
    }
  }
}

precedencegroup ListPrecedence {
  associativity: left
}
infix operator +: ListPrecedence
func + <A>(a: A, list: List<A>) -> List<A> {
  List<A>.cons(a: a, list: list)
}

infix operator ++: ListPrecedence
func ++ <A>(a: List<A>, b: List<A>) -> List<A> {
  a.concat(b)
}

List<Int>.cons(a: 2, list: .empty)
List<Int>.empty.head()

let threeTwoList = List<Int>.cons(a: 3, list: .cons(a: 2, list: .empty))
let threeTwoWithInfix = 3 + (2 + .empty)
false + (true + .empty)
threeTwoList == threeTwoWithInfix
let totalList = (5 + (4 + threeTwoList))
totalList ++ totalList.append(1)
(3 + (2 + .empty)).head()
totalList.tail()
totalList.last()
totalList.index(2)
totalList.insert(6)
totalList.append(1)
totalList.length()
let mapList = totalList.map { $0 * 2 }
print(mapList)