Generic type in a protocol

[awwright (Austin Wright)]

How am I supposed to associate a generic type with a protocol?

Suppose I have a protocol Base which represents some type of specialized matrix or lattice, or something similar. There can be different ways to index the data, which can be implemented as different structs conforming to the protocol. There also needs to be a few associated types that can store additional data, say, List<T: Comparable>. List and other types are closely associated with how the implementation of Base is implemented and how its data is indexed, and exists 1:1 with the underlying Base (for some given Comparable type T, there is only one possible List per implementation of Base).

I need to be able to construct Lists of some type, for example in a generic function:

func foo<T: Base, U: Comparable>(a: T, b: U) -> T.List<U>

In a protocol I can create a generic function, but when I do the same thing with an associated type I get

Associated types must not have a generic parameter list

What am I supposed to do here?

[Danny]

It is not clear from what you've said if this is what you're trying to do or not.

protocol Base<Scalar> {
  associatedtype Scalar: Comparable
  associatedtype List
}

func foo<T: Base>(_: T, _: T.Scalar) -> T.List

[awwright (Austin Wright)]

No, for any given T, there may be any number of different instances of T.List created with any number of types for U.

Implementing code may need to do things like:

func foo<T: Base, U: Comparable>(a: T, b: U) -> T.List<U>
   var a: T.List<Int>
   var b: T.List<String>
   ...
}

[Danny]

What's the state of higher kind types?

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 una…

[awwright (Austin Wright)]

What about it? I'm not sure this is a higher-kinded type. It's just a normal generic type where one of the type parameters is going to be filled in from a different location than the rest of the parameters.

[Danny]

Keep reading.

What's the state of higher kind types?

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],…

[awwright (Austin Wright)]

I've been working on this problem for almost a month now. "Keep reading" is not really the solution I'm looking for at this point.

[Danny]

You sound flustered. But if you don't read at least one informative post, then it will take you infinite time, not just one month, to realize that what you want is impossible, and instead, that overloading is the closest solution available.

E.g.

protocol Base {
  associatedtype List: Collection where List.Element: Comparable
}

func foo<T: Base, U: Comparable>(a: T, b: U) -> [U]
where T.List == [Never] {
  typealias List = Array
  var _: List<Int>
  var _: List<String>
  return [b]
}

struct ArrayBase: Base {
  typealias List = [Never]
}

#expect(foo(a: ArrayBase(), b: 1) == [1])

[Slava_Pestov]

@awwright

No, for any given T, there may be any number of different instances of T.List created with any number of types for U.

Implementing code may need to do things like:

func foo<T: Base, U: Comparable>(a: T, b: U) -> T.List<U>
   var a: T.List<Int>
   var b: T.List<String>
   ...
}

This is not possible. What do the concrete types substituted for T.List look like though? There might be a simpler approach to the same problem.

[awwright (Austin Wright)]

@Slava_Pestov

What do the concrete types substituted for T.List look like though?

This doesn't make sense to me, a T.List<U> is a specialized data type that relates some data structure T like a lattice to a value of some arbitrary type U, it's almost never going to be an alias for an existing data type. In very simple cases you might be able to alias T.List<U> to Dictionary<T, U>.

[awwright (Austin Wright)]

The reason I'm skeptical this implicates higher-kinded type systems is that "List" and other "nested" types could be written as top-level types, except for the need to express that, for some given U, there is a 1:1 relation from an implementation of Base T to an implementation of List<T, U>. I'm not sure why more sophisticated type logic and reasoning would become necessary.

It's already possible to write statements like

struct Foo<T> {
	struct Bar<U> {

	}
}

And further, protocols can require parameterized functions, but for some reason cannot denote parameterized structs? This seems like an arbitrary constraint rather than a limitation of the type system, and the way the error is written led me to believe there's a different but "correct" syntax that does this, perhaps involving some special usage of associatedtype or primary associated types. I find it difficult to believe that people are writing complicated Swift programs without a way to parameterize structs.

[Danny]

Unfortunately, this will require even more reading.

Type declarations in protocols / protocols as namespaces?

I've skimmed a couple of related threads but didn't find the answer to this question, apologies if this has been answered before. Say I have some protocol Proto and some conforming types, and I want to group these types, and the name Proto happens to be the best name for both the protocol and the namespace. I might try the following, which will not compile: protocol Proto { // ... requirements ... } extension Proto { struct Foo: Proto { // ERROR: Types can't be nested in protocols //…

[awwright (Austin Wright)]

Sorry, this thread is just restating what I already know.

[Slava_Pestov]

@awwright

The reason I'm skeptical this implicates higher-kinded type systems is that "List" and other "nested" types could be written as top-level types, except for the need to express that, for some given U, there is a 1:1 relation from an implementation of Base T to an implementation of List<T, U>. I'm not sure why more sophisticated type logic and reasoning would become necessary.

You just answered your own question essentially. Today, G<U> always refers to some concrete G. If the left-hand side of the < becomes parameterized, it really does require more sophisticated type logic and reasoning.

It took the Rust folks several years to design and implement generic associated types: Generic associated types to be stable in Rust 1.65 | Rust Blog

@awwright

It's already possible to write statements like

struct Foo<T> {
	struct Bar<U> {

	}
}

That's just the same thing as this though:

struct Foo<T> {}
struct FooBar<T, U> {}

[awwright (Austin Wright)]

@Slava_Pestov

That's just the same thing as this though:

It is, with the condition that for some U there is a unique FooBar<T, U> associated with Foo<T> instead of zero or more arbitrary ones.

[Slava_Pestov]

@awwright

It is, with the condition that for some U there is a unique FooBar<T, U> associated with Foo<T> instead of zero or more arbitrary ones.

That’s one way to think about it, but the point is that in the generics implementation, nested scopes are flattened and erased. The fact that Bar is nested within Foo does not play a role after name lookup.

[awwright (Austin Wright)]

@Slava_Pestov

The fact that Bar is nested within Foo does not play a role after name lookup.

Correct, the 1:1 association only exists until compile time, but in order for this to compile at all, the functions need to know that FooBar<T, U> is the list associated with Foo<T> that other functions will be using, as opposed to some other struct like FooBaz<T, U>.

This role of associating two types together is normally performed by associatedtype, but that seems to be arbritarially restricted here.

[Joe_Groff]

@awwright

func foo<T: Base, U: Comparable>(a: T, b: U) -> T.List<U>
   var a: T.List<Int>
   var b: T.List<String>
   ...
}

I realize that this is only a simplification of your actual use case, but if it so happens that you only need to instantiate the associated type at a fixed set of types like Int and String, a blunt way to work around the limitation could be to have multiple associated types, so you have:

func foo<T: Base>(a: T, b: Int) -> T.ListOfInt {
  var a: T.ListOfInt
}

func foo<T: Base>(a: T, b: String) -> T.ListOfString {
  var b: T.ListOfString
}
...

You might also try seeing if U can be hoisted into a separate associated type of the conformance. Would it be possible to express this as something like func foo<T: Base>(a: T, b: T.U) -> T.ListOfU, and then have the type T which conforms to Base be generic over U?

extension MyBase<Element>: Base {
  typealias U = Element
  typealias ListOfU = Array<Element>
}

[awwright (Austin Wright)]

For now I can get away with only needing two types, but that still means maintaining two copies of the same code just because generics don't work in this situation...
I think the solution that'll end up working is a combination of your solution with AnyHashable, since these types are always Hashable, and a wrapper around it to cast the AnyHashable value to the desired type.