AssocList

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

Usage context

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.

Assumptions

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>

Deprecated function

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.

Behavior guarantee

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)`

AssocList

Type AssocList​

Function find​

Function replace​

Function diff​

Function mapAppend​

Function disjDisjoint​

Function disj​

Function join​

Function fold​

Type `AssocList`

Function `find`

Function `replace`

Function `diff`

Function `mapAppend`

Function `disjDisjoint`

Function `disj`

Function `join`

Function `fold`