Skip to main content

core/Map

An imperative key-value map based on order/comparison of the keys. The map data structure type is stable and can be used for orthogonal persistence.

Example:

import Map "mo:core/Map";
import Nat "mo:core/Nat";

persistent actor {
  // creation
  let map = Map.empty<Nat, Text>();
  // insertion
  Map.add(map, Nat.compare, 0, "Zero");
  // retrieval
  assert Map.get(map, Nat.compare, 0) == ?"Zero";
  assert Map.get(map, Nat.compare, 1) == null;
  // removal
  Map.remove(map, Nat.compare, 0);
  assert Map.isEmpty(map);
}

The internal implementation is a B-tree with order 32.

Performance:

  • Runtime: O(log(n)) worst case cost per insertion, removal, and retrieval operation.
  • Space: O(n) for storing the entire map. n denotes the number of key-value entries stored in the map.

Type Map​

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

Function toPure​

func toPure<K, V>(map : Map<K, V>, compare : (K, K) -> Order.Order) : PureMap.Map<K, V>

Convert the mutable key-value map to an immutable key-value map.

Example:

import Map "mo:core/Map";
import PureMap "mo:core/pure/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";

persistent actor {
  let map = Map.fromIter<Nat, Text>(
    [(0, "Zero"), (1, "One"), (2, "Two")].values(), Nat.compare);
  let pureMap = Map.toPure(map, Nat.compare);
  assert Iter.toArray(PureMap.entries(pureMap)) == Iter.toArray(Map.entries(map))
}

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.

Function fromPure​

func fromPure<K, V>(map : PureMap.Map<K, V>, compare : (K, K) -> Order.Order) : Map<K, V>

Convert an immutable key-value map to a mutable key-value map.

Example:

import Map "mo:core/Map";
import PureMap "mo:core/pure/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";

persistent actor {
  let pureMap = PureMap.fromIter(
    [(0, "Zero"), (1, "One"), (2, "Two")].values(), Nat.compare);
  let map = Map.fromPure<Nat, Text>(pureMap, Nat.compare);
  assert Iter.toArray(Map.entries(map)) == Iter.toArray(PureMap.entries(pureMap))
}

Runtime: O(n * log(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.

Function clone​

func clone<K, V>(map : Map<K, V>) : Map<K, V>

Create a copy of the mutable key-value map.

Example:

import Map "mo:core/Map";
import Nat "mo:core/Nat";

persistent actor {
  let originalMap = Map.fromIter<Nat, Text>(
    [(1, "One"), (2, "Two"), (3, "Three")].values(), Nat.compare);
  let clonedMap = Map.clone(originalMap);
  Map.add(originalMap, Nat.compare, 4, "Four");
  assert Map.size(clonedMap) == 3;
  assert Map.size(originalMap) == 4;
}

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

Function empty​

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

Create a new empty mutable key-value map.

Example:

import Map "mo:core/Map";

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

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

Function singleton​

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

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

Example:

import Map "mo:core/Map";
import Iter "mo:core/Iter";

persistent actor {
  let map = Map.singleton<Nat, Text>(0, "Zero");
  assert Iter.toArray(Map.entries(map)) == [(0, "Zero")];
}

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

Function clear​

func clear<K, V>(map : Map<K, V>)

Delete all the entries in the key-value map.

Example:

import Map "mo:core/Map";
import Nat "mo:core/Nat";

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

  assert Map.size(map) == 3;

  Map.clear(map);
  assert Map.size(map) == 0;
}

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

Function isEmpty​

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

Determines whether a key-value map is empty.

Example:

import Map "mo:core/Map";
import Nat "mo:core/Nat";

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

  assert not Map.isEmpty(map);
  Map.clear(map);
  assert Map.isEmpty(map);
}

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

Function size​

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

Return the number of entries in a key-value map.

Example:

import Map "mo:core/Map";
import Nat "mo:core/Nat";

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

  assert Map.size(map) == 3;
  Map.clear(map);
  assert Map.size(map) == 0;
}

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

Function equal​

func equal<K, V>(map1 : Map<K, V>, map2 : Map<K, V>, compareKeys : (K, K) -> Types.Order, equalValues : (V, V) -> Bool) : Bool

Test whether two imperative maps have equal entries. Both maps have to be constructed by the same comparison function.

Example:

import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Text "mo:core/Text";

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

  assert Map.equal(map1, map2, Nat.compare, Text.equal);
  Map.clear(map2);
  assert not Map.equal(map1, map2, Nat.compare, Text.equal);
}

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

Function containsKey​

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

Tests whether the map contains the provided key.

Example:

import Map "mo:core/Map";
import Nat "mo:core/Nat";

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

  assert Map.containsKey(map, Nat.compare, 1);
  assert not Map.containsKey(map, Nat.compare, 3);
}

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.

Function get​

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

Get the value associated with key in the given map if present and null otherwise.

Example:

import Map "mo:core/Map";
import Nat "mo:core/Nat";

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

  assert Map.get(map, Nat.compare, 1) == ?"One";
  assert Map.get(map, Nat.compare, 3) == 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.

Function insert​

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

Given map ordered by compare, insert a new mapping from key to value. Replaces any existing entry under key. Returns true if the key is new to the map, otherwise false.

Example:

import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";

persistent actor {
  let map = Map.empty<Nat, Text>();
  assert Map.insert(map, Nat.compare, 0, "Zero");
  assert Map.insert(map, Nat.compare, 1, "One");
  assert Iter.toArray(Map.entries(map)) == [(0, "Zero"), (1, "One")];
  assert not Map.insert(map, Nat.compare, 0, "Nil");
  assert 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.

Function add​

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

Given map ordered by compare, add a mapping from key to value to map. Replaces any existing entry for key.

Example:

import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";

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

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

  assert 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.

Function swap​

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

Associates the value with the key in the map. If the key is not yet present in the map, a new key-value pair is added and null is returned. Otherwise, if the key is already present, the value is overwritten and the previous value is returned.

Example:

import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";

persistent actor {
  let map = Map.singleton<Nat, Text>(1, "One");

  assert Map.swap(map, Nat.compare, 0, "Zero") == null;
  assert Iter.toArray(Map.entries(map)) == [(0, "Zero"), (1, "One")];

  assert Map.swap(map, Nat.compare, 0, "Nil") == ?"Zero";
  assert 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.

Function replace​

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

Overwrites the value of an existing key and returns the previous value. If the key does not exist, it has no effect and returns null.

Example:

import Map "mo:core/Map";
import Nat "mo:core/Nat";

persistent actor {
  let map = Map.singleton<Nat, Text>(0, "Zero");

  let prev1 = Map.replace(map, Nat.compare, 0, "Nil"); // overwrites the value for existing key.
  assert prev1 == ?"Zero";
  assert Map.get(map, Nat.compare, 0) == ?"Nil";

  let prev2 = Map.replace(map, Nat.compare, 1, "One");  // no effect, key is absent
  assert prev2 == null;
  assert Map.get(map, Nat.compare, 1) == 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.

Function remove​

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

Delete an entry by its key in the map. No effect if the key is not present.

import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";

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

  Map.remove(map, Nat.compare, 1);
  assert Iter.toArray(Map.entries(map)) == [(0, "Zero"), (2, "Two")];
  Map.remove(map, Nat.compare, 42);
  assert Iter.toArray(Map.entries(map)) == [(0, "Zero"), (2, "Two")];
}

Runtime: O(log(n)). Space: O(log(n)) including garbage, see 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(log(n)) objects that will be collected as garbage.

Function delete​

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

Delete an existing entry by its key in the map. Returns true if the key was present in the map, otherwise false.

import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";

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

  assert Map.delete(map, Nat.compare, 1); // present, returns true
  assert Iter.toArray(Map.entries(map)) == [(0, "Zero"), (2, "Two")];

  assert not Map.delete(map, Nat.compare, 42); // absent, returns false
  assert Iter.toArray(Map.entries(map)) == [(0, "Zero"), (2, "Two")];
}

Runtime: O(log(n)). Space: O(log(n)) including garbage, see 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(log(n)) objects that will be collected as garbage.

Function take​

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

Removes any existing entry by its key in the map. Returns the previous value of the key or null if the key was absent.

import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";

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

  assert Map.take(map, Nat.compare, 0) == ?"Zero";
  assert Iter.toArray(Map.entries(map)) == [(1, "One"), (2, "Two")];

  assert Map.take(map, Nat.compare, 3) == null;
  assert Iter.toArray(Map.entries(map)) == [(1, "One"), (2, "Two")];
}

Runtime: O(log(n)). Space: O(log(n)) including garbage, see 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(log(n)) objects that will be collected as garbage.

Function maxEntry​

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

Retrieves the key-value pair from the map with the maximum key. If the map is empty, returns null.

Example:

import Map "mo:core/Map";
import Nat "mo:core/Nat";

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

  assert Map.maxEntry(map) == null;

  Map.add(map, Nat.compare, 0, "Zero");
  Map.add(map, Nat.compare, 2, "Two");
  Map.add(map, Nat.compare, 1, "One");

  assert Map.maxEntry(map) == ?(2, "Two")
}

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

Function minEntry​

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

Retrieves the key-value pair from the map with the minimum key. If the map is empty, returns null.

Example:

import Map "mo:core/Map";
import Nat "mo:core/Nat";

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

  assert Map.minEntry(map) == null;

  Map.add(map, Nat.compare, 2, "Two");
  Map.add(map, Nat.compare, 0, "Zero");
  Map.add(map, Nat.compare, 1, "One");

  assert Map.minEntry(map) == ?(0, "Zero")
}

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

Function entries​

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

Returns an iterator over the key-value pairs in the map, traversing the entries in the ascending order of the keys.

Example:

import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";

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

  assert Iter.toArray(Map.entries(map)) == [(0, "Zero"), (1, "One"), (2, "Two")];
  var sum = 0;
  var text = "";
  for ((k, v) in Map.entries(map)) { sum += k; text #= v };
  assert sum == 3;
  assert text == "ZeroOneTwo"
}

Cost of iteration over all elements: 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.

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

Function entriesFrom​

func entriesFrom<K, V>(map : Map<K, V>, compare : (K, K) -> Order.Order, key : K) : Types.Iter<(K, V)>

Returns an iterator over the key-value pairs in the map, starting from a given key in ascending order.

Example:

import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";

persistent actor {
  let map = Map.fromIter<Nat, Text>([(0, "Zero"), (3, "Three"),  (1, "One")].values(), Nat.compare);
  assert Iter.toArray(Map.entriesFrom(map, Nat.compare, 1)) == [(1, "One"), (3, "Three")];
  assert Iter.toArray(Map.entriesFrom(map, Nat.compare, 2)) == [(3, "Three")];
}

Cost of iteration over all elements: 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.

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

Function reverseEntries​

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

Returns an iterator over the key-value pairs in the map, traversing the entries in the descending order of the keys.

Example:

import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";

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

  assert Iter.toArray(Map.reverseEntries(map)) == [(2, "Two"), (1, "One"), (0, "Zero")];
  var sum = 0;
  var text = "";
  for ((k, v) in Map.reverseEntries(map)) { sum += k; text #= v };
  assert sum == 3;
  assert text == "TwoOneZero"
}

Cost of iteration over all elements: 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.

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

Function reverseEntriesFrom​

func reverseEntriesFrom<K, V>(map : Map<K, V>, compare : (K, K) -> Order.Order, key : K) : Types.Iter<(K, V)>

Returns an iterator over the key-value pairs in the map, starting from a given key in descending order.

Example:

import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";

persistent actor {
  let map = Map.fromIter<Nat, Text>([(0, "Zero"), (1, "One"), (3, "Three")].values(), Nat.compare);
  assert Iter.toArray(Map.reverseEntriesFrom(map, Nat.compare, 0)) == [(0, "Zero")];
  assert Iter.toArray(Map.reverseEntriesFrom(map, Nat.compare, 2)) == [(1, "One"), (0, "Zero")];
}

Cost of iteration over all elements: 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.

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

Function keys​

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

Returns an iterator over the keys in the map, traversing all keys in ascending order.

Example:

import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";

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

  assert Iter.toArray(Map.keys(map)) == [0, 1, 2];
}

Cost of iteration over all elements: Runtime: O(n). Space: O(1).

Function values​

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

Returns an iterator over the values in the map, traversing the values in the ascending order of the keys to which they are associated.

Example:

import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";

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

  assert Iter.toArray(Map.values(map)) == ["Zero", "One", "Two"];
}

Cost of iteration over all elements: Runtime: O(n). Space: O(1).

Function fromIter​

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

Create a mutable key-value map with the entries obtained from an iterator.

Example:

import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";

persistent actor {
  transient let iter =
    Iter.fromArray([(0, "Zero"), (2, "Two"), (1, "One")]);

  let map = Map.fromIter<Nat, Text>(iter, Nat.compare);

   assert Iter.toArray(Map.entries(map)) == [(0, "Zero"), (1, "One"), (2, "Two")];
}

Runtime: O(n * log(n)). Space: O(n). where n denotes the number of key-value entries returned by the iterator and assuming that the compare function implements an O(1) comparison.

Function forEach​

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

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

Example:

import Map "mo:core/Map";
import Nat "mo:core/Nat";

persistent actor {
  let map = Map.fromIter<Nat, Text>([(0, "Zero"), (2, "Two"), (1, "One")].values(), Nat.compare);
  var sum = 0;
  var text = "";
  Map.forEach<Nat, Text>(map, func (key, value) {
    sum += key;
    text #= value;
  });
  assert sum == 3;
  assert text == "ZeroOneTwo";
}

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.

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

Function filter​

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. Create a copy of the mutable map that only contains the key-value pairs that fulfil the criterion function.

Example:

import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";

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

  let evenNames = Map.filter<Nat, Text>(numberNames, Nat.compare, func (key, value) {
    key % 2 == 0
  });

  assert Iter.toArray(Map.entries(evenNames)) == [(0, "Zero"), (2, "Two")];
}

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.

Function map​

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

Project all values of the map in a new map. Apply a mapping function to the values of each entry in the map and collect the mapped entries in a new mutable key-value map.

Example:

import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";

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

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

  let resMap = Map.map<Nat, Text, Nat>(map, f);

  assert Iter.toArray(Map.entries(resMap)) == [(0, 0), (1, 2), (2, 4)];
}

Runtime: O(n * log(n)). Space: O(n) retained memory plus garbage, see 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(log(n)) temporary objects that will be collected as garbage.

Function foldLeft​

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

Iterate all entries in ascending order of the keys, and accumulate the entries by applying the combine function, starting from a base value.

Example:

import Map "mo:core/Map";
import Nat "mo:core/Nat";

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

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

  assert Map.foldLeft(map, (0, ""), folder) == (3, "ZeroOneTwo");
}

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.

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

Function foldRight​

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

Iterate all entries in descending order of the keys, and accumulate the entries by applying the combine function, starting from a base value.

Example:

import Map "mo:core/Map";
import Nat "mo:core/Nat";

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

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

  assert Map.foldRight(map, (0, ""), folder) == (3, "TwoOneZero");
}

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.

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

Function all​

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

Check whether all entries in the map fulfil a predicate function, i.e. the predicate function returns true for all entries in the map. Returns true for an empty map.

Example:

import Map "mo:core/Map";
import Nat "mo:core/Nat";

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

  assert Map.all<Nat, Text>(map, func (k, v) = v == Nat.toText(k));
  assert not Map.all<Nat, Text>(map, func (k, v) = k < 2);
}

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.

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

Function any​

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

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

Example:

import Map "mo:core/Map";
import Nat "mo:core/Nat";

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

  assert Map.any<Nat, Text>(map, func (k, v) = (k >= 0));
  assert not Map.any<Nat, Text>(map, func (k, v) = (k >= 3));
}

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.

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

Function filterMap​

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

Filter all entries in the map by also applying a projection to the value. Apply a mapping function project to all entries in the map and collect all entries, for which the function returns a non-null new value. Collect all non-discarded entries with the key and new value in a new mutable map.

Example:

import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";

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

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

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

  assert Iter.toArray(Map.entries(newMap)) == [(1, "Twenty One"), (2, "Twenty Two")];
}

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

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

Function assertValid​

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

Internal sanity check function. Can be used to check that key/value pairs have been inserted with a consistent key comparison function. Traps if the internal map structure is invalid.

Function toText​

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

Generate a textual representation of all the entries in the map. Primarily to be used for testing and debugging. The keys and values are formatted according to keyFormat and valueFormat.

Example:

import Map "mo:core/Map";
import Nat "mo:core/Nat";

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

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

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

Function compare​

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 must have been created by the same key comparison function. The two 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:

  • the pairwise iteration hits a entry pair entry1 and entry2 where entry1 is less than entry2 and all preceding entry pairs are equal, or,
  • map1 is a strict prefix of map2, i.e. map2 has more entries than map1 and all entries of map1 occur at the beginning of iteration map2. entry1 is less than entry2 if:
  • the key of entry1 is less than the key of entry2, or
  • entry1 and entry2 have equal keys and the value of entry1 is less than the value of entry2. Equal: map1 and map2 have same series of equal entries by pairwise iteration. Greater: map1 is neither less nor equal map2.

Example:

import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Text "mo:core/Text";

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

  assert Map.compare(map1, map2, Nat.compare, Text.compare) == #less;
  assert Map.compare(map1, map1, Nat.compare, Text.compare) == #equal;
  assert 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.