New package to use custom-types as keys in sets/dicts

[opvasger]

Hello

I’ve released a small package that reimplements all the parts of elm/core that rely on the magical comparable type-variable.

The package is available here.

The biggest upside is that custom-types are more ergonomic this way - you can use them with dictionaries & sets - below is the example from the readme - enjoy!

module Example exposing (N, compare, oneAndTwo, sort, toInt)

import Comparable
import Comparable.Set as Set exposing (Set)

type N = One | Two | Three

-- sort of nice, no?
sort : List N -> List N
sort = Comparable.sort compare

-- dict/set are available too.
oneAndTwo : Set N
oneAndTwo = Set.fromList compare [One,Two,Two,Two,Two]

-- this one builds on Basics.compare, which is usually what you want.
compare : N -> N -> Order
compare a b = Basics.compare (toInt a) (toInt b)

-- these conversions are often implemented for other purposes too.
toInt : N -> Int
toInt n =
    case n of
        One ->   1
        Two ->   2
        Three -> 3

[eike]

Unfortunately, you lose equality checks for dicts and sets as well. (The built-in versions have a special case in the compiler that makes them equal if and only if they contain the same elements or key-value pairs.) And if you’re willing to lose those checks, you can also save the From function in the data structure which would mean that users wouldn’t have to supply it at every call site.

[opvasger]

I tried a bunch of cases implementing it, and got working results for equality checks - can you show me how it doesn’t work?

https://ellie-app.com/jvwxTjMs77ra1

[yosteden]

@eike is referring to the problem that arises when a change causes your red-black tree to rotate. Elm checks for exact structural equality, which is almost certainly not what you want.

E.g. the following two sets probably should be equal, but aren’t.

import Comparable.Set as Set exposing (Set)

set0 = [1, 2, 3, 4]
    |> Set.fromList Basics.compare
    |> Set.remove Basics.compare 1
    |> Set.insert Basics.compare 1
    
set1 = [1, 2, 3, 4]
    |> Set.fromList Basics.compare

-- set0 == set1 returns False even though both are sets
-- containing the elements 1, 2, 3, and 4 and sets are unordered

You can see this in the following Ellie.

https://ellie-app.com/jvB42jR8xWJa1

And as @eike points out, if you’re willing to give up equality checks, you can just embed the function in the data structure itself and not have to pass compare for every data structure operation.

EDIT: or perhaps an even more basic example is the following:

import Comparable.Set as Set

set0 = [4, 3, 2, 1]
    |> Set.fromList Basics.compare
    
set1 = [1, 2, 3, 4]
    |> Set.fromList Basics.compare

-- set0 == set1 is False

[opvasger]

Thank you - I’ll make a patch revision to document this, and try to find a way to work around it.

The goal of the package is to use comparable type-vars as little as possible, and it still achieves that.

It would block any progress to embed the comparison-function in the data structure, and give up on equality - it would perhaps be better to add a working equality-function and document the problem clearly.

Thanks again I really appreciate the help

Does anyone know of structurally consistent data-structures with comparable (lol) performance-characteristics?

[opvasger]

I’ve published 1.2.0 with a notice about equality in the readme, Dict.equals and Set.equals.

If I ever find a performant way to have structural equality for these data-structures, it will now be a major revision where I remove the equality-functions.

[TankorSmash]

Semi-related, is it possible to somehow disable the (==) operator for a given type in Elm? I could see it being fairly easy to forget to use the Dict.equals function after some time away and without any compiler warnings.

[yosteden]

@robin.heggelund did some explorations on the subject of collections that adhere to strict structural equality. You have to pay some performance overhead for it, but it might be in the realm of acceptable. See collections-ng 3.0.0.

[yosteden]

Unfortunately it is not possible to disable the (==) operator. The more insidious bit is when the collection is nested deep within a larger data structure and someone decides to use (==) on the larger data structure, because there’s no hint at all that the data structure will break (==). Breakage of (==) is infectious. If any part of your data structure can’t use (==) then the entire whole cannot use (==).

This is why I prefer just runtime exceptions for things that don’t obey the usual semantics of ==. Not throwing an exception and instead providing an alternative equality operator makes it too easy to do the wrong thing. Runtime exceptions are bad, but even worse are completely silent errors.

[opvasger]

This sort of review makes me
feel bad about sharing this package and I think I’m making these my final words here, to focus on using Elm instead of participating in it socially.

[yosteden]

@opvasger I would be very sad to see you go. 15 people (at the time of this writing) have “heart”-ed your post. @miniBill and @dirkbj separately have also both “heart”-ed your follow-up post with the custom equality operators. I do not like using custom equality operators to make up for == behavior that conflicts with other data structure invariants. I am, however, but one voice and my opinion does not negate the value of your package, which clearly has found supporters among the community.

At least as far as I can see, the Elm community is poorer without your social contributions.

[miniBill]

I appreciate your work and would love to see more of it. Nothing is perfect but the effort you have put into this is valuable, and the result is a perfectly reasonable point on the tradeoff frontier