How could a language implement generic traits?

Question

Take C#'s IEnumerable<T> interface. It has a singular requirement:

public interface IEnumerable<out T>
{
  IEnumerator<T> GetEnumerator();
}

IEnumerator<T> simply provides a way to traverse a sequence -- the kind of thing needed for a foreach loop. The implementation of that is unimportant here.

Now let's consider the same thing in a trait-based language. Immediately you have a problem: you can't just return an enumerator, as that's not a type. You can't use an impl Enumerator<T> either, as there's no method body to determine the concrete type from. In this case you might be able to get away with a dyn Enumerator<T>, but that's less than ideal and won't work for every scenario.

One solution, taken by Swift for many years, is to not allow traits ("protocols" in Swift) to use generic type syntax at all, instead opting for inferred associated types. It simply had

public protocol Sequence {
  associatedtype Element
  associatedtype Iterator: IteratorProtocol
    where Iterator.Element == Element

  func makeIterator() -> Iterator
}

This becomes difficult to graft generic support onto. If you naïvely call all associated types generic type args, suddenly Array<Int> and Set<Int> aren't a common type -- one is Sequence<Int, IndexingIterator<Array<Int>>> and the other is Sequence<Int, Set<Int>.Iterator>.

On the other hand, not supporting generics at all becomes difficult, because now your struct can't hold a dyn Enumerable<Int>. This leads to a proliferation of either unwanted generics or single-purpose box types like Swift's AnySequence<Element>.

How could a language support generic traits without making them cumbersome to use?

Answer 1

Primary associated types

Swift added this in version 5.7, and it was a huge boon to the usability of protocols. With this syntax, you can pick and choose which associated types can act like generics:

public protocol Sequence<Element> {
  associatedtype Element
  associatedtype Iterator: IteratorProtocol
    where Iterator.Element == Element

  func makeIterator() -> Iterator
}

// Swift 'some' and 'any' are equivalent to Rust 'impl' and 'dyn' respectively
let someIntegers: some Sequence<Int> = Array<Int>([1, 2, 3])
let iter1 = someIntegers.makeIterator() // inferred type: some IteratorProtocol<Int>
let whoKnowsWhat: any Sequence<Int> = Set<Int>([1, 2, 3])
let iter2 = whoKnowsWhat.makeIterator() as any IteratorProtocol // generic lost

One advantage this has is the fact that adding primary associated types to an existing protocol is non-breaking -- you can still have some Sequence and any Sequence without generic types.

This comes with a disadvantage that you have no idea what certain associated types are, and no way to specify. Also, as illustrated in the example above, sometimes these generics are lost (in this case, the where clause means it could be kept, but in the general case that's not always possible).