[List] Demonstration of a recursive data type in Swift #algorithm #demo

List.swift

precedencegroup ListOperationPrecedence {
    associativity: right
    higherThan: MultiplicationPrecedence
}

infix operator ++: ListOperationPrecedence
infix operator |*: ListOperationPrecedence

indirect enum List<T> {
    case `nil`
    case cons(T, List)
}

extension List {
    var hd: T? {
        switch self {
        case .nil: return nil
        case .cons(let hd, _): return hd
        }
    }

    var tl: List<T>? {
        switch self {
        case .nil: return nil
        case .cons(_, let tl): return tl
        }
    }

    func cons(_ hd: T) -> List {
        .cons(hd, self)
    }

    func map<U>(_ transform: (T) throws -> U) rethrows -> List<U> {
        switch self {
        case .nil: return .nil
        case let .cons(hd, tl): return try transform(hd) |* tl.map(transform)
        }
    }

    static func |* (hd: T, tl: List) -> List {
        .cons(hd, tl)
    }

    static func ++ (lhs: List, rhs: List) -> List {
        switch lhs {
        case .nil: return rhs
        case let .cons(hd, tl): return hd |* tl ++ rhs
        }
    }

    init(_ array: [T]) {
        self = array.reversed().reduce(.nil) { $1 |* $0 }
    }
}

extension List: ExpressibleByNilLiteral {
    init(nilLiteral: ()) {
        self = .nil
    }
}

extension List: ExpressibleByArrayLiteral {
    init(arrayLiteral elements: T...) {
        self = .init(elements)
    }
}

extension List: CustomStringConvertible {
    var description: String {
        switch self {
        case .nil: return "nil"
        case let .cons(hd, tl): return "\(hd) :: \(tl)"
        }
    }
}

let a = [3].map { $0 * 2 }
print((1 |* 2 |* nil) ++ (5 |* 6 |* nil))
print([4, 3] as List)

let myList: List = [1, 2, 3]
print(myList ++ [4, 5, 6])