get : key -> Dict key value -> Maybe value

insert : key -> value -> Dict key value -> Dict key value

fromList : List (key, value) -> Dict key value

toList : Dict key value -> List (key, value)

Now let me list some properties that are really nice to have in a Dict type:

1. The key type variable doesn't have to be comparable

2. Two dicts with exactly the same key-value pairs are equal regardless of insertion order. For example, fromList [ ("X", 0), ("Y", 1) ] == fromList [ ("Y", 1), ("X", 0) ]

3. If dictA == dictB then f dictA == f dictB where f can be any function^(?)

4. Renaming/reordering record fields or custom type variants^(?) should never change the order of key-value pairs returned from toList

I expect some readers will wonder why these properties matter. Maybe they feel arbitrary. Let me make a case for why they are important:

1. We want keys to be non-comparable for the sake of convenience and type-safety. It's annoying when I have type Id = Id String or { x : Int, y : Int } and I have to convert them into a comparable type before they can be used as a key. This leads to boilerplate code and increased risk of mixing up types which can lead to bugs.

2. Having two Dicts be equal based on contents, regardless of insertion order is nice but often not that big a deal. But for Sets it's kind of their whole purpose. And Sets are essentially just an alias for Dict key ()

3. dictA == dictB implies f dictA == f dictB is quite handy:

   • If two values are equal and the same function is applied to both, you can save yourself CPU time by only computing one and reusing the result. This can also be used for caching.

   • It's easier to reason about what some code does if you are certain that == means two values are indistinguishable no matter what you do to them.

   • Any code written in Elm will have this property. It would be a shame for lamdera/containers to introduce some kernel code that violates this!

4. People often mention that when refactoring in Elm, they feel safe making large changes to their code. Part of why this is true is because renaming or reordering functions/types/fields/variants will never affect the runtime behavior of Elm code (with the sole exception being field order affecting record constructors^(?)). It would be a shame to lose this just because, Dict.toList would change when renaming/reordering record fields or custom type variants.

First, lets consider the built-in Dict type. Which of the 4 properties does it support?

1. Well it fails on 1. You can only have comparable keys.

2. It passes on 2. You'll find that fromList [ ("X", 0), ("Y", 1) ] == fromList [ ("Y", 1), ("X", 0) ] is indeed true.

3. Passes on 3. dictA == dictB implies f dictA == f dictB

4. And passes on 4. Since the built-in Dict only allows for comparable keys, records and custom types aren't allowed. Which in turn means there's no way for renames or reorderings to affect toList

type Color
    = Red
    | Green
    | Blue

myDict =
    fromList [ (Blue, 2), (Green, 1), (Red, 0) ]

We have three options:

1. Sort based on variant names. For example alphabetically sort the names in ascending order. Which gives us toList myDict == [ (Blue, 2), (Green, 1), (Red, 0) ]

2. Sort by the order the variants are defined in code. That gives us toList myDict == [ (Red, 0), (Green, 1), (Blue, 2) ]

3. Sort the list based on the order the key-value pairs were added. Then we get toList myDict == [ (Blue, 2), (Green, 1), (Red, 0) ] which is just the original list.

Do any of these approaches to sorting let us keep all 4 of the nice-to-have properties?

1. Violates 4. If we rename a variant, it could potentially change its alphabetical ordering and thereby change the output of toList.

2. Also violates 4. If we reorder our variants, that will change the output of toList

3. This does not violate 4! But what about 2 and 3?

   • Well it depends on how == is implemented for our Dict type. Supposed dictA == dictB is the same as writing toList dictA == toList dictB. In that case 2 fails in the following example:

     a = fromList [ ("X", 0), ("Y", 1) ] == fromList [ ("Y", 1), ("X", 0) ]
     
     -- is converted into this because of how we defined == to work for dict equality
     a = toList (fromList [ ("X", 0), ("Y", 1) ]) == toList (fromList [ ("Y", 1), ("X", 0) ])
     
     -- simplifies to this since ordering by insertion means toList and fromList cancel eachother out
     a = [ ("X", 0), ("Y", 1) ] == [ ("Y", 1), ("X", 0) ]
     
     -- which is
     a = False
     

     On the bright side, property 3 is valid at least!

   • Okay well how about we make it so dictA == dictB checks that both dicts have the same key-values pairs while ignoring order? In that case 2 is valid! But let's look at 3. Consider this code:

     dictA = fromList [ ("X", 0), ("Y", 1) ]
     dictB = fromList [ ("Y", 1), ("X", 0) ]
     
     a = dictA == dictB --> True
     
     b = toList dictA == toList dictB --> False
     

     This violates 3 which says that if dictA == dictB is true, then that implies f dictA == f dictB is also true for any function f. In our example that's not the case when f is toList

type Color
    = Red
    | Green
    | Blue
    compareWith(compareColor)

compareColor : Color -> Color -> Order
compareColor a b =
    Basics.compare (colorToInt a) (colorToInt b)

colorToInt : Color -> Order
colorToInt a =
    case a of
        Red -> 0
        Green -> 1
        Blue -> 2

get : key -> Dict key value -> Maybe value

insert : key -> value -> Dict key value -> Dict key value

fromList : List (key, value) -> Dict key value

toList : Dict key value -> List (key, value)

toList : (key -> key -> Order) -> Dict key value -> List (key, value)

import SomePackage exposing (OpaqueType)

dict : Dict OpaqueType Int
dict = fromList [ ... ]

list = toList sortBy dict

sortBy = Debug.todo "How do I sort an opaque type that doesn't expose any data I can use to sort with?"

Oh. And you probably want to know which properties I ended up choosing for the Dict and Set type in lamdera/containers. It was difficult to decide but here's what I settled on:

1. Obviously I included support for non-comparable keys. This whole package would be pointless without it.

2. I gave up fromList [ ("X", 0), ("Y", 1) ] == fromList [ ("Y", 1), ("X", 0) ]. This means if you want to check if two Dicts or Sets are equal, you'll need to use an extra function called unorderedEquals. This isn't ideal since you can't use it on a larger data structure that contains a Set.^(?)

3. I kept 3.

4. I kept 4.

Is it possible to pick any combination of three properties?

And of course, you can pick fewer than three properties. Elm is rare in that it guarantees properties 3 and 4 for any user code. Most languages don't and that probably extends to their respective Dict types.

Can this package be used with the normal Elm compiler?

This package is only supported by the Lamdera compiler^(?). In part this is because it contains kernel code and it's unlikely I'd be allowed to publish it to the Elm package ecosystem. But even if I was allowed, it also overrides Debug.toString and == which is only possible due to some changes to the compiler.