DEV Community

loading...

ReScript and association lists

John Jackson
I’m probably riding my bicycle or coding.
Updated on ・4 min read

This article was originally written with ReasonML. I updated it in May 2021 to use ReScript.

In my previous posts, we learned about ReScript's Map and HashMap containers. They’re powerful, and you will most likely want to use them in any medium-to-large ReScript project. But we also saw that they can be complex, especially when working with custom key types. What if you want to create a map without all the boilerplate? That’s what association lists are for.

The association list isn’t a new idea, but it isn’t common in JavaScript, so may seem strange at first for someone learning ReScript. You can think of it as the map’s predecessor. It maps keys to values but in a much more primitive way.

Association list basic facts

  • They are simpler than maps.
  • They require less boilerplate code.
  • They have all of the features of regular lists (pattern matching, immutability, etc.).
  • They are slower than maps.
  • They are suitable for small data, but don’t scale well.

Creating an association list

Association lists require no boilerplate code to set up. They are literally just lists of key-value-pairs. It’s this easy to make one:

let scores = list{("John", 3), ("Mary", 5), ("Servo", 2)}
Enter fullscreen mode Exit fullscreen mode

And that’s all you have to do. We’ve “mapped” John to a score of 3, Mary to a score of 5, and so on. ReScript has no formal type definition for an association list, but the signature is essentially list(('key, 'value)).

Really, that’s it! No functors, no cmp function, nothing fancy.

Getting a value

We can use Belt.List.getAssoc to look up any key. It takes the following arguments: a list (list(('key, 'value))), a key ('key), and an equality function (('key, 'key) => bool). It returns option('value).

For complex key types, you can write your own equality function (similar to the cmp value we saw in a previous post). But for basic cases, don’t forget that === is just a function! We can use it like this:

let johnScore = Belt.List.getAssoc(scores, "John", \"==")
/* returns Some(3) */
Enter fullscreen mode Exit fullscreen mode

(Note that it’s mandatory to wrap the === in parentheses to pass it like a value.)

Other functions

Belt.List comes with a few other handy functions:

hasAssoc returns whether a key exists or not.

Belt.List.hasAssoc(scores, "Mary", \"==")
/* returns true */
Enter fullscreen mode Exit fullscreen mode

removeAssoc removes a key and its value.

Belt.List.removeAssoc(scores, "Servo", \"==")
/* returns [("John", 3), ("Mary", 5)] */
Enter fullscreen mode Exit fullscreen mode

setAssoc sets a key and a value.

Belt.List.setAssoc(scores, "Joel", 10, \"==")
/* returns [("Joel", 10), ("John", 3), ("Mary", 5), ("Servo", 2)] */
Enter fullscreen mode Exit fullscreen mode

And, of course, you can use any other function that accepts lists. You can sort them with Belt.List.sort, filter them with Belt.List.filter, or you can even pattern-match them:

switch scores {
| list{(name, score), ...rest} =>
  doSomethingWith(name, score)
  doSomethingElseWith(rest)
| list{} => doSomethingElse()
}
Enter fullscreen mode Exit fullscreen mode

The downsides to association lists

At a glance, they seem to have all of the same functionality of maps, but without the complexity. So what’s the difference? Their simplicity is a double-edged-sword.

Maps are powered by AVL trees, which are elegant data structures that ensure that looking up values is efficient even with huge numbers of keys (O(log n) time complexity). Lists, by comparison, always have O(n) time complexity.

To put that in perspective, a map with a thousand keys will only take three times longer to look up a value than a map with ten keys. With association lists, the list with a thousand keys will take a hundred times longer than a list with ten. These time costs aren’t limited to looking up keys. Almost any function used on a list (setAssoc, hasAssoc, etc.) will scale at the same rate.

If you want add to a list without setAssoc, you can do it just like a regular list:

let newScores = list{("Mike", 7), ...scores}
Enter fullscreen mode Exit fullscreen mode

This is faster than setAssoc, but can have consequences. You aren’t checking if "Mike" already exists, so it’s possible that you’ll end up with two entries with the same key. This isn’t always dangerous because getAssoc will return the most recent entry it finds (just don’t try to shuffle the list), but it degrades performance. The old entry isn’t physically removed, so the list gets longer with stale data, making every function afterwards slower and slower.

When to use association lists

Association lists are handy, but best employed in small doses. For small sets of data, they may make more sense than a map. I took advantage of them in a few places in Coronate. I had data that would be, at most, five entries long. At that small size, the speed benefits of a map wouldn’t outweigh the complexity of instantiating it. They also let me use type variants as keys without writing a comparison function, like a map would require.

If your data is small and won’t change much after its initial creation, then association lists may make your life easier. If not, then you might want to invest in a more mature container type like a map or a hashmap.

Discussion (3)

Collapse
yawaramin profile image
Yawar Amin

Great article! I want to point out another differentiation of association lists–their keys don't need to be unique. With a map/hashmap, if you put a duplicate key in it usually replaces the existing one. With an association list, both are kept.

Sometimes this is actually a really good property to have, e.g. you really do want this for HTTP headers which can explicitly contain duplicate header names like Set-Cookie. See e.g. inbox.ocaml.org/caml-list/20190925...

Collapse
idkjs profile image
Alain

Could you get the values out of your book reviews map in your previous post using this technique?

Collapse
johnridesabike profile image
John Jackson Author

If you mean get values from the actual map, then no. Maps and lists are completely different types.

However, you can create an association list that would have the same functionality of the map:

let reviews = [(book1, review1), (book2, review2),...etc];

Because the books are records, you wouldn’t be able to use the (===) function to look them up; you’ll have to provide a custom equality function. That would probably look similar to the comparison function we used in the previous post, but it would have to return a boolean instead of an integer.

Belt.List.getAssoc(reviews, someBook, bookEqualsFn);
/* returns option(review) */