Enums

A red-black binary search tree. Adapted from Airspeed Velocity’s implementation, Chris Okasaki’s Purely Functional Data Structures, and Stefan Kahrs’ Red-black trees with types, which is implemented in the Haskell standard library.

Elements must be comparable with Strict total order.

Full documentation is available here.

A singly-linked, lazy list. Head-tail decomposition can be accomplished with a switch statement:

extension List {
  public func map<T>(f: Element -> T) -> List<T> {
    switch self {
    case .Nil: return .Nil
    case let .Cons(x, xs): return f(x) |> xs().map(f)
    }
  }
}

Where |> is the cons operator.

Operations on the beginning of the list are O(1), whereas other operations are O(n).

Discussion of this specific implementation is available here.

Full documentation is available here.