I recently published the pzp1997/assoc-list package, which aims to address the problem that the Dict module in elm/core does not work with custom keys.
While there are already several packages that attempt to solve this problem, all of the ones I have found store a function for converting the keys to comparable within the data structure itself. (The downside here is that storing functions in your data can cause runtime errors and makes serialization more challenging.) I decided to approach the problem from a different angle by using a data structure called an association list which only needs keys to be equatable rather than comparable. For better or worse, all types in Elm are equatable, so pretty much any type can be used as a key “right out of the box” in my library.
Intrigued? Check out https://package.elm-lang.org/packages/pzp1997/assoc-list/1.0.0/ for more information! Over there I explain how to use the library (spoiler: it’s a drop-in replacement for elm/core Dict), performance considerations, and take a deeper look at existing alternatives.
(And as an added bonus, you can also use the library as an ordered dictionary!)
Super cool! I love a well-explained pragmatic solution to a theoretically difficult problem like this. Thanks for releasing this and putting the extra effort into the documentation.
Simple and effective, thank you very much
It’s also great how you took care of the documentation
(performance.md), tests and implementation (Tail Call Elimination).
Now we need a Set, but it is not hard from your work. Chadtech/unique-list was actually quite close.
We have massive forms that we store user input field values in a Dict String AnswerValue. Would be super awesome to swap that for this so we can use a custom type aka union type instead of a String to keep track of the field names (to guarantee type)!
Is it just a wrapper around a list? E.g. List ( CustomTypeKey, CustomTypeValue ), then to find a key, you just iterate through the list, e.g. O(n) and return if the keys match?
What would be interesting to see is the performance with specific sized lists, e.g. 10, 100, 500, 1000, 2500, 10000 just to see where the “slowdown” vs. a regular Dict occurs.
In Elixir, we use the list structure all over the place as most of the time you are iterating through a relatively small list (e.g. sub 500 items max, mostly much fewer like 10 to 100 items). Generally speaking, if it’s too big to work with a list, the data is probably in the database.
