[Feature Request] Implement `CollectionElement` trait to conform to `EqualityComparable` trait

[arvindavoudi]

Review Mojo's priorities

• [x] I have read the roadmap and priorities and I believe this request falls within the priorities.

What is your request?

For the proposed List.index method to be operational, it is essential to first implement the CollectionElement trait to conform to the EqualityComparable trait. This prerequisite ensures that the types used within the List struct are comparable (equal/not equal), thereby allowing the index method to accurately find index of the given value by comparing it to all those present values in the list.

Moreover, in the future, the possibility of defining 'default method implementations within a trait' can simplify custom structs’ ability to be used in a list by removing the explicit necessity for implementing both __eq__ and __ne__ methods in those structs. This is aimed at achieving a level of simplicity and ability in lists similar to what we can currently find in Python.

What is your motivation for this change?

This is an essential step forward for having more stable and Pythonic collection datatypes available in Mojo while narrowing down the differences between these two languages.

Any other details?

No response

[gabrieldemarmiesse]

Maybe this is a duplicate issue? I think what you want is this: https://github.com/modularml/mojo/issues/1876#issuecomment-1976762492 , at least it would fix the issue you are mentioning and would allow List to have an index method.

[arvindavoudi]

I think these two requests are in one direction as you also mentioned but even before having conditional traits in Mojo, we can simply implement the CollectionElement trait to conform to the EqualityComparable. This enables us to have an index much earlier than having the feature requested you mentioned. I think it's applicable at the moment unless I'm missing something...?!

[gabrieldemarmiesse]

I believe the issue is that if we get close to what python does as you describe, Mojo should generate __eq__ as being the same as the is operator. https://docs.python.org/3.12/reference/datamodel.html#object.__eq__

By default, object implements eq() by using is, returning NotImplemented in the case of a false comparison: True if x is y else NotImplemented.

Which would be very strange in Mojo since value semantics imply you can't really compare two structs by looking at their memory adress, they might be on the stack, thus moved around.

[JoeLoser]

Thanks for bringing this up. Right now, before we can do this, we would need to rework the EqualityComparable trait a bit. Right now, it mandates eq and ne dunder methods return a Bool. However, if we push CollectionElement to conform to EqualityComparable trait, this would break for SIMD. Currently, SIMD is a CollectionElement trait but its eq and ne methods return SIMD[DType.bool, size] and not Bool. One thought is to beefen up the EqualityComparable trait to return a Boolable instead of just a Bool given the existing definitions for SIMD.

I asked internally if we even have a way to express that for EqualityComparable right now since that would mean having eq and ne return a Boolable (a trait) rather than a concrete type (a Bool).

[arvindavoudi]

Thanks for your concern @JoeLoser.

I think we can take 2 general approaches to make this work.

1- Make the return types from Bool to Boolable as you completely described.

2- Just as an idea, making the return types in traits over-loadable. In this case, we can have two exact definitions for a single method with different return types. I think this idea can leverage the language abilities but not quite sure if it's a good design or not as I haven't seen it anywhere before. I've been thinking about it for a few weeks as something potentially new and especially unique to Mojo (although it may exist in some other languages, idk).

Also before one of those above-mentioned approaches gets implemented, we can create another trait named SIMDCollectionElement or SIMDElement with different return type from the existing one to work this around. Therefore we can have methods like index and count much earlier, then when at least one of these is applicable, we walk into a more appropriate trait's backend solution as an enhancement for language's integrity.

Worth noting that I’m not sure if adopting to new SIMDCollectionElement will break anything or not.