Introducing assoc-list, a Dict substitute with custom keys


#1

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!)


#2

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.


#3

You continue to impress, Palmer.


#4

Simple and effective, thank you very much :heart:
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.


#5

Wow, epic! Could totally use this!

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?

Just looked at the code. Yup.

Rock on,

Adam


#6

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.


closed #7

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