Sets aren't comparable

[LiamGoodacre]

I was wanting a unionAll function:

unionAll : Set (Set comparable) -> Set comparable

I went to define it as such:

import Set as S

unionAll xs = S.foldl S.union S.empty xs

a = S.fromList [1, 2, 3]
b = S.fromList [3, 4, 5]
xs = S.fromList [a, b]

main = asText <| unionAll xs

Receiving the following compile error:

Type error on line 3:
Expecting something comparable such as an
Int, Float, Char, String, or a list or tuple of comparables.

        S.union

   Expected Type: S.Set comparable
     Actual Type: comparable

Compiled on share-elm with master/HEAD

[evancz]

I don't think sets should be comparable. In this case, it would be more
efficient to use a function like this:

unions : [Set comparable] -> Set comparable
unions = foldl Set.union Set.empty

This would lead to many fewer comparisons. This Haskell set library does it
this way, and it seems like it'd work for your case. It seems like this
could be a good candidate as a new standard Set function.

On Sunday, October 27, 2013, Liam Goodacre wrote:

I was wanting a unionAll function:

unionAll : Set (Set comparable) -> Set comparable

I went to define it as such:

import Set as S
unionAll xs = S.foldl S.union S.empty xs
a = S.fromList [1, 2, 3]b = S.fromList [3, 4, 5]xs = S.fromList [a, b]
main = asText <| unionAll xs

Receiving the following compile error:

Type error on line 3:
Expecting something comparable such as an
Int, Float, Char, String, or a list or tuple of comparables.

    S.union

Expected Type: S.Set comparable
Actual Type: comparable

Compiled on share-elmhttp://www.share-elm.com/sprout/526cdd1ee4b03cf6e675ba3awith
master/HEAD

—
Reply to this email directly or view it on GitHubhttps://github.com//issues/310
.

Sent from Gmail Mobile

[LiamGoodacre]

It seems very strange to me that I can't have a set of sets.

import Set as S
main = asText <| S.fromList [S.fromList []]

   Expected Type: S.Set comparable
     Actual Type: comparable

As far as I know, all the methods available for creating sets, constrain the argument type to be comparable.
So to have sets of sets, sets would have to be comparable.

Haskell's Data.Set.Set instances the Ord typeclass, and works perfectly fine.

I don't really want to use a list when the problem calls for a set - unless I really have to.

Thanks for your reply, any further thoughts on this?

[evancz]

I currently think this would be an very low priority to add considering the implementation cost is quite high and the concrete benefits are unclear. You are suggesting that your problem calls for sets of sets. I am not convinced by the original example, which I assume is a simplification? Here's the revised example:

import Set as S

unions = foldl S.union S.empty

a = S.fromList [1, 2, 3]
b = S.fromList [3, 4, 5]

main = asText <| unions [a, b]

I am struggling to think of a motivating example. Please share if you have a very strong use case.

[evancz]

Closing in favor of #1008 which tracks a bunch of issues in this ballpark. Idea is that we centralize the feedback in one place so we can have a better answer.

[dustinfarris]

I was wanting to keep track of "collections" of data I am subscribing to over websockets.

e.g., I might be subscribed to channel namefriends::user:12345

This is what I wanted:

type Collection
    = UserFriendsCollection String
    | SomeOtherCollection String
    | ...

type alias model =
    { collections : Set Collection
    , ...
    }

I am trying to hack out something using tuples, but a union type would have fit nicely here.

[robyoder]

I was trying to do the opposite of the OP. I wanted to make a function powerSet:

powerSet : Set comparable -> Set (Set comparable)

The power set of a set is a common function of sets in mathematics, and it is semantically incorrect to represent that as a List or Array of Sets.

For example, the power set of the set {a, b} is {{}, {a}, {b}, {a, b}}.

[robyoder]

Thinking about this more, I can't say I understand why Sets can only have comparable members. The only thing one needs to be able to do with members of a set is compare their equality, not their order.

So I would approach this problem differently and say instead of allowing Sets themselves to be comparable, we could simply remove the constraint that Sets contain only comparable types.

[robyoder]

I posted about this on Discourse. https://discourse.elm-lang.org/t/why-must-set-members-be-comparable/3205/3 The answer makes sense, so I'm back to the OP's position. 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.