Exploring user-space tuple designs in the quest for variadic generics.

Tuple.swift

// First, let's test out the basic design. This is basically just an 
// HList.

// This recurses to the right because that makes subscripting simpler, 
// at the cost of making appending impossible to generalize.
public protocol TupleProtocol: RandomAccessCollection
    where Index == Int, IndexDistance == Int, Element == Any
{
    associatedtype First
    associatedtype Rest //: TupleProtocol
    
    var first: First { get set }
    var rest: Rest { get set }
    
    // y u no hkt????
    // associatedtype Appending<T>
    // func appending<T>(_ value: T) -> Appending<T>
}

extension TupleProtocol {
    public var startIndex: Int { return 0 }
    
    public func index(_ i: Int, offsetBy offset: Int) -> Int {
        return i + offset
    }
    
    public func index(before i: Int) -> Int {
        return index(i, offsetBy: -1)
    }
    
    public func index(after i: Int) -> Int {
        return index(i, offsetBy: 1)
    }
    
    func prepending<T>(_ value: T) -> _Another<T, Self> {
        return .init(value, self)
    }
}

public struct _Another<First, Rest: TupleProtocol>: TupleProtocol {
    init(_ first: First, _ rest: Rest) {
        self.first = first
        self.rest = rest
    }
    
    public var first: First
    public var rest: Rest
    
    public var endIndex: Int {
        return rest.endIndex + 1
    }

    public subscript (_ i: Int) -> Any {
        if i == 0 {
            return first
        }
        else {
            return rest[i - 1]
        }
    }
    
    // typealias Appending<T> = _Another<First, Rest.Appending<T>>
    // func appending<T>(_ value: T) -> Appending<T> {
    //     return .init(first, rest.appending(value))
    // }
}

extension _Another where Rest == _Zero {
    init(_ first: First) {
        self.init(first, .init())
    }
}

// Allows us to terminate Tuple.Zero properly.
extension Never: TupleProtocol {
    public var first: Never {
        get { fatalError() }
        set { fatalError() }
    }
    
    public var rest: Never {
        get { fatalError() }
        set { fatalError() }
    }
    
    public var endIndex: Int { fatalError() }
    public subscript (_ i: Int) -> Any { fatalError() }
}

public struct _Zero: TupleProtocol {
    init() {}
    
    public var endIndex: Int {
        return 0
    }
    
    public subscript (_ i: Int) -> Any {
        fatalError("Cannot subscript a Tuple.Zero")
    }
    
    public var first: Never {
        get { fatalError("Cannot get the first of a Tuple.Zero") }
        set { fatalError("Cannot set the first of a Tuple.Zero") }
    }
    
    public var rest: Never {
        get { fatalError("Cannot get the rest of a Tuple.Zero") }
        set { fatalError("Cannot set the rest of a Tuple.Zero") }
    }
    
    // typealias Appending<T> = _Another<T, _Zero>
    // func appending<T>(_ value: T) -> Appending<T> {
    //     return .init(first, self)
    // }
}

enum Tuple {
    public typealias Zero = _Zero
    public typealias Another = _Another
    
    // Convenience aliases.
    public typealias One<T> = Another<T, Zero>
    public typealias Two<T, U> = Another<T, One<U>>
    public typealias Three<T, U, V> = Another<T, Two<U, V>>
    public typealias Four<T, U, V, W> = Another<T, Three<U, V, W>>
    public typealias Five<T, U, V, W, X> = Another<T, Four<U, V, W, X>>
    public typealias Six<T, U, V, W, X, Y> = Another<T, Five<U, V, W, X, Y>>
    public typealias Seven<T, U, V, W, X, Y, Z> = Another<T, Six<U, V, W, X, Y, Z>>
}

let zero = Tuple.Zero()
let one = Tuple.One(1)
let two = Tuple.Two(1, .init(2))
let three = Tuple.Three(1, .init(2, .init(3)))

dump(three)

// Okay, that works. So let's talk syntax. Suppose we could overload 
// generic types on type parameter arity (and possibly parameter 
// constraints) just like we can overload functions:
// 
//    struct Tuple<>: RandomAccessCollection {
//        var first: Never
//        var rest: Never
//        
//        ...
//    }
//    struct Tuple<First, RestTypes...>: RandomAccessCollection {
//        var first: First
//        var rest: Tuple<RestTypes>
//        
//        ...
//    }
//    
//    // XXX Do we want some way to define the common interface 
//    // of the two Tuple<...> variants?
// 
// Therefore, all variadic generic types would at root be expressed 
// recursively. We could probably support both left and right recursion 
// if we wanted. We could definitely support additional type parameters 
// other such things.
// 
// We could also potentially define functions in this way:
//
//     func lexicographicComparison(_ a: Tuple<>, _ b: Tuple<>) -> Bool {
//         // Empty tuples are equal
//         return false
//     }
// 
//     func lexicographicComparison<First, Rest...>(_ a: Tuple<First, Rest>, _ b: Tuple<First, Rest>) -> Bool
//         where First: Comparable, Rest: Comparable
//     {
//         if a.first < b.first {
//             return true
//         }
//         else if b.first < a.first {
//             return false
//         }
//         else {
//             return lexicographicComparison(a.rest, b.rest)
//         }
//     }
// 
// Although that might be tricky to actually, you know, compile.
// 
// By the way, it'd also be nice if we had a greatest-common-supertype 
// operator for types, and a subtype-of-all-types `Never`:
// 
//    struct Tuple<>: RandomAccessCollection {
//        ...
//        typealias Element = Never
//    }
//    struct Tuple<First, RestTypes...>: RandomAccessCollection {
//        ...
//        // Note that `|` here is *not* a Ceylon-style union type. It 
//        // forms a protocol composition of all supertypes the two 
//        // types are known to have in common.
//        typealias Element = First | Tuple<Rest>.Element
//        ...
//    }
// 
// But I've never managed to convince anyone of those ideas.