@rauxyo (Rob) posted a new topic, subject "Why must Set members be comparable?". It read:

   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?
    
    Here's some previous discussion: https://github.com/elm/compiler/issues/310

To which @Erkal_Selman (Erkal Selman) replied

    this may not be an answer but there was an episode of elm town where they talk about this: https://elmtown.simplecast.fm/elm-019-improved-collections-robin-heggelund-hansen

@ilias (Ilias Van Peer) replied

    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 ()`.

After which, @rauxyo (Rob) added

    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.

@rauxyo (Rob) replied

    Thanks, @Erkal_Selman. I remember listening to that episode, but I don't remember them discussing Sets. I'll have to listen again sometime.

After which, @Viir (Michael Rätzel) added

    rauxyo:
    
    > If a Set has a deterministic ordering of comparable elements, it should make sense for the set itself to be comparable
    
    Why? The order for `toList` can be defined by the order of insertion. Why would elements need to be comparable then?

So @Erkal_Selman (Erkal Selman) replied

    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
    [code] 
        pick : Set a -> Maybe a
        pick =
          Set.toList >> List.head
        
    [/code]
    
    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.

@Erkal_Selman (Erkal Selman) replied

    Did you see turboMaCk/any-set? It may solve your problem.

So @norpan (Martin Norbäck Olivers) replied

    It's not just that. Let's say you have two `Set`s, `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.

@mgold replied

    rauxyo:
    
    > Does this constraint belie an implementation detail such as a binary tree for efficient Set operations?
    
    Yes, that's exactly it.
    
    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.

@rauxyo (Rob) replied

    Thanks! That's an interesting implementation.
    
    Coming from a mathematical side, I want sets to be able to contain anything, but I definitely appreciate the logarithmic optimization here.
    
    Hopefully the issues above can be solved.

After which, @rauxyo (Rob) added

    norpan:
    
    > perhaps it's worth scrapping equality of sets.
    
    I hope that doesn't happen.

To which @robin.heggelund (Robin Heggelund Hansen) replied

    For more information on how Elm's data structures work, have a look at this video, where I did my best to explain them: https://www.youtube.com/watch?v=mmiNobpx7eI&t=

After which, @rauxyo (Rob) added

    Thanks, Robin. I hadn't seen that one. The implementation of arrays was fascinating.

After which, @jc00ke (Jesse Cooke) added

    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 `OrderedSet`s 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`.

@dta (David Andrews) replied

    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.

To which @robin.heggelund (Robin Heggelund Hansen) replied

    According to the documentation for `Set.toList`:
    [code] 
            Convert a set into a list, sorted from lowest to highest.
        
    [/code]

To which @jc00ke (Jesse Cooke) replied

    I guess I was conflating math and programming. Both `toList` and `fromList` orders, so my `unless` branch fires 
    
    I guess I should have RTFM eh? 
    [code] 
        > import Set
        > [2, 1, 0, -1, 0, 2] |> Set.fromList
        Set.fromList [-1,0,1,2]
        > [2, 1, 0, -1, 0, 2] |> Set.fromList |> Set.toList
        [-1,0,1,2]
        
    [/code]

@system (system) replied

    This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.


{'source': 'discourse', 'url': 'https://discourse.elm-lang.org/t/why-must-set-members-be-comparable/3205', 'title': 'Why must Set members be comparable?', 'views': 1292, 'has_accepted_answer': False, 'word_count': 919, 'like_count': 12, 'reply_count': 10, 'participant_count': 9, 'posts': 19, 'tags': '', 'author': '@rauxyo (Rob)', 'participants': '@rauxyo (Rob), @Erkal_Selman (Erkal Selman), @ilias (Ilias Van Peer), @Viir (Michael Rätzel), @norpan (Martin Norbäck Olivers), @mgold, @robin.heggelund (Robin Heggelund Hansen), @jc00ke (Jesse Cooke), @dta (David Andrews), @system (system)', 'image_url': [None], 'created_at': '2019-02-23T18:54:44.888Z', 'last_posted_at': '2019-03-11T17:30:40.298Z'}