List.swift

import UIKit
private enum ListNode<Element> {
    case End
    indirect case Node(Element, next: ListNode<Element>)
    
    func cons(x: Element) -> ListNode<Element> {
        // 每次 cons 调用将把 tag 加一
        return .Node(x, next: self)
    }
}

public struct ListIndex<Element> {
    private let node: ListNode<Element>
    private let tag: Int
}

extension ListIndex: ForwardIndexType {
    public func successor() -> ListIndex<Element> {
        switch node {
        case let .Node(_, next: next):
            return ListIndex(node: next, tag: tag.predecessor())
        case .End:
            fatalError("cannot increment endIndex")
        }
    }
}

public func == <T>(lhs: ListIndex<T>, rhs: ListIndex<T>) -> Bool {
    return lhs.tag == rhs.tag
}

public struct List<Element>: CollectionType {
    // Index's type could be inferred, but it helps make the rest of
    // the code clearer:
    public typealias Index = ListIndex<Element>
    
    public var startIndex: Index
    public var endIndex: Index
    
    public subscript(idx: Index) -> Element {
        switch idx.node {
        case .End: fatalError("Subscript out of range")
        case let .Node(x, _): return x
        }
    }
}

extension List: ArrayLiteralConvertible {
    public init(arrayLiteral elements: Element...) {
        startIndex = ListIndex(node: elements.reverse().reduce(.End) {
            $0.cons($1)
            }, tag: elements.count)
        endIndex = ListIndex(node: .End, tag: 0)
    }
}