indirect enum List<T>: CustomStringConvertible {
    case empty
    case cons(T, List<T>)
    
    init(_ values: T...) {
        self = List(values)
    }
    
    init<U: Sequence>(_ values: U) where U.Element == T {
        self = values.reversed().reduce(.empty) { $0.prepend($1) }
    }
    
    func prepend(_ element: T) -> List<T> {
        switch self {
        case .empty: return .cons(element, .empty)
        case let .cons(head, tail): return .cons(element, tail.prepend(head))
        }
    }
    
    func append(_ element: T) -> List<T> {
        switch self {
        case .empty: return self.prepend(element)
        case let .cons(head, tail): return .cons(head, tail.append(element))
        }
    }
    
    func prepend(_ elements: List<T>) -> List<T> {
        return elements.reduce(self) { $0.prepend($1) }
    }
    
    func append(_ elements: List<T>) -> List<T> {
        return elements.reduce(self) { $0.append($1) }
    }
    
    var isEmpty: Bool {
        guard case .empty = self else {
            return false
        }
        return true
    }
    
    var head: T? {
        guard case let .cons(head, _) = self else {
            return nil
        }
        return head
    }
    
    var tail: List<T> {
        guard case let .cons(_, tail) = self else {
            return .empty
        }
        return tail
    }
    
    var count: Int {
        switch self {
        case .empty: return 0
        case let .cons(_, tail): return 1 + tail.count
        }
    }
    
    subscript(index: Int) -> T {
        assert(index >= 0)
        switch self {
        case .empty: fatalError("index out of bounds")
        case let .cons(head, tail):
            if index == 0 {
                return head
            } else {
                return tail[index - 1]
            }
        }
    }
    
    func map<U>(_ f: (T) throws -> U) rethrows -> List<U> {
        switch self {
        case .empty: return .empty
        case let .cons(head, tail): return .cons(try f(head), try tail.map(f))
        }
    }
    
    func flatMap<U>(_ f: (T) throws -> List<U>) rethrows -> List<U> {
        switch self {
        case .empty: return .empty
        case let .cons(head, tail):
            return try f(head).append(tail.flatMap(f))
        }
    }
    
    func filterMap<U>(_ f: @escaping (T) throws -> U?) rethrows -> List<U> {
        switch self {
        case .empty: return .empty
        default: return try reduce(List<U>.empty) { s, c in
                guard let n = try f(c) else {
                    return s
                }
                return s.prepend(n)
            }.reversed()
        }
    }
    
    func reduce<U>(_ initial: U, f: (U, T) throws -> U) rethrows -> U {
        switch self {
        case .empty: return initial
        case let .cons(head, tail): return try tail.reduce(f(initial, head), f: f)
        }
    }
    
    func foldRight<U>(_ initial: U, f: (T, U) -> U) -> U {
        switch self {
        case .empty: return initial
        case let .cons(head, tail): return f(head, tail.foldRight(initial, f: f))
        }
    }
    
    func reversed() -> List<T> {
        return reduce(List.empty, f:{ $0.prepend($1)})
    }
    
    func toArray() -> [T] {
        return reduce([T]()) { s, c in
            return s + [c]
        }
    }
    
    var description: String {
        return "List(" + map({String(describing: $0)}).joined(", ") + ")"
    }
    
}

extension List where T == String {
    func joined(_ separator: String) -> String {
        switch self {
        case .empty: return ""
        case let .cons(head, tail):
            if tail.isEmpty {
                return head
            } else {
                return head + separator + tail.joined(separator)
            }
        }
    }
}

extension List where T: Equatable {
    
    func equal(rhs: List<T>) -> Bool {
        switch (self, rhs) {
        case (.empty, .empty): return true
        case (.empty, .cons(_, _)), (.cons(_, _), .empty): return false
        case let (.cons(head1, tail1), .cons(head2, tail2)):
            return (head1 == head2) && tail1.equal(rhs: tail2)
        }
    }
    
    static func ==(lhs: List<T>, rhs: List<T>) -> Bool {
        return lhs.equal(rhs: rhs)
    }
    
}

infix operator >>=
func >>=<T, U>(lhs: List<T>, rhs: (T) -> List<U>) -> List<U> {
    return lhs.flatMap(rhs)
}