indirect enum List as CollectionType

list.swift

// A simple linked list using enums:
enum List<Element> {
    case End
    indirect case Node(Element, List<Element>)
    
    func cons(x: Element) -> List<Element> {
        return .Node(x, self)
    }
}

extension List: ArrayLiteralConvertible {
    init(arrayLiteral elements: Element...) {
        self = elements.reverse().reduce(.End) {
            $0.cons($1)
        }
    }
}


// conforming to SequenceType is easy
extension List: SequenceType {
    func generate() -> AnyGenerator<Element> {
        var current: List<Element> = self
        return anyGenerator {
            switch current {
            case .End: return nil
            case let .Node(x, next):
                current = next
                return x
            }
        }
    }
}

// which gives plenty of useful extensions
let l: List = ["1","2","3"]
",".join(l)
l.contains("2")
l.flatMap { Int($0) }


// but not all, e.g. first, dropFirst

// so how can we make it a collection type?

// nodes ought to be useable as indices...
// successor is just the next node
extension List: ForwardIndexType {
    func successor() -> List<Element> {
        switch self {
        case let .Node(_, next):
            return next
        case .End:
            fatalError("cannot increment endIndex")
        }
    }
}

// here's the problem, ForwardIndex must be Equatable,
// so how to do this:
func ==<T>(lhs: List<T>, rhs: List<T>) -> Bool {
    switch (lhs,rhs) {
    case (.End,.End): return true
    case (.End,.Node): return false
    case (.Node,.End): return false
    case (.Node,.Node):
        // in the absence of indirect case identity, 
        // do something that probably deserves a ಠ_ಠ
        return unsafeBitCast(lhs, UInt.self) == unsafeBitCast(rhs, UInt.self)
    }
}


// this works _and_ is compatible with the value type aspects of enums,
// because you can't update enums in-place, 

// so copying means the reference is the same:
let a = l
a == l  // true (in the same sense a copied Array shortcuts == using the identity of its buffer)

// but changing the value changes the identity
var b = l
var c = l
a == b && b == c && c == a  // true
b = l.cons("3")
c = ["1","2"]
a == b || b == c || c == a  // false

// now, it's trivial to make List indexable, and thus a collection
extension List: CollectionType {
    var startIndex: List<Element> { return self }
    var endIndex: List<Element> { return .End }
    subscript(idx: List<Element>)->Element {
        switch idx {
        case .End: fatalError("Subscript out of range")
        case let .Node(x,_): return x
        }
    }
}

// and now you can use them as indices
l.first
",".join(dropFirst(l))

// list append
func +<T>(lhs: List<T>, rhs: List<T>) -> List<T> {
    switch lhs {
    case .End:
        return rhs
    case let .Node(x, xs):
        return (xs + rhs).cons(x)
    }
}

let ll = l + l // copies left-hand l
let lll = l + l
ll == lll // false, they are different lists even if they contain the same values

// I guess it's debatable whether the following is "correct" behaviour
advance(ll, 3) == l   // true
advance(lll, 3) == l  // true

// are there any cases where this collection can be used to get definitely incorrect behaviour?

Alternatively you could implement == like this:

func ==<T>(lhs: List<T>, rhs: List<T>) -> Bool {
    switch (lhs,rhs) {
    case (.End,.End): return true
    default:
        return false
    }
}

Which works for traversal but breaks the rules for Equatable:

l.startIndex == l.startIndex  // false

Wouldn't setting an Equatable constraint for Element be better?
then we'll have

func ==<T>(lhs: List<T>, rhs: List<T>) -> Bool {
    switch (lhs,rhs) {
    case (.End,.End): return true
    case (.End,.Node): return false
    case (.Node,.End): return false
    case let (.Node(x),.Node(y)):
        return x == y
    }
}