What's the state of higher kind types?

Evolution Discussion
1

Hey there,

Given that protocols can by now be generic, I wanted to know if there are any plans to enable something like this in the near future:

protocol Arrow<S, T> {
   func compose<U>(_ next: Self<T, U>) -> Self<S, U>
}

Letting us write Self<...> would be extremely helpful for a bunch of functional programming patterns and to me (who doesn't know much about how the compiler works), it seems like we're 90% there? Any posts I've seen that want something similar seem to be older than generic protocols, so I hope you don't mind that I ask :)

1 Like
2

Unless I really missed something, that is not the case (and just an example for the confusion predicted in the discussion about primary associated types :disappointed:).

5 Likes
3

That's of course an important nuance. Not sure if this is a blocker for Self<...> and if so, how.

4

I've always thought of it this way: In protocols with associated types, all references of type Self actually resolve to (in this case) the type Arrow<S, T>. The syntax you show would have Self resolve to unadorned Arrow which is not a type, but a type constructor. Adding <T, U> to Arrow is precisely using Arrow as a type constructor to construct a new type.

There's just no syntax combination which allows surface level language users to directly access Arrow as a type. Such a type would be a higher kind of type (pun intended).

Dunno if that explanation helps anyone else, but its what I finally settled on for myself.

3 Likes
6

I don't think Self is relevant to this topic. The generic type parameters of a protocol do not have to match up with those of adopting types, so re-specializing is impossible at the protocol level. Switcheroos of placeholder types, I think, always need to be copy-pasted to the type level.

While the following is not as constrained as re-specialized Selfs, it might be useful, but the second some here can't be expressed:

protocol Arrow<S, T> {
  associatedtype S
  associatedtype T

  func compose<U>(_ next: some Arrow<T, U>) -> some Arrow<S, U> // 'some' type cannot be the return type of a protocol requirement; did you mean to add an associated type?
}

I.e. You can write this…

struct 💘<S, T, 💔>: Arrow {
  func compose<U>(_ next: some Arrow<T, U>) -> some Arrow<S, U> {
    💘<_, _, Never>()
  }
}

…but if you want it to be a protocol requirement, you need to switch to any Arrow<S, U> in both places.

2 Likes
7

The way I envisioned it, the function wasn’t generic over arrows. Composing arrows with arbitrary arrows of appropriate generic type is pretty meaningless.

struct ArrayArrow<S, T> : Arrow<S, T> {
let closure: (S) -> [T]
func compose<U>(_ next: ArrayArrow<T, U>) -> ArrayArrow<S, U> {
   .init {closure($0).flatMap (next.closure)}
}
}

I would want this to be a conformance. I would not want it to be composable with an OptionArrow of analogous design.

1 Like
8

Precisely. The challenge I've issued to students before is: write a protocol Mappable which covers map on both Array and Optional. The protocol must be written in a way that does not allow Array's implementation to return Optional or Optional's implementation to return Array.

When folks really grok why they can't do that, they see what higher-kinded types are all about. And they eventually see why Sequence's implementation returns Array and why Combine's implementation returns a specific MapPublisher.

4 Likes
9

I think the feature you're looking for is generic associated types. Rust has this: 1598-generic_associated_types - The Rust RFC Book

Swift allowing this some day is not outside the realm of possibility, but it's not completely trivial (the Rust folks spent several years designing and implementing this, AFAIK).

It would require an overhaul of how the requirement machine builds a rewrite system from requirements, which currently makes a pretty fundamental assumption that associated types are unary type constructors (T.Element is kind of like Element<T>; a generic associated type T.MapResult<E> has two arguments, T and E).

We would also need to think about how the runtime type metadata side of this works, too.

One day I will finish (start) documenting how the requirement machine works, and maybe then more folks can get involved in discussing future directions for generics.

16 Likes
10

How would this interact with the ability to have non-generic implementations? Like if we allowed this:

extension Sequence {
  func specialMap<T>(_ transform: (Element) -> T) -> Self<T>
}

What would "".specialMap { _ in 1 } even mean? You can’t have a String<Int> — String.Element is fixed as Character.

11

That's a good question. I think the right way to think about this is that specialMap() returns a generic associated type, not a hypothetical re-parameterized Self:

protocol Mappable {
  associatedtype Element
  associatedtype MapResult<Result>

  func map<Result>(_ fn: (Element) -> Result) -> MapResult<Result>
}

String would just have to conform with MapResult being Array, to allow map() in full generality:

extension String: Mappable {
  typealias Element = Character
  typealias MapResult<Result> = Array<Result>
}

However this raises the question of what MapResult could possibly be, other than Array. Clearly Optional could witness MapResult<Result> with Optional<Result>, and perhaps in a LinkedList type, it could be LinkedList<Result>. However even with Set, you'd be prevented from setting typealias MapResult<Result> = Set<Result>, because Result isn't required to be Hashable here.

6 Likes
12

I would be fascinated to read such documentation. I don’t know if perhaps this would be too casual or simply not your style, but I’m sure it would reduce the friction enormously of creating at least some documentation if you simply did a screen recording of your IDE where you just start talking about how it works in whatever way first comes to your mind (with surely a small amount of initial thought about where to start), jumping into definitions and then back again while you point out any and all relevant information that you think of. No pressure, just wanted to give the idea…

1 Like
13

Parameterized associate types are how ML languages model higher kinded types0, but they're free functions (or functions in a module). I think the equivalent would be making a separate mapper type:

protocol Mappable {
  associatedtype Container<A>
  static func map<Element, Result>(
    _ base: Container<Element>, 
    transform: (Element) -> Result
  ) -> Container<Result>
}

struct ArrayMapper: Mappable {
  typealias Container<A> = [A]
  static func map<Element, Result>(
    _ base: [Element],  
    _ transform: (Element) -> Result
  ) -> [Result]
}

We could then extend array so we still have method syntax:

extension Array {
  func map<Result>(_ transform: (Element) -> Result) -> [Result] {
    ArrayMapper.map(self, transform)
  }
}

I'm not sure how you'd define the protocol so that Container is Self or if it's possible.

1 Like
14

That's an excellent link @Slava_Pestov. I especially liked the part about how we teach these concepts, as that has been a particular problem for me. I find that most of my students have problems with the idea of a type constructor (associated or not) and I wonder if referring to them instead as generic_associated_types actually fixes that problem.