Bags to accept non-hashable elements

[mlenzen]

Bags should accept non-hashable elements. Currently a bag is backed by a
dict, so you can't add a bag to another bag.

[mlenzen]

Maybe, add a list to the backing. Whenever a mutable elem is added/accessed, it would fall back to the list.

[mlenzen]

I think this does make sense, it won't reduce performance, it will just make bag more flexible.

[joeystevens00]

I think if bag isn't hashable then it can't support checking equality of nested objects when they're not ordered the same way. The underlying data type as a list or a tuple means insertion ordering will be preserved and considered when checking equality. I can't seem to find a way to validate that two unordered nested lists are equal but the bags they represent very well might be.

This means this will be valid:

b = frozenbag([1, 1, 2, 3])	 # prototypical frozen multiset
c = frozenbag([4, 4, 5, 5, b, b])  # make sure we can nest them
d = frozenbag([4, frozenbag([1, 1, 2, 3]), 4, 5, b, 5])
assert bag([4, 4, 5, 5, c]) == bag([4, 5, d, 4, 5])

But this won't because the different ordering of b([1,3,2,1]) causes the data structure to be different than in the child object in d([1,1,2,3]). Both bags contain the same number of elements and are equal when normally checked together but not here:

b = frozenbag([1, 3, 2, 1])	 # prototypical frozen multiset
c = frozenbag([4, 4, 5, 5, b, b])  # make sure we can nest them
d = frozenbag([4, frozenbag([1, 1, 2, 3]), 4, 5, b, 5])
assert bag([4, 4, 5, 5, c]) == bag([4, 5, d, 4, 5])

https://github.com/mlenzen/collections-extended/compare/master...joeystevens00:bag_support_non_hashable_elements?expand=1