FingerTree.swift

indirect enum FingerTree<T> {
    case Empty,
         Single(_ value: T),
         Deep(
           left: Digit<T>,
           child: FingerTree<Node<T>>,
           right: Digit<T>
         )
}

enum Digit<T> {
    case One(_ _0: T),
         Two(_ _0: T, _ _1: T),
         Three(_ _0: T, _ _1: T, _ _2: T),
         Four(_ _0: T, _ _1: T, _ _2: T, _ _3: T)
}

enum Node<T> {
    case Node2(_ _0: T, _ _1: T),
         Node3(_ _0: T, _ _1: T, _ _2: T)
}

func addToRight<T>(tree: FingerTree<T>, value: T) -> FingerTree<T> {
    switch (tree) {
    case .Empty:
        return .Single(value)
    case .Single(let v0):
        return .Deep(left: .One(v0), child: .Empty, right: .One(value))
    case let .Deep(left: left, child: child, right: right):
        switch (right) {
        case let .One(v0):
            return .Deep(
              left: left,
              child: child,
              right: .Two(v0, value)
            )
        case let .Two(v0, v1):
            return .Deep(
              left: left,
              child: child,
              right: .Three(v0, v1, value)
            )
        case let .Three(v0, v1, v2):
            return .Deep(
              left: left,
              child: child,
              right: .Four(v0, v1, v2, value)
            )
        case let .Four(v0, v1, v2, v3):
            return .Deep(
              left: left,
              child: addToRight(tree: child, value: .Node3(v0, v1, v2)),
              right: .Two(v3, value)
            )
        }
    }
}