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 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: 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 entry
map := 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 difference
let 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 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: 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 them
let 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.