It’s impossible to create a Set of Sets because all Set creation functions require comparable types. Why is this? A Set does not have or need the ability to order its elements; it needs only to be able to check equality. Does this constraint belie an implementation detail such as a binary tree for efficient Set operations?

It needs the comparable to operate in O log n. If those runtime characteristics aren’t important to your use-case (small datasets, no tight loops, …), it’s not too hard to make a structure that only checks equality.

The easiest way to do this, I think, would be using pzp1997/assoc-list and having a type alias Set a = AssocList.Dict a ().

Thanks. I came to that conclusion as I was writing my question. So I guess I would probably prefer to just allow Sets to be comparable as well, as was mentioned in the issue I linked and now this collection of issues: https://github.com/elm/compiler/issues/1008.

If a Set has a deterministic ordering of comparable elements, it should make sense for the set itself to be comparable, just like tuples of comparable types are also comparable.

Here is what I’ve understood from the conversation in elm town:

Although the documentation says that you shouldn’t write code which depends on the order of the elements in a set, people do that.

For example, some coder may write the function

pick : Set a -> Maybe a
pick =
Set.toList >> List.head

which picks an “arbitrary” element from a set.

This code should not break anything, if there is a new implementation of set.

For this reason they implement sets using an (internal) ordering.
And when they change the implementation of set, they make sure that this original ordering is respected.

The elements of a set must be comparable so that from that ordering the internal ordering (which is used when implementing sets) can be derived uniquely.

So all of it is for not breaking old, badly written code.

It’s not just that. Let’s say you have two Sets, a and b, and a == b, then toList a == toList b should also hold, since you are allowed by referential transparency to substitute equal values.

Put perhaps it’s worth scrapping equality of sets.

Elm dictionaries are implemented as (self-balancing) binary search trees. Sets are actually just dictionaries with values of type (). If you haven’t seen “unit” before, it’s a type with only one value, also called (). Point is, sets don’t care about the value in the underlying dictionary, only that there is one.

I don’t think this is the case, unless toList imposes an ordering itself. List has a fundamental property that a Set does not share: ordering. Now, an OrderedSet, yes, I’d buy that if a and b are OrderedSets and a == b, then toList a == toList b. But the only way you can get to toList a == toList b is if toList orders the elements of a and b.

In elm, a == b implies f a == f b for any values of a, b, and f. So, toList will always return the elements in the same order, but that order may not be a sorted order.