Compiler: User-defined data types (and records) not comparable

[pchiusano]

If I define:

data Day = Sun | Mon | Tue | Wed | Thu | Fri | Sat

I cannot compare Day values with < or use Day as a key in a Dict. This really discourages me from defining (and using) more precise types in my programs. I could use a String instead of Day, but then I lose the typechecker's help when I accidentally do something nonsensical that makes sense for arbitrary strings, but not for days. :(

This would be fine if there were a way to provide a custom comparable implementation for a data type, but there's no way to do that, either. This comes up a _lot_. It's very common to want to use some ADT as a key in a Dict, or store some ADT in a Set.

[mgold]

Hmm, Haskell doesn't have this either unless you define it yourself (and it makes you define equality first). I think it shouldn't be _too_ hard to work out the semantics of comparing ADTs but I think it's worth bringing up on the mailing list.

[pchiusano]

Fyi, Haskell has deriving, which gives you a sensible default:

data Woot = Foo | Bar | Baz Int deriving (Ord,Show)

I find that 90% of the time this is all you want - I don't care what the order is, I just want it to be ordered so I can use it as a key in a Map, etc. Also Ord is a subclass of Eq, so you only need to define Ord (which implies Eq).

I can raise this on the list.

[jameshfisher]

+1 -- I just ran into this. Specifically I get the error:

Looks like you want something comparable, but the only valid comparable
types are Int, Float, Char, String, lists, or tuples.

The reason for the limitation in Set and Dict is not because of the implementation of those containers, which look like they use an RB-tree implemented in Elm. It should be simple to add an explicit comparator to this.

The inability to use user-defined data types in core containers (Set, Dict) is a serious shortcoming. I suggest that, until Elm gets typeclasses, those containers should allow the programmer to pass an explicit record-based first-class typeclass, e.g.

type alias Ord a = { compare: a -> a -> Basics.Order }
empty' : Ord k -> Dict k v
empty = empty' { compare = compare }

update : k -> (Maybe v -> Maybe v) -> Dict k v -> Dict k v
-- previously update : comparable -> (Maybe v -> Maybe v) -> Dict comparable v -> Dict comparable v
...

This only introduces a new function empty', redefines empty to be semantically the same, and changes the types for update, insert, remove etc. I think everything type-correct using the old types would also be type-correct with these new types, so this change is backwards-compatible.

(We must assume that the programmer only uses a single Ord k instance per type k. This assumption is necessary for e.g. merge, which would have to choose between the compare functions for the left and right dictionaries.)

[evancz]

Closing in favor of #1008 which will track any issue along these lines and see the different use cases and discussions.

[rtfeldman]

We've run into this a lot with validation errors.

Specifically we want to enumerate all the fields on a form as a union type (e.g. type Field = Username | Password | Email), and then to represent validation errors as a Dict Field String so we can easily look up whether there is an error on a given field with things like Dict.get.

We work around this by using List (Field, String) as a fake Dict and then filter it a lot. You can see a public example of where we're doing this here: http://package.elm-lang.org/packages/NoRedInk/elm-rails/1.1.0/Rails-Decode - we'd definitely prefer if that function had the following signature:

errors : Dict String comparable -> Decoder (Dict comparable (List String))

Right now we can't do that, because if we did we couldn't use union types for our fields.

[Fresheyeball]

:+1: running into this one with some game dev stuff. The inability to express mapping from Union Types as the Model is quite frustrating.

[garbas]

couldn't this be solved using something like

module Days exposing (Day, compare)

data Day = Mon | Tue | Wed | Thu | Fri | Sat | Sun

toInt = Day -> Int
toInt day =
    case day of
        Mon -> 1
        Tue -> 2
        Wed -> 3
        Thu -> 4
        Fri -> 5
        Sat -> 6
        Sun -> 7

compare = Day -> Day -> Bool
compare day1 day2 = (toInt day) > (toInt day2)

[jvoigtlaender]

couldn't this be solved using something like

Depends on what you mean by "this". For example, one of the things mentioned in the opening post is the desire to be able to use Day as the key type in a Dict. Your proposal helps none with that.

[garbas]

@jvoigtlaender sry, i thought Dict part is self explanatory, to use it in Dict i would do, eg:

week = Dict.fromList[(toInt Mon, [ Event "meeting1" ], ...)
modayEvents = week.get <| toInt Mon

you might even create a WeekDict module which would hide all the repetative toInt parts

[jvoigtlaender]

In that plain form, what about the type correctness that the original poster wanted here? How is your solution better than one using Strings? How do you prevent someone from accidentally querying entry 8 in that dict? A Dict Day Whatever would have type guarantees that neither the String nor the toInt approach has.

About a less plain approach, somehow creating a WeekDict that hides toInt calls: How are you going to apply all the wonderful functions from http://package.elm-lang.org/packages/elm-lang/core/latest/Dict and http://package.elm-lang.org/packages/elm-community/dict-extra/latest/Dict-Extra on your WeekDict encapsulation?

[garbas]

@jvoigtlaender thank you for explaining it to me, i'm new to elm. i see now what do you mean by type guarantee.

[OvermindDL1]

About a less plain approach, somehow creating a WeekDict that hides toInt calls: How are you going to apply all the wonderful functions from http://package.elm-lang.org/packages/elm-lang/core/latest/Dict and http://package.elm-lang.org/packages/elm-community/dict-extra/latest/Dict-Extra on your WeekDict encapsulation?

Which can be solved once Elm gets HKT's. Or those libraries decide to invert function control (which I doubt they would do, nor should they really do).

[rtfeldman]

Relevant to this discussion: https://github.com/eeue56/elm-all-dict

[OvermindDL1]

@rtfeldman Ooo interesting find, though it might be better to make toString wrappers in your own code? I am curious if there is a Dict that can store any record especially though. I'd love to be able to store dynamic TEA component models like that in a library I've made...

[amigalemming]

A type-safe but cumbersome work-around could be to create custom Dict type for Day keys, by wrapping a Dict Int a. E.g.

type DayDict a = DayDict (Dict Int a)

insert : Day -> a -> DayDict a -> DayDict a
insert day a (DayDict dict) = DayDict (Dict.insert (dayToInt day) a dict)

[aryairani]

Running into this. If tuples are comparable, shouldn't records (which are also an enumerable list of fields) and ADTs (which are are an enumerable list of constructors, each with an enumerable list of fields) also be comparable?

I also just had to downgrade my intended Sets and Dicts to Lists and Lists of pairs, and was unconsciously moving towards @rtfeldman's approach:

We work around this by using List (Field, String) as a fake Dict and then filter it a lot.

but I feel like this will get out of control quickly.

+1 to comparable ADTs, and why not records as well, especially since they may be part of the ADT.

[brianhempel]

Sketch-n-Sketch would benefit from allowing arbitrary ADTs as set members and dictionary keys; also allowing arbitrary ADTs to be comparable would be beneficial as well.

A proposal. Perhaps decomposing comparability into two classes is clearest:

(1) For enumerated ADTs that have a natural ordering, such as the days of the week example above, allow the ADT to be annotated as comparable:

comparable type Day = Sun | Mon | Tue | Wed | Thu | Fri | Sat

In practice, this would be equivalent to Haskell's deriving (Ord), and would allow the user to use < > >= <= on instances of their ADT.

(Ideally, a custom comparison function could be specified, but that is a separate feature.)

(2) It may not make sense to allow the use of < > >= <= on all ADTs. Some ADTs do not have a natural ordering. However, even these ADTs should be usable as set members or dictionary keys.

Requiring "comparability" to be a set member/dictionary key is an implementation detail—if sets were based on hashmaps then they would require "hashability". Because "comparability" is an implementation detail, keep it hidden.

Allow all ADTs to be internally comparable using special methods (e.g. internal_less_than, internal_greater_than) and silently use those methods to implement set membership and dictionary keying.

A user can thus use any ADT in a set or dictionary, but cannot call < > >= <= on their ADT unless they explicitly mark it comparable.

---

_Update 2017-12-13:_ Having mulled on this for almost a year now, item (2) above is much more important to us than item (1). I can't think of any place in Sketch-n-Sketch where we need ADTs to be comparable so we can sort them: we just need to be able to use arbitrary items as set members and (less often) dictionary keys.

_Update 2017-12-20:_ Item (2) of this proposal now has a pull request which allows using ADTs and records in sets.

[ktonon]

I'm generating an elm package for the AWS SDK (from the apis/*.normal.json files). Some of the types are maps from enums to other things. For example, from devicefarm-2015-06-23.normal.json

"PurchasedDevicesMap":{
  "type":"map",
  "key":{"shape":"DevicePlatform"},
  "value":{"shape":"Integer"}
},
"DevicePlatform":{
  "type":"string",
  "enum":[
    "ANDROID",
    "IOS"
  ]
},

I would like to represent DevicePlatform as

type DevicePlatform
    = ANDROID
    | IOS

but currently I can't because then PurchasedDevicesMap becomes

Dict DevicePlatform Int

[masklinn]

(1) For enumerated ADTs that have a natural ordering, such as the days of the week example above

I think the ability to have ordering on sum types in Elm would be very convenient (especially if it were necessarily opt-in would be neat). That said I want to note that DoW is a terrible example for it as the ordering is highly locale-dependent, as those paying attention may have noticed from @garbas 's comment:

1. although the abrahamic tradition starts the week on Sunday, that only remains in the Americas, and a few other specific countries (not necessarily of abrahamic tradition): Japan, India, Israel, South Africa, Taiwan
2. Most of the world (Europe, Oceania, most of Asia) starts the week on Monday, that's also the ISO-8601 standard
3. And the Islamic world starts the week on Saturday

So weekdays are mostly an argument towards not ordering sum types.

Some ADTs do not have a natural ordering. However, even these ADTs should be usable as set members or dictionary keys.

To the extent that they are either "empty" or containing suitable items themselves, in fact that's one issue with a comparable annotation (aka deriving(Ord)), it would/will need to handle sum types which can not be made comparable.

Because "comparability" is an implementation detail, keep it hidden.

It's not an implementation detail, it's necessarily part of the API since it's a contract the map key must fulfill for the collection to work properly. Just as hashability (and equatability, and that the two are coherent) is part of the contract for hashmaps.

Adding a "secret" implicit comparability for hashmap would be unlikely to make things clearer, as you'd now get sum types which can and can't be used as map keys without any explanation why e.g. sum types where any constructor has collection or record associated data. Requiring an explicit annotation and only allowing annotated sum types to be used as keys would provide the occasion for the compiler to generate clear error messages in case of incompatibility.