import Foundation

enum List<Element> {
    case end
    indirect case node(Element, next: List<Element>)
}

extension List {
    func cons(_ x: Element) -> List {
        return .node(x, next: self)
    }
}

extension List: ExpressibleByArrayLiteral {
    init(arrayLiteral elements: Element...) {
        self = elements.reversed().reduce(.end) { (partialList, element) in
            return partialList.cons(element)
        }
    }
}

extension List {
    mutating func push(_ x: Element) {
        self = self.cons(x)
    }

    mutating func pop() -> Element? {
        switch self {
        case .end:
            return nil
        case .node(let x, next: let next):
            self = next
            return x
        }
    }
}

extension List: IteratorProtocol, Sequence {
    mutating func next() -> Element? {
        return pop()
    }
}

extension List: CustomStringConvertible where Element: CustomStringConvertible {
    var description: String {
        return "[" + self.map { String(describing: $0) }.joined(separator: " -> ") + "]"
    }
}

let empty = List<String>.end
let list = List.node(1, next: .end)
let secondList = List.end.cons(1).cons(2).cons(3)
var thirdList: List = [0, 1, 2, 3]
thirdList.push(10)
thirdList.pop()


var stringsList: List = ["a", "b", "c"]
stringsList.push("abc")