AssocList
Map implemented as a linked-list of key-value pairs ("Associations").
This map implementation primarily serves as the underlying bucket structure for other map types. In most cases, those higher-level map implementations are easier to use.
Runtime and space complexity assumes that combine
, equal
, and other functions execute in O(1)
time and space.
Type AssocList
type AssocList<K, V> = List.List<(K, V)>
Import from the base library to use this module.
import AssocList "mo:base/AssocList";
import List "mo:base/List";
import Nat "mo:base/Nat";
type AssocList<K, V> = AssocList.AssocList<K, V>;
Initialize an empty map using an empty list.
var map : AssocList<Nat, Nat> = List.nil(); // Empty list as an empty map
map := null; // Alternative: null as empty list.
map
Function find
func find<K, V>(map : AssocList<K, V>, key : K, equal : (K, K) -> Bool) : ?V
Find the value associated with key key
, or null
if no such key exists.
Compares keys using the provided function equal
.
Example:
// Create map = [(0, 10), (1, 11), (2, 12)]
map := AssocList.replace(map, 0, Nat.equal, ?10).0;
map := AssocList.replace(map, 1, Nat.equal, ?11).0;
map := AssocList.replace(map, 2, Nat.equal, ?12).0;
// Find value associated with key 1
AssocList.find(map, 1, Nat.equal)
Runtime | Space |
---|---|
O(size) | O(1) |
Function replace
func replace<K, V>(map : AssocList<K, V>, key : K, equal : (K, K) -> Bool, value : ?V) : (AssocList<K, V>, ?V)
Maps key
to value
in map
, and overwrites the old entry if the key
was already present. Returns the old value in an option if it existed and
null
otherwise, as well as the new map. Compares keys using the provided
function equal
.
Example:
// Add three entries to the map
// map = [(0, 10), (1, 11), (2, 12)]
map := AssocList.replace(map, 0, Nat.equal, ?10).0;
map := AssocList.replace(map, 1, Nat.equal, ?11).0;
map := AssocList.replace(map, 2, Nat.equal, ?12).0;
// Override second entry
map := AssocList.replace(map, 1, Nat.equal, ?21).0;
List.toArray(map)
Runtime | Space |
---|---|
O(size) | O(size) |
Function diff
func diff<K, V, W>(map1 : AssocList<K, V>, map2 : AssocList<K, W>, equal : (K, K) -> Bool) : AssocList<K, V>
Produces a new map containing all entries from map1
whose keys are not
contained in map2
. The "extra" entries in map2
are ignored. Compares
keys using the provided function equal
.
Example:
// Create map1 = [(0, 10), (1, 11), (2, 12)]
var map1 : AssocList<Nat, Nat> = null;
map1 := AssocList.replace(map1, 0, Nat.equal, ?10).0;
map1 := AssocList.replace(map1, 1, Nat.equal, ?11).0;
map1 := AssocList.replace(map1, 2, Nat.equal, ?12).0;
// Create map2 = [(2, 12), (3, 13)]
var map2 : AssocList<Nat, Nat> = null;
map2 := AssocList.replace(map2, 2, Nat.equal, ?12).0;
map2 := AssocList.replace(map2, 3, Nat.equal, ?13).0;
// Take the difference
let newMap = AssocList.diff(map1, map2, Nat.equal);
List.toArray(newMap)
Runtime | Space |
---|---|
O(size1 * size2) | O(1) |
Function mapAppend
func mapAppend<K, V, W, X>(map1 : AssocList<K, V>, map2 : AssocList<K, W>, f : (?V, ?W) -> X) : AssocList<K, X>
mapAppend
is deprecated and may be removed in future versions. Consider using an alternative approach.
Function disjDisjoint
func disjDisjoint<K, V, W, X>(map1 : AssocList<K, V>, map2 : AssocList<K, W>, f : (?V, ?W) -> X) : AssocList<K, X>
Produces a new map by mapping entries in map1
and map2
using f
and
concatenating the results. Assumes that there are no collisions between
keys in map1
and map2
.
Example:
import { trap } "mo:base/Debug";
// Create map1 = [(0, 10), (1, 11), (2, 12)]
var map1 : AssocList<Nat, Nat> = null;
map1 := AssocList.replace(map1, 0, Nat.equal, ?10).0;
map1 := AssocList.replace(map1, 1, Nat.equal, ?11).0;
map1 := AssocList.replace(map1, 2, Nat.equal, ?12).0;
// Create map2 = [(4, "14"), (3, "13")]
var map2 : AssocList<Nat, Text> = null;
map2 := AssocList.replace(map2, 4, Nat.equal, ?"14").0;
map2 := AssocList.replace(map2, 3, Nat.equal, ?"13").0;
// Map and append the two AssocLists
let newMap =
AssocList.disjDisjoint<Nat, Nat, Text, Text>(
map1,
map2,
func((v1, v2) : (?Nat, ?Text)) {
switch(v1, v2) {
case(?v1, null) {
debug_show(v1) // convert values from map1 to Text
};
case(null, ?v2) {
v2 // keep values from map2 as Text
};
case _ {
trap "These cases will never happen in mapAppend"
}
}
}
);
List.toArray(newMap)
Runtime | Space |
---|---|
O(size1 + size2) | O(size1 + size2) |
Function disj
func disj<K, V, W, X>(map1 : AssocList<K, V>, map2 : AssocList<K, W>, equal : (K, K) -> Bool, combine : (?V, ?W) -> X) : AssocList<K, X>
Creates a new map by merging entries from map1
and map2
, and mapping
them using combine
. combine
is also used to combine the values of colliding keys.
Keys are compared using the given equal
function.
combine
will never be applied to (null, null)
.
Example:
import { trap } "mo:base/Debug";
// Create map1 = [(0, 10), (1, 11), (2, 12)]
var map1 : AssocList<Nat, Nat> = null;
map1 := AssocList.replace(map1, 0, Nat.equal, ?10).0;
map1 := AssocList.replace(map1, 1, Nat.equal, ?11).0;
map1 := AssocList.replace(map1, 2, Nat.equal, ?12).0;
// Create map2 = [(2, 12), (3, 13)]
var map2 : AssocList<Nat, Nat> = null;
map2 := AssocList.replace(map2, 2, Nat.equal, ?12).0;
map2 := AssocList.replace(map2, 3, Nat.equal, ?13).0;
// Merge the two maps using `combine`
let newMap =
AssocList.disj<Nat, Nat, Nat, Nat>(
map1,
map2,
Nat.equal,
func((v1, v2) : (?Nat, ?Nat)) : Nat {
switch(v1, v2) {
case(?v1, ?v2) {
v1 + v2 // combine values of colliding keys by adding them
};
case(?v1, null) {
v1 // when a key doesn't collide, keep the original value
};
case(null, ?v2) {
v2
};
case _ {
trap "This case will never happen in disj"
}
}
}
);
List.toArray(newMap)
Runtime | Space |
---|---|
O(size1 * size2) | O(size1 + size2) |
Function join
func join<K, V, W, X>(map1 : AssocList<K, V>, map2 : AssocList<K, W>, equal : (K, K) -> Bool, combine : (V, W) -> X) : AssocList<K, X>
Takes the intersection of map1
and map2
, only keeping colliding keys
and combining values using the combine
function. Keys are compared using
the equal
function.
Example:
// Create map1 = [(0, 10), (1, 11), (2, 12)]
var map1 : AssocList<Nat, Nat> = null;
map1 := AssocList.replace(map1, 0, Nat.equal, ?10).0;
map1 := AssocList.replace(map1, 1, Nat.equal, ?11).0;
map1 := AssocList.replace(map1, 2, Nat.equal, ?12).0;
// Create map2 = [(2, 12), (3, 13)]
var map2 : AssocList<Nat, Nat> = null;
map2 := AssocList.replace(map2, 2, Nat.equal, ?12).0;
map2 := AssocList.replace(map2, 3, Nat.equal, ?13).0;
// Take the intersection of the two maps, combining values by adding them
let newMap = AssocList.join<Nat, Nat, Nat, Nat>(map1, map2, Nat.equal, Nat.add);
List.toArray(newMap)
Runtime | Space |
---|---|
O(size1 * size2) | O(size1 + size2) |
Function fold
func fold<K, V, X>(map : AssocList<K, V>, base : X, combine : (K, V, X) -> X) : X
Collapses the elements in map
into a single value by starting with base
and progessively combining elements into base
with combine
. Iteration runs
left to right.
Example:
// Create map = [(0, 10), (1, 11), (2, 12)]
var map : AssocList<Nat, Nat> = null;
map := AssocList.replace(map, 0, Nat.equal, ?10).0;
map := AssocList.replace(map, 1, Nat.equal, ?11).0;
map := AssocList.replace(map, 2, Nat.equal, ?12).0;
// (0 * 10) + (1 * 11) + (2 * 12)
AssocList.fold<Nat, Nat, Nat>(map, 0, func(k, v, sumSoFar) = (k * v) + sumSoFar)
Runtime | Space |
---|---|
O(size) | O(size) |