In this chapter, we’ll discuss other common data structures for representing collections of values: sets, maps, stacks, and queues. ReScript’s standard libraries provide several options for these collections, with similar APIs but different use cases. We’ll break down these collections into two categories: immutable collections and mutable collections.
Like lists, updates on immutable collections are functional and do not actually change the contents of the collection being updated. Instead, they return a new collection with the update applied.
The immutable collections we will cover include Belt.Set and Belt.Map.
Like arrays, updates on mutable collections change the contents of the collection. They are similar to collections in JavaScript.
The mutable collections we will cover include
Belt.HashSet
Belt.MutableSet
Belt.MutableMap
Belt.HashMap
Js.Dict
Belt.MutableQueue
Belt.MutableStack
For reference, here are some tables comparing different types of sets and maps in ReScript’s standard library. We’ll go into more detail about their usage and performance later in the chapter, and it may be useful to refer back to this table for side-by-side comparisons.
First, let’s compare the three different types of sets:
A representation exhibits the comparison between the 3 different types of sets. It includes data on the collection, details about their usage, performance, and runtime representation.
Next, let’s look at the four different types of maps:
A representation exhibits the comparison between the 4 different types of sets. It includes data on the collection, details about their usage, mutable, J SON compatible, performance, and runtime representation.
Immutable Collections
ReScript’s standard library supports immutable sets and maps, through the Belt.Set and Belt.Map modules.
Similar to lists, updates made to these immutable collections do not modify the original collection. Unlike lists however, random lookups have good performance – the time to look up a certain value in an immutable set/map scales logarithmically with the number of elements it has.
Another useful property of these immutable collections is that they are naturally sorted. This means that operations that iterate through all the keys, such as map, forEach, reduce, etc., will iterate through the keys in a predictable order, and finding the minimum/maximum key in the collection costs the same as looking up any other key.
Immutable Sets
Belt.Set is an immutable collection used to store a set of unique values.
There are two specialized submodules to support common use cases: use Belt.Set.Int for sets of integers and Belt.Set.String for sets of strings.
Creating a Set
Sets can be initialized empty or from an array of values:
open Belt
let emptySet = Set.String.empty
let birdSet = Set.String.fromArray([
"robin",
"robin",
"sparrow",
"duck"
])
Sets can be easily converted to arrays and lists with toArray and toList, respectively. The former is also useful for debugging purposes, since arrays have a more readable format when printed:
birdSet->Set.String.toArray->Js.log
Console output:
["duck", "robin", "sparrow"]
Updating a Set
Updating a set returns a new set without modifying the original:
let set = Set.String.empty
let set' = set->Set.String.add("duck")
let set'' = set'->Set.String.remove("duck")
Js.log(Set.String.size(set))
Js.log(Set.String.size(set'))
Js.log(Set.String.size(set''))
Console output:
0
1
0
Updates and operations can be chained using the pipe operator:
let set = Set.String.empty
->Set.String.add("duck")
->Set.String.add("pigeon")
->Set.String.add("duck")
->Set.String.remove("pigeon")
set->Set.String.toArray->Js.log
Console output:
["duck"]
Common Set Operations
Use Set.has to check if an element is in a set:
let seenBirds = Set.String.fromArray(["duck"])
let hasSeenDuck = Set.String.has(set, "duck")
let hasSeenChicken = Set.String.has(set, "chicken")
Js.log(hasSeenDuck)
Js.log(hasSeenChicken)
Console output:
true
false
The API for sets supports common operations such as union (union), intersection (intersect), and difference (diff). These operations will all return a new set without changing the inputs:
let allSeenBirds = Set.String.union(seenBirdsDay1, seenBirdsDay2)
let seenBothDays = Set.String.intersect(seenBirdsDay1, seenBirdsDay2)
let seenFirstDayOnly = Set.String.diff(seenBirdsDay1, seenBirdsDay2)
allSeenBirds->Set.String.toArray->Js.log
seenBothDays->Set.String.toArray->Js.log
seenFirstDayOnly->Set.String.toArray->Js.log
Console output:
["duck", "pelican", "robin", "sparrow"]
["duck"]
["robin", "sparrow"]
Immutable Maps
Belt.Map is an immutable collection used to store key-value mappings. The interface for maps is very similar to the interface for sets. Use Belt.Map.Int for maps with integer keys, and Belt.Map.String for maps with string keys.
Here are some examples showing how to use Belt.Map.String. Maps with other key types work the same way; the main difference is which module’s functions are being used.
Creating a Map
Maps can be initialized empty or from an array or list of key-value pairs:
open Belt
let emptyMap = Map.String.empty
let birdCount = Map.String.fromArray([
("duck", 126),
("goose", 23),
("pelican", 3),
("heron", 5)
])
Maps may be converted to an array of key-value pairs using toArray. This is useful if we need to print the contents of the map:
birdCount->Map.String.toArray->Js.log
Console output:
[
["duck", 126],
["goose", 23],
["heron", 5],
["pelican", 3]
]
Updating a Map
Map updates are immutable, meaning they return a new map without modifying the original:
let map = Map.String.empty
let map' = map->Map.String.set("duck", 10)
let map'' = map'->Map.String.remove("duck")
map->Map.String.size->Js.log
map'->Map.String.size->Js.log
map''->Map.String.size->Js.log
Console output:
0
1
0
As with sets, updates and other operations can be chained using the pipe operator:
let map = Map.String.empty
->Map.String.set("duck", 10)
->Map.String.set("pigeon", 5)
->Map.String.remove("pigeon")
map->Map.String.toArray->Js.log
Console output:
[["duck", 10]]
Accessing a Map
There are three APIs that can be used to access values in maps:
get returns an optional value, forcing us to handle cases when the key does not exist.
getExn throws Not_found if the key does not exist.
getWithDefault returns a default value if the key does not exist.
Here are some examples of those APIs in action:
let sawPelicans = Map.String.get(birdCount, "pelican")
switch sawPelicans {
| Some(_) => Js.log("saw pelicans")
| None => Js.log("did not see pelicans")
}
let ducks = Map.String.getExn(birdCount, "duck")
Js.log(ducks)
let swans = Map.String.getWithDefault(birdCount, "swan", 0)
Js.log(swans)
Console output:
saw pelicans
126
0
Using Collections: Luggage Example Revisited
One common use case for collections is aggregating values from a list or array. Recall the luggage example from the last chapter, where we had the following array of passengers and their luggage:
To get the set of passenger names without duplicates, we can use a set. First, we use Array.map to get an array of just the names. Then, we create a set. Finally, we convert the set back into a new array without duplicates:
let passengers = Belt.Array.map(luggage, ((name, _)) => name)
->Belt.Set.String.fromArray
->Belt.Set.String.toArray
Js.log(passengers)
Console output:
["John", "Sarah", "Seth"]
Recall that in the previous chapter we also wanted to calculate the total weight of the luggage carried by each passenger. That can be done easily and cleanly using a map.
We start with an empty map and use Array.reduce with an accumulator function that returns the updated map at each step. Notice that using getWithDefault allows us to avoid having to specify separate cases to handle whether or not the key already exists:
let totalLuggagePerPerson = (luggage: array<(string, int)>) => {
Higher-order functions like map, keep, and reduce are not just for lists and arrays; they can be used on standard library collections as well:
let luggageMap = totalLuggagePerPerson(luggage)
let tooMuchLuggage = luggageMap->Belt.Map.String.keep((_, weight) => weight > 200)
tooMuchLuggage->Map.String.keysToArray->Js.log
let totalLuggageWeight = luggageMap->Belt.Map.String.reduce(0,
(sum, _, weight) => sum + weight
)
Js.log(totalLuggageWeight)
Console output:
["John"]
489
Advanced Topic: Generic Collections
While working with collections, we’re bound to come across cases where we want to use custom data types (not strings or integers) in our collection.
Unlike many other languages, ReScript allows us to use complex data like arrays or objects as the keys for sets and maps. There isn’t really a distinction between “primitives” and “references/objects” – all data types are treated equally and a generic set or map can hold anything, as long as there’s a way to compare them.
The first step to creating a generic set is defining a comparison function for our data type. The comparison function takes in two values, returning -1 if the first value is “less” than the second value, 1 if the first value is “greater” than the second value, and 0 if the values are the “same.” How we define “less,” “greater,” and “same” are entirely up to us, as long as the definitions are consistent. The reason we need to define these comparisons is because values in a set and keys in a map are ordered, and we need a way to define a global ordering over the possible values in the set.
To illustrate, let’s define a comparison function for integers (creating a set with this would be roughly equivalent to Belt.Set.Int):
module IntCmp = Belt.Id.MakeComparable({
type t = int
let cmp = (a, b) => {
if a < b {
-1
} else if a > b {
1
} else {
0
}
}
})
Notice that we’re actually calling Belt.Id.MakeComparable on a module that contains the definitions of our data type and comparison function. The idea of functions that take in modules and create other modules is called functor – we’ll explore that in more detail in a later chapter.
With our custom comparable module defined, we can create generic sets by passing our comparable module in the ~id named parameter. In the example we initialize the set from an array using Set.fromArray; empty sets can be created using Set.make:
let intSet = Belt.Set.fromArray([1, 2, 3, 4, 4], ~id=module(IntCmp))
intSet->Belt.Set.toArray->Js.log
Console output:
[1, 2, 3, 4]
If we want the values in the set to be in reverse order, we can simply change the comparison function:
module RevIntCmp = Belt.Id.MakeComparable({
type t = int
let cmp = (a, b) => {
if a < b {
1
} else if a > b {
-1
} else {
0
}
}
})
let revIntSet = Belt.Set.fromArray([1, 2, 3, 4, 4], ~id=module(RevIntCmp))
revIntSet->Belt.Set.toArray->Js.log
Console output:
[4, 3, 2, 1]
Now that we’ve covered how to define custom comparables, let’s apply this to a more practical example – the board game Battleship. Battleship involves two players trying to sink each other’s ships placed on separate 10x10 grids. Players take turns guessing coordinates on the grid without knowing where the other player’s ships are – if the guessed coordinate has a ship on it, then that ship is “hit.”
In our Battleship game, coordinates are tuples of two integers representing the x and y values, respectively. We can use sets of coordinates to represent the locations that have already been guessed, and the locations of the ships. To create a generic set of coordinates, we need to first define a comparable module:
module CoordCmp = Belt.Id.MakeComparable({
type t = (int, int)
let cmp = (a, b) => Pervasives.compare(a, b)
})
Custom Comparison Functions
We used Pervasives.compare to define the comparison function. This is sort of a generic deep comparison function that we can use for composite data types like tuples. It’s handy, but may be less efficient than a manually defined comparison function. If we wanted to implement the comparison function for integer pairs manually, it might look something like this:
let cmp = ((x1, y1), (x2, y2)) => {
if x1 < x2 {
-1
} else if x1 > x2 {
1
} else if y1 < y2 {
-1
} else if y1 > y2 {
1
} else {
0
}
}
Next, we’ll initialize a set of coordinates we have already guessed, along with a set of coordinates that contain a ship:
let guessed = Belt.Set.fromArray([(1,1)], ~id=module(CoordCmp))
let ships = Belt.Set.fromArray([(2,2), (2,3), (2,4)], ~id=module(CoordCmp))
Finally, we’ll write a function that checks a coordinate value against the contents of the sets and print out an appropriate message for the player. For simplicity, we’ll treat out-of-bounds shots as misses.
Notice that we do not have to pass the ~id param to any of the generic set functions after we create it:
let checkCoord = ((x, y) as coord, guesses, ships) => {
open Belt
if guesses->Set.has(coord) {
Js.log("already guessed")
} else if ships->Set.has(coord) {
Js.log("hit")
} else {
Js.log("miss")
}
}
checkCoord((1, 1), guessed, ships)
checkCoord((0, 0), guessed, ships)
checkCoord((2, 2), guessed, ships)
Console output:
already guessed
miss
hit
We can use the same method to create maps with generic keys. To give a more concrete example, let’s reimplement what we have from before using a generic map. This time, we will create a map where the keys are x-y coordinates and the values are what is on those coordinates. Again, we will ignore out-of-bounds checks and omit empty squares for simplicity.
First, we’ll define a simple variant type for the values:
type grid = Ship | Guessed
Next, we’ll initialize a generic map with some initial values like we did with sets earlier:
Finally, we can use switch to pattern match on the optional value returned from Map.get to elegantly implement checkCoord:
let checkCoord = ((x, y) as coord, board) => {
switch Belt.Map.get(board, coord) {
| Some(Guessed) => Js.log("already guessed")
| Some(Ship) => Js.log("hit")
| None => Js.log("miss")
}
}
checkCoord((1, 1), board)
checkCoord((0, 0), board)
checkCoord((2, 2), board)
Console output:
already guessed
miss
hit
Mutable Collections
In addition to immutable collections, ReScript’s standard library also supports a number of mutable collections. These mutable collections work the same way that arrays and collections work in JavaScript – any updates will mutate the collection in-place.
Mutable collections are useful even if we are writing code in a functional style, and in some cases it is preferable to use mutable collections over immutable ones for reasons such as performance or JSON compatibility. In addition to mutable versions of map and set, ReScript’s standard library also offers mutable stacks and queues.
Mutable Stack
Belt.MutableStack implements a LIFO (last-in first-out) stack data structure. As its name suggests, updates to the stack modify it in place. A mutable stack can contain elements of any type, as long as its contents are all the same type.
Empty stacks are created using the make function, and elements can be added using push:
open Belt
let s = MutableStack.make()
s->MutableStack.push("a")
s->MutableStack.push("b")
s->MutableStack.push("c")
The pop function mutates the stack to remove the top element and returns the element. The top function returns the top element without removing it from the stack. Both of these functions return optional values – if the stack is not empty, then they will return the element wrapped with Some; otherwise, they will return None:
let s = MutableStack.make()
s->MutableStack.push("a")
s->MutableStack.push("b")
s->MutableStack.push("c")
s->MutableStack.size->Js.log
s->MutableStack.pop->Option.getExn->Js.log
s->MutableStack.size->Js.log
s->MutableStack.top->Option.getExn->Js.log
s->MutableStack.size->Js.log
Console output:
3
c
2
b
2
We can iterate through the elements of a stack using the forEach function. The iteration order will always be the same order elements would be popped in, the reverse of the insertion order:
let s = MutableStack.make()
s->MutableStack.push("a")
s->MutableStack.push("b")
s->MutableStack.push("c")
s->MutableStack.forEach(Js.log)
Console output:
c
b
a
This is just one possible implementation of a stack in ReScript, and by no means are we forced to use it. There are also other alternatives to this module if we want a stack with different properties:
If we want an immutable stack, we can just use a list and push/pop values from the head.
If we want a stack that is printable/JSON-serializable and interoperable with JavaScript code, we can just use an array and push/pop values from one end.
Mutable Queue
MutableQueue implements a FIFO (first-in first-out) queue data structure. Like MutableStack, updates will mutate the queue in place.
Queues can be initialized empty using make, or initialized from an array using fromArray. The elements in the array will be added to the queue in order. Elements can be added to the queue using add:
open Belt
let q = MutableQueue.make()
let q2 = MutableQueue.fromArray([1, 2, 3, 4, 5])
q->MutableQueue.size->Js.log
q2->MutableQueue.size->Js.log
q->MutableQueue.add(1)
q->MutableQueue.size->Js.log
Console output:
0
5
1
The pop function mutates the queue to remove the first element and returns the element. The peek function returns the first element without removing it from the queue. Similar to mutable stack both of these functions return optional values, although MutableQueue also provides the popExn and peekExn functions, which return unwrapped values but will throw if the queue is empty.
let q = MutableQueue.make()
q->MutableQueue.add("a")
q->MutableQueue.add("b")
q->MutableQueue.add("c")
q->MutableQueue.size->Js.log
q->MutableQueue.popExn->Js.log
q->MutableQueue.size->Js.log
q->MutableQueue.peekExn->Js.log
q->MutableQueue.size->Js.log
Console output:
3
a
2
b
2
The toArrayfunction can be used to convert queues into arrays. The first element in the queue will always be at the beginning of the array, and the last element of the queue will always be at the end of the array:
let q = MutableQueue.make()
q->MutableQueue.add("a")
q->MutableQueue.add("b")
q->MutableQueue.add("c")
q->MutableQueue.toArray->Js.log
Console output:
["a", "b", "c"]
This is useful when we want to print/serialize the contents of the queue, or if we want to use the array standard library to manipulate the contents of the queue. MutableQueue supports operations like forEach, map, and reduce, but the array standard library contains a wider selection.
Mutable Set and Mutable Map
As their name suggests, Belt.MutableSet and Belt.MutableMap are mutable versions of the Belt.Set and Belt.Map modules described earlier in the chapter. Their performance characteristics are very similar – updates and accesses scale logarithmically with the number of elements in the collection.
We can use MutableSet and MutableMap with generic types using a custom comparable module, just like we would for the immutable Set/Map.
The basic APIs of MutableSet/MutableMap are almost identical to those of Set/Map, with the main difference being that update operations modify the collection in place and return unit, instead of returning an updated collection.
Mutable Map Example
To illustrate this difference, we can revisit the luggage example again using a MutableMap. Here, we use Array.forEach to build the map – since updates happen in place, we do not need to pass along the updated map at each iteration like we did using Array.reduce for the immutable version:
let totalLuggagePerPerson = (luggage: array<(string, int)>) => {
open Belt
let weights = MutableMap.String.make()
Array.forEach(luggage, ((person, weight) as item) => {
let curr = weights->MutableMap.String.getWithDefault(person, 0)
HashSets and HashMaps are another way to represent mutable sets and maps in ReScript. The main advantage of using a HashSet/HashMap over other types of sets/maps is performance. Looking up a value in a Map or MutableMap will take longer as the number of mappings increases, while the time to look up a value in a HashMap stays roughly constant no matter how many mappings it contains.
In general, the API for HashSet/HashMap is very similar to the API MutableSet/MutableMap, but there are a few differences which I’ll outline in the following.
Creating a Hash Set/Hash Map
Empty HashSets and HashMaps need to be provided with a “hint size” at creation time, through the ~hintSize named parameter. This can be seen as a rough estimate of how many elements the collection is expected to hold, although it’s only an approximation so we don’t need to worry about getting it exactly right:
let hashSet = Belt.HashSet.Int.make(~hintSize=50)
The hintSize is not required for HashSets and HashMaps initialized from arrays or lists:
let hashSet = Belt.HashSet.Int.fromArray([1, 1, 2, 3])
Accessing Hash Maps
Right now, HashMaps do not offer getWithDefault and getExn functions out of the box, only a get function that returns an optional value. However, we can pipe get into Belt.Option.getWithDefault or Belt.Option.getExn to get the same behaviors.
Hash Map Example
The differences between HashMap and MutableMap creation and access APIs are demonstrated in this version of the luggage example, implemented using a HashMap:
let totalLuggagePerPerson = (luggage: array<(string, int)>) => {
open Belt
let weights = HashMap.String.make(~hintSize=10)
Array.forEach(luggage, ((person, weight) as item) => {
If we are using a custom data type as the key to a HashSet or HashMap, we will have to define a custom hash function for that data type which takes in a value of that type and outputs some integer.
Just like how we made custom comparison modules using Belt.Id.MakeComparable, custom hashing modules are made using Belt.Id.MakeHashable. Here’s a trivial example for integers (in practice, we would use Belt.HashSet.Int):
open Belt
module IntHash = Id.MakeHashable({
type t = int
let hash = x => x
let eq = (a, b) => a == b
})
let hashset = HashSet.make(~hintSize=100, ~id=module(IntHash))
hashset->HashSet.add(1)
hashset->HashSet.add(1)
hashset->HashSet.add(1)
hashset->HashSet.add(2)
hashset->HashSet.size->Js.log
Console output:
2
Ideally, our hashfunction should be written such that two values that are not equal to each other (as defined by eq) will hash to different numbers. For example, if we wanted to make unique hashes for coordinates on a 10x10 grid in battleship, it might look like this:
module CoordHash = Belt.Id.MakeHashable({
type t = (int, int)
let hash = ((x, y)) => 100 * x + y
let eq = (a, b) => a == b
})
The simple hash function defined earlier will give unique hashes as long as the values for each coordinate are between 0 and 99. For example, (0,0) will hash to 0, (9,9) will hash to 909, etc. This is more than adequate for our purposes, since all the coordinate values will be between 0 and 9.
More complex data types can require more complex hash functions, and it’s not always possible to guarantee unique hashes. The important thing to remember is that your hash functions don’t need to be perfect. If two different values hash to the same number (a collision), your hash table will still work, although a bad hash function that causes lots of collisions will degrade performance. If there are constraints on the possible keys, we can use that to simplify the hash function like we did in the previous example.
Beyond the differences involved in defining a comparable and a hashable, usage of generic HashSets and HashMaps is virtually the same as the other set/map APIs.
Here’s the battleship Set example from earlier, reimplemented with a HashSet:
open Belt
module CoordHash = Id.MakeHashable({
type t = (int, int)
let hash = ((x, y)) => 100 * x + y
let eq = (a, b) => a == b
})
let guessed = HashSet.fromArray([(1,1)], ~id=module(CoordHash))
let ships = HashSet.fromArray([(2,2), (2,3), (2,4)], ~id=module(CoordHash))
let checkCoord = ((x, y) as coord, guesses, ships) => {
if HashSet.has(guesses, coord) {
Js.log("already guessed")
} else if HashSet.has(ships, coord) {
Js.log("hit")
} else {
Js.log("miss")
}
}
checkCoord((1, 1), guessed, ships)
checkCoord((0, 0), guessed, ships)
checkCoord((2, 2), guessed, ships)
Console output:
already guessed
miss
hit
Here’s the battleship map example from earlier, reimplemented with a HashMap:
Dicts (dictionaries) are another way to represent key-value pairs in ReScript. Keys must be strings, and values can be any type as long as all the values are the same type.
Like records and objects, dicts are JavaScript objects at runtime. This means that we can safely pass dicts between ReScript code and JavaScript code, making them useful for interoperability. Unlike the other types of maps, we can directly log them with Js.log and serialize them into JSON.
Creating a Dict
Dicts can be created empty, or initialized from an array or list of key-value pairs:
let scores = Js.Dict.empty()
Js.log(scores)
let scores = Js.Dict.fromArray([("Player 1", 100), ("Player 2", 200)])
Js.log(scores)
let scores = Js.Dict.fromList(list{("Player 1", 100), ("Player 2", 200)})
Js.log(scores)
Console output:
{}
{"Player 1": 100, "Player 2": 200}
{"Player 1": 100, "Player 2": 200}
Accessing a Dict
The main access function for dicts is type-safe and returns an option, which can be pattern matched or handled with Belt.Option.getWithDefault or Belt.Option.getExn:
open Belt
let score1 = Js.Dict.get(scores, "Player 1")->Option.getExn
let score2 = Js.Dict.get(scores, "ashdgjasd")->Option.getWithDefault(0)
Js.log2(score1, score2)
Console output:
100 0
Updating a Dict
As previously mentioned, dicts are mutable=:
let scores = Js.Dict.empty()
scores->Js.Dict.set("Player 1", 100)
Js.log(scores)
Console output:
{"Player 1": 100}
Serializing a Dict
Since dicts are just JavaScript objects at runtime, printing and serializing is simple.
We can print them directly using Js.log:
let scores = Js.Dict.fromArray([("Player 1", 100), ("Player 2", 200)])
Js.log(scores)
Console output:
{ "Player 1": 100, "Player 2": 200 }
Assuming the values of the dict also cleanly serialize to JSON, we can use a function like Js.Json.serializeExn to serialize the entire dict to a JSON string:
let scores = Js.Dict.fromArray([("Player 1", 100), ("Player 2", 200)])
let serialized = Js.Json.serializeExn(scores)
Js.log(serialized)
Console output:
'{ "Player 1": 100, "Player 2": 200 }'
If we need to serialize any of the other map types to JSON objects, we can convert them to a Dict. If the original map has something other than strings as keys, we’ll need to convert the keys to strings.
Here’s an example converting Belt.Map.String to Js.Dict:
open Belt
let scores = Map.String.fromArray([("Player 1", 100), ("Player 2", 200)])
let scoresDict = scores->Map.String.toArray->Js.Dict.fromArray
Js.log(scoresDict)
Console output:
{ "Player 1": 100, "Player 2": 200 }
Dicts can also be used to model the shape of objects parsed from JSON, when the number and names of an object’s properties are not predetermined. When the property names are known beforehand, records or objects should be used instead.
In the final chapter, we’ll revisit dicts again when we discuss strategies for parsing and validating JSON payloads.
Which Collection Should I Use?
In this chapter, we covered three different types of sets and four different types of maps available in ReScript’s standard library. For newcomers to the language, it can be confusing to determine which one to use. For many use cases, which collection you choose is entirely up to your own preference, but there are some cases when a specific type of set/map is better than the others.
Let’s start with sets first. The three different types of sets that we covered are Set, MutableSet, and HashSet. Refer to the table at the beginning of the chapter to see a side-by-side comparison.
HashSets should be used for collections that are expected to be very large since they are more performant, while regular Sets offer immutability and ordered keys in exchange for slightly worse performance.
Since Set and MutableSet are implemented as binary trees under the hood, they are actually quite performant, although still not as good as HashSets. Set and MutableSet lookups take logarithmic time based on the size of the set, while HashSets with well-designed hash functions have constant-time lookup regardless of the size of the collection. The caveat here is “well-designed”: if you have a generic HashSet with a bad hash function that leads to tons of collisions, then the performance may be worse than a regular Set!
Here’s a checklist to help determine which type of set to use:
Use Belt.Set if we want immutability or ordering with reasonable performance.
Use Belt.HashSet if we want the best possible performance, we don’t care about the sort order of the values in the set, and the set will contain integers, strings, or a data type that we can write a good hash function for.
If none of the above, use either Belt.Set or Belt.MutableSet.
Next, we’ll discuss maps. The four different types of maps that we covered are Map, MutableMap, HashMap, and Dict. Refer to the table at the beginning of the chapter for a side-by-side comparison.
Dict should be used in situations when we want to easily deserialize or serialize the mapping to JSON or when we need to pass mappings between JavaScript and ReScript. The performance characteristics of Map/MutableMap/HashMap are similar to the performance comparisons I made for Set/MutableSet/HashSet, and as such the guidance for which type of map to use is similar to the guidance for sets.
Here’s a checklist to help determine which type of map to use:
Use Belt.Map if we need immutability or ordered keys.
Use Js.Dict if we need to serialize the data to JSON, we want to pass the data to JavaScript, or the keys are strings.
Use Belt.HashMap if we want the best possible performance, we don’t care about the sort order of the keys in the map, and the keys are integers, strings, or a data type that we can write a good hash function for.
If none of the above, use Belt.Map or Belt.MutableMap.
