[swift-evolution] [Manifesto] Completing Generics

[plx]

Thanks for publishing the manifesto; for the most part everything seems reasonable and logical extensions that would “complete" the current system.

I do have a few remarks and I’m going to put them each in a separate email (they don’t relate to each other).

# Comment: Variadic Generics “Need” Structural Union Types

Disclaimer: I’m not 100% sure on the terminology; I’m using “structural union” here to mean an “anonymous enum” (like “A | B | C | D”) wherein both (a) the order matters (e.g. `(A | B | C | D)` and `(D | C | B | A)` are different types) and also (b) types can repeated (e.g. `(Int | Int | Int)` exists and isn’t just `Int`). If that’s not a "structural union” I apologize for the inappropriate terminology.

Content: I think variadic generics will wind up being rather limited in their utility w/out a correspondingly-variadic form of “structural union”; the reason is that for many type-combinators the right representation for some of the resulting associated types is a sum. 

Here’s a motivating example: a read-only collection acts as the concatenation of its `n` input collections. Today this requires a family of types (one per `n` you wish to support) and would superficially seem like a good place to use variadic generics...but it’s not so straightforward:

// non-variadic version:
struct ChainCollection3<A:Collection,B:Collection,C:Collection> : Collection {
  let a = A
  let b = B
  let c = C
}

enum ChainCollection3Index<A:Collection,B:Collection,C:Collection> : ForwardIndex {
  case IndexA(A.Index) // <- can’t be just `A` due to name collision!
  case IndexB(B.Index) //
  case IndexC(C.Index) //
}

// showing the index in use:
extension ChainCollection3 {

  associatedtype Index = ChainCollection3Index<A,B,C>

  var startIndex: Index { return .IndexA(a.startIndex) }
  var endIndex: Index { return .IndexC(c.endIndex) }

  // the below isn’t actually correct b/c it doesn’t
  // properly handle the case when one of the constituent
  // collections is empty…also assuming collections-move-indices:
  func successorFor(index: Index) -> Index {
    switch (index) {
      case let .IndexA(aIndex):
        return aIndex == a.endIndex ? .IndexB(b.startIndex) : .IndexA(a.successorFor(aIndex))
      case let .IndexB(bIndex):
        return bIndex == b.endIndex ? .IndexC(c.startIndex) : .IndexB(b.successorFor(bIndex))
      case let .IndexC(cIndex):
        precondition(cIndex != c.endIndex)
        return .IndexC(c.successorFor(cIndex))       
    }
  }

  // and so on, mostly obvious boilerplate

}

…and although a good variadic generics system could eliminate the need for the family like ChainCollection*, it’s hard to see how you could implement an `Index` type in the variadic setting—without which you are “capped” at the `Sequence` level—w/out also having *variadic* structural unions (I think the best you could *maybe* do is manually implement the equivalent of that enum as e.g. a managed buffer with a type tag and a lot of casting, but you wouldn’t *want* to do that...).

Perhaps I’m missing a trick here, but if I’m not it does seem like the lack of variadic structural unions places a pretty low ceiling on what you could build using variadic generics.