Inheritance vs composition: How would you implement an "unordered list"? Subclass of list, or composition?

Question

This came up at work and left me thinking about the best way to model this:

In Python, we have the built-in list container, which is a mutable sequence. Equality between two lists is defined as equality of all items in the list, in their respective positions.

Now a colleague felt the need to define a type that's a list for all practical purposes, except that two lists should be considered equal if they contain the same elements, in the same quantities, but in arbitrary order. Basically,

unordered_list_1 = UnorderedList([1,2,3])
unordered_list_2 = UnorderedList([3,2,1])
unordered_list_1 == unordered_list_2 # True!

The colleague solved this by inheriting from list and overriding the __eq__ special method:

class UnorderedList(list):
 def __eq__(self, other):
 if isinstance(other, UnorderedList):
 return ordered(self) == ordered(other)
 else:
 return NotImplemented

In this form it runs into a gotcha, because the builtin python types such as list take some shortcuts with their special methods; the not-equal __ne__ special method does not just fall back onto the __eq__ special method, so you get the funny scenario where two of these unordered lists can both be equal and not equal.

I suggested inheriting from UserList instead, which is meant to be subclassed, or maybe from one of the collections.abc abstract base classes. Another colleague chimed in with the familiar "Favor composition over inheritance" advice.

I feel that composition in this case would lead to a lot of boilerplate delegation code:

class UnorderedListUsingDelegation:
 def __init__(self):
 self._list = list()
 def __eq__(self, other):
 if isinstance(other, UnorderedListUsingDelegation):
 return ordered(self._list) == ordered(self.other._list)
 else:
 return NotImplemented
 def append(self, item):
 self._list.append(item)
 # Basically def every method implemented by class list and write delegation code for it:
 # pop, push, extend, __getitem__, __setitem__ and so on

So from that consideration, I feel like inheritance is exactly right here: A teeny tiny specialization of behavior.

But on the other hand: Is the UnorderedList actually substitutable for the list class? Not so sure here. If you do "normal" list operations, then you shouldn't notice whether you are using an instance of the list class or of the UnorderedList class. Inserting and retrieving of elements works just fine. On the other hand, you might get unexpected behavior when comparing lists:

list1 = UnorderedList()
list2 = UnorderedList()
list1.append(1)
list2.append(3)
list1 == list2 # False
list1.append(2)
list2.append(2)
list1 == list2 # False
list1.append(3)
list2.append(1)
list1 == list2 # True!

I guess what I'm after is some clarity on how broadly or narrowly the Liskov substitution principle should be applied. Or maybe the solution is something altogether different. Maybe we shouldn't put such a "hack" into the __eq__ special method and rather be explicit about what we're doing, by writing a function like

def sorted_equal(a, b):
 return sorted(a) == sorted(b)

I assume the colleague is working with some framework that expects to be working with list objects but wants to inject this special way of comparing lists.

• Erik Eidt: Are you sure that in the end {1,2,3} == {3,2,3}?
• candied_orange: Been wondering if that was a typo myself.
• Erik Eidt: Sorted-ness is an interesting quality; it is not just sorted vs. unsorted, but rather by what comparison function (or not sorted at all), which is difficult to encode in the type system. There are efforts to do that, for example see here: kataskeue.com/gdp.pdf
• candied_orange: Sets have equality. I was expecting this to act like a set with cardinality.
• Karl Bielefeldt: It's a multiset.

Answer 1

In Python, we have the built-in list container, which is a mutable sequence.

Your new list is not a list according to Liskov. Your list is not a sequence, it is a Multiset otherwise known as a bag. Bags are equal if they contain the same elements in no specific order. There are several implementations already: google MultiSets in Python.

Don't forget about set which is built in. If your bag will only contain unique values.

Answer 2

A fatal flaw of that approach is that the equals method is not "symmetric":

For any reference values x and y, x.equals(y) must return true if and only if y.equals(x) return true.

Consider when you have an instance unOrderedList and another standard python orderedList. They have the same elements but in different order.

unOrderedList == orderedList // true
 but
orderedList == unOrderedList // false

This will break a lot of things in hard to debug ways.

Answer 3

It sounds like going with a single utility method is the way to go. But it should have a name. sorted_equal is named for the implementation. A name like contains_the_same_values puts the emphasis on the true purpose of the function.