Skip to content

Instantly share code, notes, and snippets.

@beccadax
Last active June 29, 2021 12:51
Show Gist options
  • Save beccadax/03bfe923fced45fa31c0a2b3ba650328 to your computer and use it in GitHub Desktop.
Save beccadax/03bfe923fced45fa31c0a2b3ba650328 to your computer and use it in GitHub Desktop.
Exploring user-space tuple designs in the quest for variadic generics.
// 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.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment