AssocList

Map implemented as a linked-list of key-value pairs ("Associations").

NOTE: This map implementation is mainly used as underlying buckets for other map structures. Thus, other map implementations are easier to use in most cases.

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 mapmap := 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 1AssocList.find(map, 1, Nat.equal)``

Runtime: O(size)

Space: O(1)

*Runtime and space assumes that `equal` runs in O(1) time and space.

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 entrymap := AssocList.replace(map, 1, Nat.equal, ?21).0;List.toArray(map)``

Runtime: O(size)

Space: O(size)

*Runtime and space assumes that `equal` runs in O(1) time and space.

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 differencelet newMap = AssocList.diff(map1, map2, Nat.equal);List.toArray(newMap)``

Runtime: O(size1 * size2)

Space: O(1)

*Runtime and space assumes that `equal` runs in O(1) time and space.

Function `mapAppend`​

``func mapAppend<K, V, W, X>(map1 : AssocList<K, V>, map2 : AssocList<K, W>, f : (?V, ?W) -> X) : AssocList<K, X>``

@deprecated

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 AssocListslet 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: O(size1 + size2)

Space: O(1)

*Runtime and space assumes that `f` runs in O(1) time and space.

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.

NOTE: `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: O(size1 * size2)

Space: O(size1 + size2)

*Runtime and space assumes that `equal` and `combine` runs in O(1) time and space.

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 themlet newMap = AssocList.join<Nat, Nat, Nat, Nat>(map1, map2, Nat.equal, Nat.add);List.toArray(newMap)``

Runtime: O(size1 * size2)

Space: O(size1 + size2)

*Runtime and space assumes that `equal` and `combine` runs in O(1) time and space.

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: O(size)

Space: O(size)

*Runtime and space assumes that `combine` runs in O(1) time and space.