pure/Map

Immutable, ordered key-value maps.

The map type is stable whenever the key and value types are stable, allowing map values to be stored in stable variables.

Keys are ordered by an explicit compare function, which must be the same across all operations on a given map.

Example:

import Map "mo:base/pure/Map";
import Nat "mo:base/Nat";

persistent actor {
  // creation
  let empty = Map.empty<Nat, Text>();
  // insertion
  let map1 = Map.add(empty, Nat.compare, 0, "Zero");
  // retrieval
  let null = Map.get(empty, Nat.compare, 0);
  let ?"Zero" = Map.get(map1, Nat.compare, 0);
  // deletion
  let map2 = Map.delete(map1, Nat.compare, 0);
  assert not Map.isEmpty(map1);
  assert Map.isEmpty(map2);
}

The internal representation is a red-black tree.

A red-black tree is a balanced binary search tree ordered by the keys.

The tree data structure internally colors each of its nodes either red or black, and uses this information to balance the tree during the modifying operations.

Performance:

Note:

Credits:

The core of this implementation is derived from:

type Map<K, V> = Types.Pure.Map<K, V>

public func empty<K, V>() : Map<K, V>

Create a new empty immutable key-value map.

Example:

import Map "mo:base/pure/Map";
import Nat "mo:base/Nat";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.empty<Nat, Text>();
  Debug.print(Nat.toText(Map.size(map))); // prints `0`
}

Runtime: O(1). Space: O(1).

public func isEmpty<K, V>(map : Map<K, V>) : Bool

Determines whether a key-value map is empty.

Example:

import Map "mo:base/pure/Map";
import Nat "mo:base/Nat";
import Debug "mo:base/Debug";

persistent actor {
  let map0 = Map.empty<Nat, Text>();
  let map1 = Map.add(map0, Nat.compare, 0, "Zero");

  Debug.print(debug_show(Map.isEmpty(map0))); // prints `true`
  Debug.print(debug_show(Map.isEmpty(map1))); // prints `false`
}

Runtime: O(1). Space: O(1).

public func size<K, V>(map : Map<K, V>) : Nat

Determine the size of the map as the number of key-value entries.

Example:

import Map "mo:base/pure/Map";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

let map = Map.fromIter<Nat, Text>(Iter.fromArray([(0, "Zero"), (2, "Two"), (1, "One")]), Nat.compare);

Debug.print(debug_show(Map.size(map)));
// 3

Runtime: O(n). Space: O(1).

public func containsKey<K, V>(
  map : Map<K, V>,
  compare : (K, K) -> Order.Order,
  key : K
) : Bool

Test whether the map map, ordered by compare, contains a binding for the given key.

Example:

import Map "mo:base/pure/Map";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.fromIter<Nat, Text>(Iter.fromArray([(0, "Zero"), (2, "Two"), (1, "One")]), Nat.compare);

  Debug.print(debug_show Map.containsKey(map, Nat.compare, 1)); // => true
  Debug.print(debug_show Map.containsKey(map, Nat.compare, 42)); // => false
}

Runtime: O(log(n)). Space: O(1). where n denotes the number of key-value entries stored in the map and assuming that the compare function implements an O(1) comparison.

public func get<K, V>(
  map : Map<K, V>,
  compare : (K, K) -> Order.Order,
  key : K
) : ?V

Given, map ordered by compare, return the value associated with key key if present and null otherwise.

Example:

import Map "mo:base/pure/Map";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.fromIter<Nat, Text>(Iter.fromArray([(0, "Zero"), (2, "Two"), (1, "One")]), Nat.compare);

  Debug.print(debug_show(Map.get(map, Nat.compare, 1)));
  // ?"One"
  Debug.print(debug_show(Map.get(map, Nat.compare, 42)));
  // null
}

Runtime: O(log(n)). Space: O(1). where n denotes the number of key-value entries stored in the map and assuming that the compare function implements an O(1) comparison.

public func insert<K, V>(
  map : Map<K, V>,
  compare : (K, K) -> Order.Order,
  key : K,
  value : V
) : (Map<K, V>, Bool)

Given map ordered by compare, insert a mapping from key to value. Returns the modified map and true if the key is new to map, otherwise false.

Example:

import Map "mo:base/pure/Map";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.empty<Nat, Text>();

  let (map0, true) = Map.insert(map, Nat.compare, 0, "Zero");
  let (map1, true) = Map.insert(map0, Nat.compare, 1, "One");
  Debug.print(debug_show(Iter.toArray(Map.entries(map1))));
  // [(0, "Zero"), (1, "One")]
  let (map2, false) = Map.insert(map1, Nat.compare, 0, "Nil");
  Debug.print(debug_show(Iter.toArray(Map.entries(map2))));
  // [(0, "Nil"), (1, "One")]

}

Runtime: O(log(n)). Space: O(log(n)). where n denotes the number of key-value entries stored in the map and assuming that the compare function implements an O(1) comparison.

Note: The returned map shares with the m most of the tree nodes. Garbage collecting one of maps (e.g. after an assignment m := Map.add(m, cmp, k, v)) causes collecting O(log(n)) nodes.

public func add<K, V>(
  map : Map<K, V>,
  compare : (K, K) -> Order.Order,
  key : K,
  value : V
) : Map<K, V>

Given map ordered by compare, add a new mapping from key to value. Replaces any existing entry with key key. Returns the modified map.

Example:

import Map "mo:base/pure/Map";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

persistent actor {
  var map = Map.empty<Nat, Text>();

  map := Map.add(map, Nat.compare, 0, "Zero");
  map := Map.add(map, Nat.compare, 1, "One");
  map := Map.add(map, Nat.compare, 0, "Nil");

  Debug.print(debug_show(Iter.toArray(Map.entries(map))));
  // [(0, "Nil"), (1, "One")]
}

Runtime: O(log(n)). Space: O(log(n)). where n denotes the number of key-value entries stored in the map and assuming that the compare function implements an O(1) comparison.

Note: The returned map shares with the m most of the tree nodes. Garbage collecting one of maps (e.g. after an assignment m := Map.add(m, cmp, k, v)) causes collecting O(log(n)) nodes.

public func swap<K, V>(
  map : Map<K, V>,
  compare : (K, K) -> Order.Order,
  key : K,
  value : V
) : (Map<K, V>, ?V)

Given map ordered by compare, add a mapping from key to value. Overwrites any existing entry with key key. Returns the modified map and the previous value associated with key key or null if no such value exists.

Example:

import Map "mo:base/pure/Map";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

persistent actor {
  let map0 = Map.fromIter<Nat, Text>(
    Iter.fromArray([(0, "Zero"), (2, "Two"), (1, "One")]),
    Nat.compare);

  let (map1, old1) = Map.swap(map0, Nat.compare, 0, "Nil");

  Debug.print(debug_show(Iter.toArray(Map.entries(map1))));
  Debug.print(debug_show(old1));
  // [(0, "Nil"), (1, "One"), (2, "Two")]
  // ?"Zero"

  let (map2, old2) = Map.swap(map0, Nat.compare, 3, "Three");

  Debug.print(debug_show(Iter.toArray(Map.entries(map2))));
  Debug.print(debug_show(old2));
  // [(0, "Zero"), (1, "One"), (2, "Two"), (3, "Three")]
  // null
}

Runtime: O(log(n)). Space: O(log(n)) retained memory plus garbage, see the note below. where n denotes the number of key-value entries stored in the map and assuming that the compare function implements an O(1) comparison.

Note: The returned map shares with the m most of the tree nodes. Garbage collecting one of maps (e.g. after an assignment m := Map.swap(m, Nat.compare, k, v).0) causes collecting O(log(n)) nodes.

public func replaceIfExists<K, V>(
  map : Map<K, V>,
  compare : (K, K) -> Order.Order,
  key : K,
  value : V
) : (Map<K, V>, ?V)

Overwrites the value of an existing key and returns the updated map and previous value. If the key does not exist, returns the original map and null.

Example:

import Map "mo:base/pure/Map";
import Nat "mo:base/Nat";
import Debug "mo:base/Debug";

persistent actor {
  let singleton = Map.singleton(0, "Null");

  let (map1, oldZero) = Map.replaceIfExists(singleton, Nat.compare, 0, "Zero"); // overwrites the value for existing key.
  Debug.print(debug_show(oldZero)); // prints `?"Null"`, previous value.
  Debug.print(debug_show(Map.get(map1, Nat.compare, 0))); // prints `?"Zero"`, new value.
  let empty = Map.empty<Nat, Text>();
  let (map2, oldOne) = Map.replaceIfExists(empty, Nat.compare, 1, "One");  // no effect, key is absent
  Debug.print(debug_show(oldOne)); // prints `null`, key was absent.
  Debug.print(debug_show(Map.get(map2, Nat.compare, 0))); // prints `null`
}

Runtime: O(log(n)). Space: O(log(n)). where n denotes the number of key-value entries stored in the map and assuming that the compare function implements an O(1) comparison.

public func remove<K, V>(
  map : Map<K, V>,
  compare : (K, K) -> Order.Order,
  key : K
) : Map<K, V>

Given a map, ordered by compare, deletes any entry for key from map. Has no effect if key is not present in the map. Returns the updated map.

Example:

import Map "mo:base/pure/Map";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.fromIter<Nat, Text>(Iter.fromArray([(0, "Zero"), (2, "Two"), (1, "One")]), Nat.compare);

  let map1 = Map.remove(map, Nat.compare, 1);
  Debug.print(debug_show(Iter.toArray(Map.entries(map1))));
  // [(0, "Zero"), (2, "Two")]
  let map2 = Map.remove(map0, Nat.compare, 42))
  Debug.print(debug_show(Iter.toArray(Map.entries(map2))));
  // [(0, "Zero"), (1, "One"), (2, "Two")]
}

Runtime: O(log(n)). Space: O(log(n)) where n denotes the number of key-value entries stored in the map and assuming that the compare function implements an O(1) comparison.

Note: The returned map shares with the m most of the tree nodes. Garbage collecting one of maps (e.g. after an assignment map := Map.delete(map, compare, k).0) causes collecting O(log(n)) nodes.

public func delete<K, V>(
  map : Map<K, V>,
  compare : (K, K) -> Order.Order,
  key : K
) : (Map<K, V>, Bool)

Given a map, ordered by compare, deletes any entry for key from map. Has no effect if key is not present in the map. Returns the updated map and true if the key was present in map, otherwise false.

Example:

import Map "mo:base/pure/Map";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.fromIter<Nat, Text>(Iter.fromArray([(0, "Zero"), (2, "Two"), (1, "One")]), Nat.compare);

  let (map1, true) = Map.delete(map, Nat.compare, 1);
  Debug.print(debug_show(Iter.toArray(Map.entries(map1))));
  // [(0, "Zero"), (2, "Two")]
  let (map2, false) = Map.delete(map0, Nat.compare, 42))
  Debug.print(debug_show(Iter.toArray(Map.entries(map2))));
  // [(0, "Zero"), (1, "One"), (2, "Two")]
}

Runtime: O(log(n)). Space: O(log(n)) where n denotes the number of key-value entries stored in the map and assuming that the compare function implements an O(1) comparison.

Note: The returned map shares with the m most of the tree nodes. Garbage collecting one of maps (e.g. after an assignment map := Map.delete(map, compare, k).0) causes collecting O(log(n)) nodes.

public func take<K, V>(
  map : Map<K, V>,
  compare : (K, K) -> Order.Order,
  key : K
) : (Map<K, V>, ?V)

Given a map, ordered by compare, deletes the entry for key. Returns a modified map, leaving map unchanged, and the previous value associated with key or null if no such value exists.

Example:

import Map "mo:base/pure/Map";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

persistent actor {
  let map0 = Map.fromIter<Nat, Text>(Iter.fromArray([(0, "Zero"), (2, "Two"), (1, "One")]), Nat.compare);

  let (map1, old1) = Map.take(map0, Nat.compare, 0);

  Debug.print(debug_show(Iter.toArray(Map.entries(map1))));
  Debug.print(debug_show(old1));
  // [(1, "One"), (2, "Two")]
  // ?"Zero"

  let (map2, old2) = Map.take(map0, Nat.compare, 42);

  Debug.print(debug_show(Iter.toArray(Map.entries(map2))));
  Debug.print(debug_show(old2));
  // [(0, "Zero"), (1, "One"), (2, "Two")]
  // null
}

Runtime: O(log(n)). Space: O(log(n)). where n denotes the number of key-value entries stored in the map and assuming that the compare function implements an O(1) comparison.

Note: The returned map shares with the m most of the tree nodes. Garbage collecting one of maps (e.g. after an assignment map := Map.remove(map, compare, key)) causes collecting O(log(n)) nodes.

public func maxEntry<K, V>(map : Map<K, V>) : ?(K, V)

Given a map retrieves the key-value pair in map with a maximal key. If map is empty returns null.

Example:

import Map "mo:base/pure/Map";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.fromIter<Nat, Text>(Iter.fromArray([(0, "Zero"), (2, "Two"), (1, "One")]), Nat.compare);

  Debug.print(debug_show(Map.maxEntry(map)));
  Debug.print(debug_show(Map.maxEntry(Map.empty<Nat, Text>())));
  // null
}

Runtime: O(log(n)). Space: O(1). where n denotes the number of key-value entries stored in the map.

public func minEntry<K, V>(map : Map<K, V>) : ?(K, V)

Retrieves a key-value pair from map with the minimal key. If the map is empty returns null.

Example:

import Map "mo:base/pure/Map";
import Iter "mo:base/Iter";
import Nat "mo:base/Nat";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.fromIter<Nat, Text>(Iter.fromArray([(0, "Zero"), (2, "Two"), (1, "One")]), Nat.compare);

  Debug.print(debug_show(Map.minEntry(map)));
  // ?(0, "Zero")
  Debug.print(debug_show(Map.minEntry(Map.empty())));
   // => null
}

Runtime: O(log(n)). Space: O(1). where n denotes the number of key-value entries stored in the map.

public func entries<K, V>(map : Map<K, V>) : Iter.Iter<(K, V)>

Returns an Iterator (Iter) over the key-value pairs in the map. Iterator provides a single method next(), which returns pairs in ascending order by keys, or null when out of pairs to iterate over.

Example:

import Map "mo:base/pure/Map";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.fromIter<Nat, Text>(Iter.fromArray([(0, "Zero"), (2, "Two"), (1, "One")]), Nat.compare);

  Debug.print(debug_show(Iter.toArray(Map.entries(map))));
  // [(0, "Zero"), (1, "One"), (2, "Two")]
  var sum = 0;
  for ((k, _) in Map.entries(map)) { sum += k; };
  Debug.print(debug_show(sum));
  // 3
}

Cost of iteration over all elements: Runtime: O(n). Space: O(log(n)) retained memory plus garbage, see the note below. where n denotes the number of key-value entries stored in the map.

Note: Full map iteration creates O(n) temporary objects that will be collected as garbage.

public func reverseEntries<K, V>(map : Map<K, V>) : Iter.Iter<(K, V)>

Same as entries but iterates in descending order.

public func keys<K, V>(map : Map<K, V>) : Iter.Iter<K>

Given a map, returns an Iterator (Iter) over the keys of the map. Iterator provides a single method next(), which returns keys in ascending order, or null when out of keys to iterate over.

Example:

import Map "mo:base/pure/Map";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.fromIter<Nat, Text>(
    Iter.fromArray([(0, "Zero"), (2, "Two"), (1, "One")]),
  Nat.compare);

  Debug.print(debug_show(Iter.toArray(Map.keys(map))));
  // [0, 1, 2]
}

Cost of iteration over all elements: Runtime: O(n). Space: O(log(n)) retained memory plus garbage, see the note below. where n denotes the number of key-value entries stored in the map.

Note: Full map iteration creates O(n) temporary objects that will be collected as garbage.

public func values<K, V>(map : Map<K, V>) : Iter.Iter<V>

Given a map, returns an Iterator (Iter) over the values of the map. Iterator provides a single method next(), which returns values in ascending order of associated keys, or null when out of values to iterate over.

Example:

import Map "mo:base/pure/Map";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

persistent actor {
let map = Map.fromIter<Nat, Text>(
  Iter.fromArray([(0, "Zero"), (2, "Two"), (1, "One")]),
  Nat.compare);

  Debug.print(debug_show(Iter.toArray(Map.values(map))));
  // ["Zero", "One", "Two"]
}

Cost of iteration over all elements: Runtime: O(n). Space: O(log(n)) retained memory plus garbage, see the note below. where n denotes the number of key-value entries stored in the map.

Note: Full map iteration creates O(n) temporary objects that will be collected as garbage.

public func fromIter<K, V>(iter : Iter.Iter<(K, V)>, compare : (K, K) -> Order.Order) : Map<K, V>

Returns a new map, containing all entries given by the iterator i. If there are multiple entries with the same key the last one is taken.

Example:

import Map "mo:base/pure/Map";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.fromIter<Nat, Text>(Iter.fromArray([(0, "Zero"), (2, "Two"), (1, "One")]), Nat.compare);

  Debug.print(debug_show(Iter.toArray(Map.entries(map))));
  // [(0, "Zero"), (1, "One"), (2, "Two")]
}

Runtime: O(n * log(n)). Space: O(n) retained memory plus garbage, see the note below. where n denotes the number of key-value entries stored in the map and assuming that the compare function implements an O(1) comparison.

Note: Creates O(n * log(n)) temporary objects that will be collected as garbage.

public func map<K, V1, V2>(map : Map<K, V1>, f : (K, V1) -> V2) : Map<K, V2>

Given a map and function f, creates a new map by applying f to each entry in the map m. Each entry (k, v) in the old map is transformed into a new entry (k, v2), where the new value v2 is created by applying f to (k, v).

Example:

import Map "mo:base/pure/Map";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.fromIter<Nat, Text>(
    Iter.fromArray([(0, "Zero"), (2, "Two"), (1, "One")]),
    Nat.compare);

  func f(key : Nat, _val : Text) : Nat = key * 2;

  let resMap = Map.map(map, f);

  Debug.print(debug_show(Iter.toArray(Map.entries(resMap))));
  // [(0, 0), (1, 2), (2, 4)]
}

Cost of mapping all the elements: Runtime: O(n). Space: O(n) retained memory where n denotes the number of key-value entries stored in the map.

public func foldLeft<K, V, A>(
  map : Map<K, V>,
  base : A,
  combine : (A, K, V) -> A
) : A

Collapses the elements in the map into a single value by starting with base and progressively combining keys and values into base with combine. Iteration runs left to right.

Example:

import Map "mo:base/pure/Map";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.fromIter<Nat, Text>(Iter.fromArray([(0, "Zero"), (2, "Two"), (1, "One")]), Nat.compare);

  func folder(accum : (Nat, Text), key : Nat, val : Text) : ((Nat, Text))
    = (key + accum.0, accum.1 # val);

  Debug.print(debug_show(Map.foldLeft(map, (0, ""), folder)));
  // (3, "ZeroOneTwo")
}

Cost of iteration over all elements: Runtime: O(n). Space: depends on combine function plus garbage, see the note below. where n denotes the number of key-value entries stored in the map.

Note: Full map iteration creates O(n) temporary objects that will be collected as garbage.

public func foldRight<K, V, A>(
  map : Map<K, V>,
  base : A,
  combine : (K, V, A) -> A
) : A

Collapses the elements in the map into a single value by starting with base and progressively combining keys and values into base with combine. Iteration runs right to left.

Example:

import Map "mo:base/pure/Map";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.fromIter<Nat, Text>(
    Iter.fromArray([(0, "Zero"), (2, "Two"), (1, "One")]),
    Nat.compare);

  func folder(key : Nat, val : Text, accum : (Nat, Text)) : ((Nat, Text))
    = (key + accum.0, accum.1 # val);

  Debug.print(debug_show(Map.foldRight(map, (0, ""), folder)));
  // (3, "TwoOneZero")
}

Cost of iteration over all elements: Runtime: O(n). Space: depends on combine function plus garbage, see the note below. where n denotes the number of key-value entries stored in the map.

Note: Full map iteration creates O(n) temporary objects that will be collected as garbage.

public func all<K, V>(map : Map<K, V>, pred : (K, V) -> Bool) : Bool

Test whether all key-value pairs in map satisfy the given predicate pred.

Example:

import Map "mo:base/pure/Map";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.fromIter<Nat, Text>(
    Iter.fromArray([(0, "0"), (2, "2"), (1, "1")]),
    Nat.compare);

  Debug.print(debug_show(Map.all<Text>(map, func (k, v) = (v == debug_show(k)))));
  // true
  Debug.print(debug_show(Map.all<Text>(map, func (k, v) = (k < 2))));
  // false
}

Runtime: O(n). Space: O(1). where n denotes the number of key-value entries stored in the map.

public func any<K, V>(map : Map<K, V>, pred : (K, V) -> Bool) : Bool

Test if any key-value pair in map satisfies the given predicate pred.

Example:

import Map "mo:base/pure/Map";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.fromIter<Nat, Text>(
    Iter.fromArray([(0, "0"), (2, "2"), (1, "1")]),
    Nat.compare);

  Debug.print(debug_show(Map.any<Text>(map, func (k, v) = (k >= 3))));
  // false
  Debug.print(debug_show(Map.any<Text>(map, func (k, v) = (k >= 0))));
  // true
}

Runtime: O(n). Space: O(1). where n denotes the number of key-value entries stored in the map.

public func singleton<K, V>(key : K, value : V) : Map<K, V>

Create a new immutable key-value map with a single entry.

Example:

import Map "mo:base/pure/Map";
import Debug "mo:base/Debug";

persistent actor {
  let cityCodes = Map.singleton<Text, Nat>("Zurich", 8000);
  Debug.print(debug_show(Map.size(cityCodes)));
  // 1
}

Runtime: O(1). Space: O(1).

public func forEach<K, V>(map : Map<K, V>, operation : (K, V) -> ())

Apply an operation for each key-value pair contained in the map. The operation is applied in ascending order of the keys.

Example:

import Map "mo:base/pure/Map";
import Nat "mo:base/Nat";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.fromIter<Nat, Text>(
    Iter.fromArray([(0, "Zero"), (2, "Two"), (1, "One")]),
    Nat.compare);
  Map.forEach<Nat, Text>(map, func (key, value) {
    Debug.print("key=" # Nat.toText(key) # ", value='" # value # "'");
  })
}

Runtime: O(n). Space: O(1) retained memory plus garbage, see below. where n denotes the number of key-value entries stored in the map.

public func filter<K, V>(
  map : Map<K, V>,
  compare : (K, K) -> Order.Order,
  criterion : (K, V) -> Bool
) : Map<K, V>

Filter entries in a new map. Returns a new map that only contains the key-value pairs that fulfil the criterion function.

Example:

import Map "mo:base/pure/Map";
import Nat "mo:base/Nat";

persistent actor {
  let numberNames = Map.fromIter<Nat, Text>(Iter.fromArray([(0, "Zero"), (2, "Two"), (1, "One")]), Nat.compare);
  let evenNames = Map.filter<Nat, Text>(numberNames, Nat.compare, func (key, value) {
    key % 2 == 0
  });
}

Runtime: O(n). Space: O(n). where n denotes the number of key-value entries stored in the map and assuming that the compare function implements an O(1) comparison.

public func filterMap<K, V1, V2>(
  map : Map<K, V1>,
  compare : (K, K) -> Order.Order,
  f : (K, V1) -> ?V2
) : Map<K, V2>

Given a map, comparison compare and function f, constructs a new map ordered by compare, by applying f to each entry in map. For each entry (k, v) in the old map, if f evaluates to null, the entry is discarded. Otherwise, the entry is transformed into a new entry (k, v2), where the new value v2 is the result of applying f to (k, v).

Example:

import Map "mo:base/pure/Map";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.fromIter<Nat, Text>(
    Iter.fromArray([(0, "Zero"), (2, "Two"), (1, "One")]),
    Nat.compare);

  func f(key : Nat, val : Text) : ?Text {
    if(key == 0) {null}
    else { ?("Twenty " # val)}
  };

  let newMap = Map.filterMap(map, Nat.compare, f);

  Debug.print(debug_show(Iter.toArray(Map.entries(newMap))));
  // [(1, "Twenty One"), (2, "Twenty Two")]
}

Runtime: O(n * log(n)). Space: O(n) retained memory plus garbage, see the note below. where n denotes the number of key-value entries stored in the map and assuming that the compare function implements an O(1) comparison.

Note: Creates O(n * log(n)) temporary objects that will be collected as garbage.

public func assertValid<K, V>(map : Map<K, V>, compare : (K, K) -> Order.Order) : ()

Validate the representation invariants of the given map. Assert if any invariants are violated.

public func toText<K, V>(
  map : Map<K, V>,
  keyFormat : K -> Text,
  valueFormat : V -> Text
) : Text

Converts the map to its textual representation using keyFormat and valueFormat to convert each key and value to Text.

import Map "mo:base/pure/Map";
import Nat "mo:base/Nat";

persistent actor {
  let map = Map.fromIter<Nat, Text>(
    Iter.fromArray([(0, "Zero"), (2, "Two"), (1, "One")]),
    Nat.compare);
  Map.toText<Nat, Text>(map, Nat.toText, func t { t })
   // => "{(0, Zero), (1, One), (2, Two)}"
}

Runtime: O(size)

Space: O(size)

*Runtime and space assumes that keyFormat and valueFormat run in O(1) time and space.

public func equal<K, V>(
  map1 : Map<K, V>,
  map2 : Map<K, V>,
  compareKey : (K, K) -> Order.Order,
  equalValue : (V, V) -> Bool
) : Bool

Test whether two immutable maps have equal entries. Assumes both maps are ordered equivalently.

Example:

import Map "mo:base/pure/Map";
import Nat "mo:base/Nat";
import Debug "mo:base/Debug";
import Text "mo:base/Text";

persistent actor {
  let map1 = Map.fromIter<Nat, Text>(
    Iter.fromArray([(0, "Zero"), (1, "One"), (2, "Two")]),
    Nat.compare);
  let map2 = Map.fromIter<Nat, Text>(
    Iter.fromArray([(2, "Two"), (1, "One"), (0, "Zero")]),
    Nat.compare);
  assert(Map.equal(map1, map2, Nat.compare, Text.equal));
}

Runtime: O(n). Space: O(1).

public func compare<K, V>(
  map1 : Map<K, V>,
  map2 : Map<K, V>,
  compareKey : (K, K) -> Order.Order,
  compareValue : (V, V) -> Order.Order
) : Order.Order

Compare two maps by primarily comparing keys and secondarily values. Both maps are iterated by the ascending order of their creation and order is determined by the following rules: Less: map1 is less than map2 if:

Example:

import Map "mo:base/pure/Map";
import Nat "mo:base/Nat";
import Text "mo:base/Text";

persistent actor {
  let map1 = Map.fromIter<Nat, Text>(
    Iter.fromArray([(0, "Zero"), (1, "One")]),
    Nat.compare);
  let map2 = Map.fromIter<Nat, Text>(
    Iter.fromArray([(0, "Zero"), (2, "Two")]),
    Nat.compare);

  let orderLess = Map.compare(map1, map2, Nat.compare, Text.compare);
  // `#less`
  let orderEqual = Map.compare(map1, map1, Nat.compare, Text.compare);
  // `#equal`
  let orderGreater = Map.compare(map2, map1, Nat.compare, Text.compare);
  // `#greater`
}

Runtime: O(n). Space: O(1) retained memory plus garbage, see below. where n denotes the number of key-value entries stored in the map and assuming that compareKey and compareValue have runtime and space costs of O(1).

Note: Creates O(log(n)) temporary objects that will be collected as garbage.