list.swift

class Wrapper<T> {
    let _val: T[]
    
    init(_ v: T) {
        _val = [v]
    }
    
    func __conversion() -> T {
        return _val[0]
    }
}

enum ListImpl<T> {
    case None
    case Some(Wrapper<T>, List<T>)
}

class List<T> {

    let _impl : ListImpl<T>
    
    init() {
        _impl = .None
    }
    
    init(_ h: T, _ t: List<T>)
    {
        _impl = .Some(Wrapper(h), t)
    }
    
    convenience init(_ h: T) {
        self.init(h, List<T>())
    }
    
    class func from(elements: T[]) -> List<T> {
        var ret = List<T>()
        for var i = elements.count - 1; i >= 0; --i {
            ret = elements[i] + ret
        }
        return ret
    }
    
    var empty : Bool {
        switch _impl {
            case .None: return true
            case .Some: return false
        }
    }

    var head : T? {
        switch _impl {
            case .None: return nil
            case let .Some(h, _): return h
        }
    }

    var tail : List<T>? {
        switch _impl {
            case .None: return nil
            case let .Some(_, t): return t
        }
    }

    @lazy var _last : Wrapper<T?> = {
        if let last = self.tail?.last {
            return Wrapper(last)
        }
        return Wrapper(self.head)
    }()

    var last : T? { return _last }
    
    @lazy var _count : Int = {
        return self.fold(0) { $0.0 + 1 }
    }()

    var count : Int { return _count }

    func fold<U>(a: U, op: (U, T) -> U) -> U {
        switch _impl {
            case .None: return a
            case let .Some(h, t):
                let ret = op(a, h)
                if let tail = self.tail {
                    return tail.fold(ret, op)
                }
                return ret
        }
    }

    func foldr<U>(a: U, op: (T, U) -> U) -> U {
        switch _impl {
            case .None: return a
            case let .Some(h, tail): return op(h, tail.foldr(a, op))
        }
    }
    
    func map<U>(op: T -> U) -> List<U> {
        return fold(List<U>()) { op($1) + $0 }
    }

    func filter(op: T -> Bool) -> List<T> {
        return fold(List<T>()) { op($1) ? $1 + $0 : $0 }
    }

    subscript(idx: Int) -> T {
        return idx == 0 ? head! : tail![idx - 1]
    }
}

@infix func + <T> (h: T, t: List<T>) -> List<T> {
    return List<T>(h, t)
}

@infix func + <T> (h: List<T>, t: T) -> List<T> {
    return h.foldr(List<T>(t), +)
}

@infix func + <T> (h: List<T>, t: List<T>) -> List<T> {
    return h.foldr(t, +)
}

extension List : Sequence {
    func generate() -> GeneratorOf<T> {
        var current : List? = self;
        return GeneratorOf() {
            let ret = current?.head
            current = current?.tail
            return ret
        }
    }
}

extension List : Printable {
    var description: String {
        return "[" + join(", ", map { "\($0)" }) + "]"
    }
}

extension List : ArrayLiteralConvertible {
    class func convertFromArrayLiteral(elements: T...) -> List {
        return from(elements)
    }
}