Recursive Trait Conformance Issue for Nested Collections // Parametric Traits

[jjvraw]

Since certain collection types, such as List[T] are defined with a generic type parameter T that must conform to CollectionElement, nested structures such as List[List[T]] are allowed. However, for example, the List type does not conform to other CollectionElement-based traits such as

• ComparableCollectionElement
• EqualityComparableCollectionElement
• RepresentableCollectionElement
• StringableCollectionElement.

This leads to limitations which are generally intuitive to a programmer, such as the following operations being disallowed:

var a = List(1) in List(List(1))
var b = List(List(1)) == List(List(1))
var c = List(List(1)).__repr__()
var d = List(List(1)).__str__()

(respective to the mentioned traits)

For instance, if we consider the __contains__ method of List:

fn __contains__[
        U: EqualityComparableCollectionElement, //
    ](self: List[U], value: U) -> Bool:

this limits the List API for nested instances. It creates a quasi recursive dependency on EqualityComparableCollectionElement where the most inner list's elements' type needs to conform to a trait that the list itself doesn't satisfy.

I believe this is somewhat of an expression problem under the current trait system, and would really enjoy to hear potential design choices to resolve this while maintaining performance.

For instance, if we involve parametric traits, similar to Higher-Kinded Types as in languages like Haskell, perhaps something like this could be a solution:

trait ParametricEqualityComparable[F[_]]:
    fn __eq__[T: EqualityComparable](self: F[T], other: F[T]) -> Bool:
        ...

impl ParametricEqualityComparable[List]:
    fn __eq__[T: EqualityComparable](self: List[T], other: List[T]) -> Bool:
        if len(self) != len(other):
            return False
        for i in range(len(self)):
            if self[i] != other[i]:
                return False
        return True

This approach would allow for recursive comparison of nested structures. __contains__ could be simplified to:

impl ParametricContainable[List]:
    fn __contains__[T: EqualityComparable](self: List[T], value: T) -> Bool:
        for item in self:
            if item == value:
                return True
        return False

For simple elements, it would use their == operator directly. For nested lists, it would trigger the recursive __eq__ we defined earlier.

Perhaps there's a simpler solution?

[soraros]

List[List[T]] won't work because of #3215 (comment). It's expected that something like Eq a => Eq (List a) will work in the future.

[jjvraw]

What do you mean by List[List[T]] won't work?

In that particular example you referenced, S[T] does not strictly conform to RepresentableCollectionElement due to the difference in signatures of __repr__, correct?

This is the same reason that List(1) in List(List(1)) will not work, as the __eq__ method defined in EqualityComparable, inherited by EqualityComparableCollectionElement, has a different method signature than that of what List has, thus not strictly conforming to the trait.

Hence, we get this somewhat recursive dependency on the inner most type.

[soraros]

I was merely describing the current state, not some fundamental limitation: the support of conditional conformance is incomplete. When the feature is more built out, we can expect e.g. the list example to work without introducing higher-kinded types. They work just fine in Swift and Rust, and suppose we have the impl statement like you used in your examples, we can use Rust's solution directly.

[helehex]

Once we have associated traits we might be able to cook something up in regards to this.