Map implemented as a linked-list of key-value pairs ("Associations").
:::note 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. :::
:::note Assumptions
Runtime and space complexity assumes that combine, equal, and other functions execute in O(1) time and space.
:::
Blob is an immutable, iterable sequence of bytes. Unlike [Nat8], which is less compact (using 4 bytes per logical byte), Blob provides a more efficient representation.
Blobs are not indexable and can be empty. To manipulate a Blob, convert it to [var Nat8] or Buffer<Nat8>, perform your changes, then convert it back.
Import from the base library to use this module.
motoko name=import
import Blob "mo:base/Blob";:::note Additional features
Some built-in features are not listed in this module:
Blob literal from a Text literal, provided the context expects an expression of type Blob.b.size() : Nat returns the number of bytes in the blob b.b.vals() : Iter.Iter<Nat8> returns an iterator to enumerate the bytes of the blob b.
:::For example:
motoko include=import
import Debug "mo:base/Debug";
import Nat8 "mo:base/Nat8";
let blob = "\00\00\00\ff" : Blob; // blob literals, where each byte is delimited by a back-slash and represented in hex
let blob2 = "charsもあり" : Blob; // you can also use characters in the literals
let numBytes = blob.size(); // => 4 (returns the number of bytes in the Blob)
for (byte : Nat8 in blob.vals()) { // iterator over the Blob
Debug.print(Nat8.toText(byte))
}:::note Operator limitation
Comparison functions (equal, notEqual, less, lessOrEqual, greater, greaterOrEqual) are defined in this library to allow their use as function values in higher-order functions.
Operators like ==, !=, <, <=, >, and >= cannot currently be passed as function values.
:::
Boolean type and operations.
While boolean operators _ and _ and _ or _ are short-circuiting,
avoiding computation of the right argument when possible, the functions
logand(_, _) and logor(_, _) are strict and will always evaluate both
of their arguments.
Class Buffer<X> provides a mutable list of elements of type X.
It wraps a resizable underlying array and is comparable to ArrayList or Vector in other languages.
You can convert a buffer to a fixed-size array using Buffer.toArray, which is recommended for storing data in stable variables.
Like arrays, buffer elements are indexed from 0 to size - 1.
:::note Assumptions
Runtime and space complexity assumes that combine, equal, and other functions execute in O(1) time and space.
:::
:::note Size vs capacity
size: Number of elements in the buffer.capacity: Length of the underlying array.The invariant capacity >= size always holds.
:::
:::warning Performance caveat
Operations like add are amortized O(1) but can take O(n) in the worst case.
For large buffers, these worst cases may exceed the cycle limit per message.
Use with care when growing buffers dynamically.
:::
:::info Constructor behavior
The initCapacity argument sets the initial capacity of the underlying array.
Example:
motoko name=initialize
import Buffer "mo:base/Buffer";
let buffer = Buffer.Buffer<Nat>(3); // Creates a new Buffer| Runtime | Space |
|-----------|-----------|
| O(initCapacity) | O(initCapacity) |
The Internet Computer allows canister smart contracts to store a small amount of data during update method processing so that during query call processing, the canister can obtain a certificate about that data.
:::info Intended audience
This module provides a low-level interface to this API, aimed at advanced users and library implementors. See the Internet Computer interface specification and corresponding documentation for how to use this to make query calls to your canister tamperproof. :::
Utility functions for debugging.
Import from the base library to use this module.
motoko name=import
import Debug "mo:base/Debug";Double-ended queue (deque) of a generic element type T.
The interface of deques is purely functional, not imperative, and deques are immutable values. In particular, deque operations such as push and pop do not update their input deque but instead return the value of the modified deque, alongside any other data. The input deque is left unchanged.
Examples of use-cases:
Queue (FIFO) by using pushBack() and popFront().
Stack (LIFO) by using pushFront() and popFront().
A deque is internally implemented as two lists, a head access list and a (reversed) tail access list, that are dynamically size-balanced by splitting.
Construction: Create a new deque with the empty<T>() function.
:::note Performance characteristics
Push and pop operations have O(1) amortized cost and O(n) worst-case cost per call.
Space usage follows the same pattern.
n denotes the number of elements stored in the deque.
:::
Error values and inspection.
The Error type is the argument to throw, parameter of catch.
The Error type is opaque.
Managing cycles within actors on the Internet Computer (ICP).
The usage of the Internet Computer is measured, and paid for, in cycles. This library provides imperative operations for observing cycles, transferring cycles, and observing refunds of cycles.
:::warning Experimental API
This low-level API is experimental and may change or be removed in the future. Dedicated syntactic support for manipulating cycles may be added to the language, which would make this library obsolete. :::
:::note Volatile cycle balance
Since cycles measure computational resources, the value of balance() can change from one call to the next.
:::
Example:
motoko no-repl
import Cycles "mo:base/ExperimentalCycles";
import Debug "mo:base/Debug";
actor {
public func main() : async() {
Debug.print("Main balance: " # debug_show(Cycles.balance()));
Cycles.add<system>(15_000_000);
await operation(); // accepts 10_000_000 cycles
Debug.print("Main refunded: " # debug_show(Cycles.refunded())); // 5_000_000
Debug.print("Main balance: " # debug_show(Cycles.balance())); // decreased by around 10_000_000
};
func operation() : async() {
Debug.print("Operation balance: " # debug_show(Cycles.balance()));
Debug.print("Operation available: " # debug_show(Cycles.available()));
let obtained = Cycles.accept<system>(10_000_000);
Debug.print("Operation obtained: " # debug_show(obtained)); // => 10_000_000
Debug.print("Operation balance: " # debug_show(Cycles.balance())); // increased by 10_000_000
Debug.print("Operation available: " # debug_show(Cycles.available())); // decreased by 10_000_000
}
}Low-level interface to the Internet Computer.
:::warning Experimental API This low-level API is experimental and likely to change or even disappear. :::
Byte-level access to (virtual) stable memory.
:::warning Experimental module
As the name suggests, this library is experimental, subject to change, and may be replaced by safer alternatives in later versions of Motoko. Use at your own risk and discretion. :::
:::warning Deprecation notice
Use of ExperimentalStableMemory may be deprecated in the future.
Consider using Region.mo for isolated memory regions.
Isolated regions ensure that writing to one region does not affect unrelated state elsewhere.
:::
This is a lightweight abstraction over IC stable memory and supports persisting raw binary data across Motoko upgrades. It is fully compatible with Motoko's stable variables, which also use IC stable memory internally, but do not interfere with this API.
Memory is allocated using grow(pages), sequentially and on demand, in units of 64KiB pages, starting with 0 allocated pages.
New pages are zero-initialized.
Growth is capped by a soft page limit set with the compile-time flag --max-stable-pages <n> (default: 65536, or 4GiB).
Each load reads from byte address offset in little-endian format using the natural bit-width of the type.
Traps if reading beyond the allocated size.
Each store writes to byte address offset in little-endian format using the natural bit-width of the type.
Traps if writing beyond the allocated size.
Text can be handled using Text.decodeUtf8 and Text.encodeUtf8 in combination with loadBlob and storeBlob.
The current page allocation and contents are preserved across upgrades.
:::note IC stable memory discrepancy
The IC’s reported stable memory size (ic0.stable_size) may exceed what Motoko’s size() returns.
This and the growth cap exist to protect Motoko’s internal use of stable variables.
If you're not using stable variables (or using them sparingly), you may increase --max-stable-pages toward the IC maximum (currently 64GiB).
Even if not using stable variables, always reserve at least one page.
:::
Usage:
motoko no-repl
import StableMemory "mo:base/ExperimentalStableMemory";Double precision (64-bit) floating-point numbers in IEEE 754 representation.
This module contains common floating-point constants and utility functions.
Notation for special values in the documentation below:
+inf: Positive infinity
-inf: Negative infinity
NaN: "not a number" (can have different sign bit values, but NaN != NaN regardless of the sign).
:::note Floating point numbers have limited precision and operations may inherently result in numerical errors. :::
Examples of numerical errors:
0.1 + 0.1 + 0.1 == 0.3 // => false
1e16 + 1.0 != 1e16 // => false
Advice:
== or != are discouraged. Instead, it is better to compare
floating-point numbers with a numerical tolerance, called epsilon.Example:
import Float "mo:base/Float";
let x = 0.1 + 0.1 + 0.1;
let y = 0.3;
let epsilon = 1e-6; // This depends on the application case (needs a numerical error analysis).
Float.equalWithin(x, y, epsilon) // => true
Nat for the base
and a Nat for the exponent (decimal point).NaN sign:
NaN sign is only applied by abs, neg, and copySign. Other operations can have an arbitrary
sign bit for NaN results.Create functions from simpler inputs, most commonly used when programming in functional style using higher-order functions.
Class HashMap<K, V> provides a hashmap from keys of type K to values of type V.
The class is parameterized by the key's equality and hash functions, and an initial capacity.
However, the underlying allocation occurs only upon the first insertion.
Internally, the map is backed by an array of AssocList (buckets).
The array doubles in size when the expected bucket list size grows beyond a fixed threshold.
:::warning Performance considerations
Certain operations, such as put, are amortized O(1) but can run in worst-case O(size) time.
These worst cases may exceed the cycle limit per message on large maps.
This analysis assumes that the hash function distributes keys uniformly.
Use caution when growing large maps and ensure good hash functions are used.
:::
:::note Non-amortized alternative
For maps without amortization, see TrieMap.
:::
:::info Constructor note
The initCapacity argument sets the initial number of buckets.
All runtime and space complexities assume that the equality and hash functions run in O(1) time and space.
:::
Example:
motoko name=initialize
import HashMap "mo:base/HashMap";
import Text "mo:base/Text";
let map = HashMap.HashMap<Text, Nat>(5, Text.equal, Text.hash);| Runtime | Space |
|-----------|-----------|
| O(1) | O(1) |
Class Heap<X> provides a priority queue of elements of type X.
The class wraps a purely-functional implementation based on a leftist heap.
:::note Constructor details
The constructor takes in a comparison function compare that defines the ordering between elements of type X. Most primitive types have a default version of this comparison function defined in their modules (e.g. Nat.compare). The runtime analysis in this documentation assumes that the compare function runs in O(1) time and space.
:::
Example:
motoko name=initialize
import Heap "mo:base/Heap";
import Text "mo:base/Text";
let heap = Heap.Heap<Text>(Text.compare);| Runtime | Space |
|-----------|-----------|
| O(1) | O(1) |
Signed integer numbers with infinite precision (also called big integers).
:::note
Most operations on integer numbers (e.g. addition) are available as built-in operators (e.g. -1 + 1).
This module provides equivalent functions and Text conversion.
:::
:::info Function form for higher-order use
Several arithmetic and comparison functions (e.g. add, sub, equal, less, pow) are defined in this module to enable their use as first-class function values, which is not possible with operators like +, -, ==, etc., in Motoko. This allows you to pass these operations to higher-order functions such as map, foldLeft, or sort.
:::
Import from the base library to use this module.
motoko name=import
import Int "mo:base/Int";Provides utility functions on 16-bit signed integers.
:::note
Most operations are available as built-in operators (e.g. 1 + 1).
:::
:::info Function form for higher-order use
Several arithmetic and comparison functions (e.g. add, sub, bitor, bitand, pow) are defined in this module to enable their use as first-class function values, which is not possible with operators like +, -, ==, etc., in Motoko. This allows you to pass these operations to higher-order functions such as map, foldLeft, or sort.
:::
Import from the base library to use this module.
motoko name=import
import Int16 "mo:base/Int16";Provides utility functions on 32-bit signed integers.
:::note
Most operations are available as built-in operators (e.g. 1 + 1).
:::
:::info Function form for higher-order use
Several arithmetic and comparison functions (e.g. add, sub, bitor, bitand, pow) are defined in this module to enable their use as first-class function values, which is not possible with operators like +, -, ==, etc., in Motoko. This allows you to pass these operations to higher-order functions such as map, foldLeft, or sort.
:::
motoko name=import
import Int32 "mo:base/Int32";Provides utility functions on 64-bit signed integers.
:::note
Most operations are available as built-in operators (e.g. 1 + 1).
:::
:::info Function form for higher-order use
Several arithmetic and comparison functions (e.g. add, sub, bitor, bitand, pow) are defined in this module to enable their use as first-class function values, which is not possible with operators like +, -, ==, etc., in Motoko. This allows you to pass these operations to higher-order functions such as map, foldLeft, or sort.
:::
Import from the base library to use this module.
motoko name=import
import Int64 "mo:base/Int64";Provides utility functions on 8-bit signed integers.
:::info Function form for higher-order use
Several arithmetic and comparison functions (e.g. add, sub, bitor, bitand, pow) are defined in this module to enable their use as first-class function values, which is not possible with operators like +, -, ==, etc., in Motoko. This allows you to pass these operations to higher-order functions such as map, foldLeft, or sort.
:::
:::note
Most operations are available as built-in operators (e.g. 1 + 1).
:::
Import from the base library to use this module.
motoko name=import
import Int8 "mo:base/Int8";Purely-functional, singly-linked lists.
A list of type List<T> is either null or an optional pair of a value of type T and a tail, itself of type List<T>.
:::note Assumptions
Runtime and space complexity assumes that equal, and other functions execute in O(1) time and space.
:::
To use this library, import it using:
motoko name=initialize
import List "mo:base/List";Natural numbers with infinite precision.
:::note
Most operations on integer numbers (e.g. addition) are available as built-in operators (e.g. 1 + 1).
This module provides equivalent functions and Text conversion.
:::
:::info Function form for higher-order use
Several arithmetic and comparison functions (e.g. add, sub, equal, less, pow) are defined in this module to enable their use as first-class function values, which is not possible with operators like +, -, ==, etc., in Motoko. This allows you to pass these operations to higher-order functions such as map, foldLeft, or sort.
:::
Import from the base library to use this module.
motoko name=import
import Nat "mo:base/Nat";Provides utility functions on 16-bit unsigned integers.
:::note
Most operations on integer numbers (e.g. addition) are available as built-in operators (e.g. 1 + 1).
This module provides equivalent functions and Text conversion.
:::
:::info Function form for higher-order use
Several arithmetic and comparison functions (e.g. add, sub, equal, less, pow) are defined in this module to enable their use as first-class function values, which is not possible with operators like +, -, ==, etc., in Motoko. This allows you to pass these operations to higher-order functions such as map, foldLeft, or sort.
:::
Import from the base library to use this module.
motoko name=import
import Nat16 "mo:base/Nat16";Provides utility functions on 32-bit unsigned integers.
:::note
Most operations on integer numbers (e.g. addition) are available as built-in operators (e.g. 1 + 1).
This module provides equivalent functions and Text conversion.
:::
:::info Function form for higher-order use
Several arithmetic and comparison functions (e.g. add, sub, equal, less, pow) are defined in this module to enable their use as first-class function values, which is not possible with operators like +, -, ==, etc., in Motoko. This allows you to pass these operations to higher-order functions such as map, foldLeft, or sort.
:::
Import from the base library to use this module.
motoko name=import
import Nat32 "mo:base/Nat32";Provides utility functions on 64-bit unsigned integers.
:::note
Most operations on integer numbers (e.g. addition) are available as built-in operators (e.g. 1 + 1).
This module provides equivalent functions and Text conversion.
:::
:::info Function form for higher-order use
Several arithmetic and comparison functions (e.g. add, sub, equal, less, pow) are defined in this module to enable their use as first-class function values, which is not possible with operators like +, -, ==, etc., in Motoko. This allows you to pass these operations to higher-order functions such as map, foldLeft, or sort.
:::
Import from the base library to use this module.
motoko name=import
import Nat64 "mo:base/Nat64";Provides utility functions on 8-bit unsigned integers.
:::note
Most operations on integer numbers (e.g. addition) are available as built-in operators (e.g. 1 + 1).
This module provides equivalent functions and Text conversion.
:::
:::info Function form for higher-order use
Several arithmetic and comparison functions (e.g. add, sub, equal, less, pow) are defined in this module to enable their use as first-class function values, which is not possible with operators like +, -, ==, etc., in Motoko. This allows you to pass these operations to higher-order functions such as map, foldLeft, or sort.
:::
Import from the base library to use this module.
motoko name=import
import Nat8 "mo:base/Nat8";The None type represents a type with no value.
It is often used to type code that fails to return control (e.g. an infinite loop)
or to designate impossible values (e.g. the type ?None only contains null).
Optional values can be seen as a typesafe null. A value of type ?Int can
be constructed with either null or ?42. The simplest way to get at the
contents of an optional is to use pattern matching:
let optionalInt1 : ?Int = ?42;
let optionalInt2 : ?Int = null;
let int1orZero : Int = switch optionalInt1 {
case null 0;
case (?int) int;
};
assert int1orZero == 42;
let int2orZero : Int = switch optionalInt2 {
case null 0;
case (?int) int;
};
assert int2orZero == 0;The functions in this module capture some common operations when working with optionals that can be more succinct than using pattern matching.
Stable key-value map implemented as a red-black tree with nodes storing key-value pairs.
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.
| Runtime | Space |
|----------|------------|
| O(log(n)) (worst case per insertion, removal, or retrieval) | O(n) (for storing the entire tree) |
n denotes the number of key-value entries (i.e. nodes) stored in the tree.
:::note Garbage collection
Unless stated otherwise, operations that iterate over or modify the map (such as insertion, deletion, traversal, and transformation) may create temporary objects with worst-case space usage of O(log(n)) or O(n). These objects are short-lived and will be collected by the garbage collector automatically.
:::
:::note Assumptions
Runtime and space complexity assumes that compare, equal, and other functions execute in O(1) time and space.
:::
:::info Credits
The core of this implementation is derived from:
Stable ordered set implemented as a red-black tree.
A red-black tree is a balanced binary search tree ordered by the elements.
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.
| Runtime | Space |
|----------|------------|
| O(log(n)) (worst case per insertion, removal, or retrieval) | O(n) (for storing the entire tree) |
n denotes the number of key-value entries (i.e. nodes) stored in the tree.
:::note Garbage collection
Unless stated otherwise, operations that iterate over or modify the map (such as insertion, deletion, traversal, and transformation) may create temporary objects with worst-case space usage of O(log(n)) or O(n). These objects are short-lived and will be collected by the garbage collector automatically.
:::
:::note Assumptions
Runtime and space complexity assumes that compare, equal, and other functions execute in O(1) time and space.
:::
:::info Credits
The core of this implementation is derived from:
This prelude file proposes standard library features that may belong in the language (compiler-internal) prelude sometime, after some further experience and discussion. Until then, they live here.
Module for interacting with Principals (users, canisters, or other entities).
Principals are used to identify entities that can interact with the Internet Computer including users or canisters.
Example textual representation of Principals:
un4fu-tqaaa-aaaab-qadjq-cai
In Motoko, there is a primitive Principal type called Principal. As an example
of where you might see Principals, you can access the Principal of the
caller of your shared function.
motoko no-repl
shared(msg) func foo() {
let caller : Principal = msg.caller;
};Then, you can use this module to work with the Principal.
:::note Comparison usage
These functions are defined in this library in addition to the existing comparison operators so that they can be passed as function values to higher-order functions. It is currently not possible to use operators such as ==, !=, <, <=, >, or >= as function values directly.
:::
Import from the base library to use this module.
motoko name=import
import Principal "mo:base/Principal";Key-value map implemented as a red-black tree (RBTree) with nodes storing key-value pairs.
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.
Creation:
Instantiate class RBTree<K, V> that provides a map from keys of type K to values of type V.
Example:
import RBTree "mo:base/RBTree";
import Nat "mo:base/Nat";
import Debug "mo:base/Debug";
let tree = RBTree.RBTree<Nat, Text>(Nat.compare); // Create a new red-black tree mapping Nat to Text
tree.put(1, "one");
tree.put(2, "two");
tree.put(3, "tree");
for (entry in tree.entries()) {
Debug.print("Entry key=" # debug_show(entry.0) # " value=\"" # entry.1 #"\"");
}:::note Performance
O(log(n)) worst case cost per insertion, removal, and retrieval operation.O(n) for storing the entire tree.O(log(n)) for storing the entire tree.n` denotes the number of key-value entries (i.e. nodes) stored in the tree.
::::::note
Tree insertion, replacement, and removal produce O(log(n)) garbage objects.
:::
:::info Credits The core of this implementation is derived from:
A module for obtaining randomness on the Internet Computer (IC).
This module provides the fundamentals for user abstractions to build on.
Dealing with randomness on a deterministic computing platform, such as the IC, is intricate. Some basic rules need to be followed by the user of this module to obtain (and maintain) the benefits of crypto- graphic randomness:
Blobs).Blob) - or surplus entropy
not utilised yet - cannot be used for a new round of bets without
losing the cryptographic guarantees.Concretely, the below class Finite, as well as the
*From methods risk the carrying-over of state from previous rounds.
These are provided for performance (and convenience) reasons, and need
special care when used. Similar caveats apply for user-defined (pseudo)
random number generators.
Usage:
motoko no-repl
import Random "mo:base/Random";Byte-level access to isolated, (virtual) stable memory regions.
This is a moderately lightweight abstraction over IC stable memory and supports persisting
regions of binary data across Motoko upgrades.
Use of this module is fully compatible with Motoko's use of
stable variables, whose persistence mechanism also uses (real) IC stable memory internally, but does not interfere with this API.
It is also fully compatible with existing uses of the ExperimentalStableMemory library, which has a similar interface, but,
only supported a single memory region, without isolation between different applications.
The Region type is stable and can be used in stable data structures.
A new, empty Region is allocated using function new().
Regions are stateful objects and can be distinguished by the numeric identifier returned by function id(region).
Every region owns an initially empty, but growable sequence of virtual IC stable memory pages.
The current size, in pages, of a region is returned by function size(region).
The size of a region determines the range, [ 0, ..., size(region)*2^16 ), of valid byte-offsets into the region; these offsets are used as the source and destination of load/store operations on the region.
Memory is allocated to a region, using function grow(region, pages), sequentially and on demand, in units of 64KiB logical pages, starting with 0 allocated pages.
A call to grow may succeed, returning the previous size of the region, or fail, returning a sentinel value. New pages are zero initialized.
A size of a region can only grow and never shrink. In addition, the stable memory pages allocated to a region will not be reclaimed by garbage collection, even if the region object itself becomes unreachable.
Growth is capped by a soft limit on physical page count controlled by compile-time flag
--max-stable-pages <n> (the default is 65536, or 4GiB).
Each load operation loads from region relative byte address offset in little-endian
format using the natural bit-width of the type in question.
The operation traps if attempting to read beyond the current region size.
Each store operation stores to region relative byte address offset in little-endian format using the natural bit-width of the type in question.
The operation traps if attempting to write beyond the current region size.
Text values can be handled by using Text.decodeUtf8 and Text.encodeUtf8, in conjunction with loadBlob and storeBlob.
The current region allocation and region contents are preserved across upgrades.
NB: The IC's actual stable memory size (ic0.stable_size) may exceed the
total page size reported by summing all regions sizes.
This (and the cap on growth) are to accommodate Motoko's stable variables and bookkeeping for regions.
Applications that plan to use Motoko stable variables sparingly or not at all can
increase --max-stable-pages as desired, approaching the IC maximum (initially 8GiB, then 32Gib, currently 64Gib).
All applications should reserve at least one page for stable variable data, even when no stable variables are used.
Usage:
motoko no-repl
import Region "mo:base/Region";Error handling with the Result type.
Class Stack<X> provides a minimal LIFO stack of elements of type X.
See library Deque for mixed LIFO/FIFO behavior.
Example:
motoko name=initialize
import Stack "mo:base/Stack";
let stack = Stack.Stack<Nat>(); // create a stack| Runtime | Space |
|-----------|-----------|
| O(1) | O(1) |
Utility functions for Text values.
A Text value represents human-readable text as a sequence of characters of type Char.
let text = "Hello!";
let size = text.size(); // 6
let iter = text.chars(); // iterator ('H', 'e', 'l', 'l', 'o', '!')
let concat = text # " 👋"; // "Hello! 👋"The "mo:base/Text" module defines additional operations on Text values.
Import the module from the base library:
motoko name=import
import Text "mo:base/Text";:::note
Text values are represented as ropes of UTF-8 character sequences with O(1) concatenation.
:::
System time
Timers for one-off or periodic tasks. Applicable as part of the default mechanism.
:::note Timer resolution
The resolution of the timers is in the order of the block rate, so durations should be chosen well above that. For frequent canister wake-ups the heartbeat mechanism should be considered. :::
:::note Overriding system function
The functionality described below is enabled only when the actor does not override it by declaring an explicit system func timer.
:::
:::note Upgrade persistence
Timers are not persisted across upgrades. One possible strategy
to re-establish timers after an upgrade is to walk stable variables
in the post_upgrade hook and distill necessary timer information
from there.
:::
:::note Security warning
Basing security (e.g. access control) on timers is almost always the wrong choice. Be sure to inform yourself about state-of-the-art dApp security. If you must use timers for security controls, be sure to consider reentrancy issues, and the vanishing of timers on upgrades and reinstalls. :::
:::note Further information
Further usage information for timers. :::
:::note Compilation flag
If moc is invoked with -no-timer, the importing will fail.
:::
Functional key-value hash map.
Provides an applicative (purely functional) hash map, called a trie, where each operation returns a new version of the structure without mutating the original.
Operations use Key records that group the key value with its precomputed hash.
For imperative or object-oriented alternatives, see TrieMap or HashMap.
:::warning Hash collision limit
Each trie node supports at most 8 distinct keys with the same hash (MAX_LEAF_SIZE = 8). Exceeding this will cause a trap.
:::
:::info Credits Based on Section 6 of "Incremental computation via function caching", Pugh & Teitelbaum. :::
Example:
import Trie "mo:base/Trie";
import Text "mo:base/Text";
// we do this to have shorter type names and thus
// better readability
type Trie<K, V> = Trie.Trie<K, V>;
type Key<K> = Trie.Key<K>;
// we have to provide `put`, `get` and `remove` with
// a record of type `Key<K> = { hash : Hash.Hash; key : K }`;
// thus we define the following function that takes a value of type `K`
// (in this case `Text`) and returns a `Key<K>` record.
func key(t: Text) : Key<Text> { { hash = Text.hash t; key = t } };
// we start off by creating an empty `Trie`
let t0 : Trie<Text, Nat> = Trie.empty();
// `put` requires 4 arguments:
// - the trie we want to insert the value into,
// - the key of the value we want to insert (note that we use the `key` function defined above),
// - a function that checks for equality of keys, and
// - the value we want to insert.
//
// When inserting a value, `put` returns a tuple of type `(Trie<K, V>, ?V)`.
// to get the new trie that contains the value, we use the `0` projection
// and assign it to `t1` and `t2` respectively.
let t1 : Trie<Text, Nat> = Trie.put(t0, key "hello", Text.equal, 42).0;
let t2 : Trie<Text, Nat> = Trie.put(t1, key "world", Text.equal, 24).0;
// If for a given key there already was a value in the trie, `put` returns
// that previous value as the second element of the tuple.
// in our case we have already inserted the value 42 for the key "hello", so
// `put` returns 42 as the second element of the tuple.
let (t3, n) : (Trie<Text, Nat>, ?Nat) = Trie.put(
t2,
key "hello",
Text.equal,
0,
);
assert (n == ?42);
// `get` requires 3 arguments:
// - the trie we want to get the value from
// - the key of the value we want to get (note that we use the `key` function defined above)
// - a function that checks for equality of keys
//
// If the given key is nonexistent in the trie, `get` returns `null`.
var value = Trie.get(t3, key "hello", Text.equal); // Returns `?42`
assert(value == ?0);
value := Trie.get(t3, key "universe", Text.equal); // Returns `null`
assert(value == null);
// `remove` requires 3 arguments:
// - the trie we want to remove the value from,
// - the key of the value we want to remove (note that we use the `key` function defined above), and
// - a function that checks for equality of keys.
//
// In the case of keys of type `Text`, we can use `Text.equal`
// to check for equality of keys. Function `remove` returns a tuple of type `(Trie<K, V>, ?V)`.
// where the second element of the tuple is the value that was removed, or `null` if
// there was no value for the given key.
let removedValue : ?Nat = Trie.remove(
t3,
key "hello",
Text.equal,
).1;
assert (removedValue == ?0);
// To iterate over the Trie, we use the `iter` function that takes a trie
// of type `Trie<K,V>` and returns an iterator of type `Iter<(K,V)>`:
var sum : Nat = 0;
for (kv in Trie.iter(t3)) {
sum += kv.1;
};
assert(sum == 24);Class TrieMap<K, V> provides a map from keys of type K to values of type V.
The class wraps and manipulates an underlying hash trie, found in the Trie module.
The trie is a binary tree where element positions are determined using the hash of the keys.
:::warning Limitations
This data structure allows at most MAX_LEAF_SIZE = 8 hash collisions.
Attempts to insert more than 8 keys (whether directly via put or indirectly via other operations) with the same hash value will trap.
This limitation is inherited from the underlying Trie data structure.
:::
:::note Interface compatibility
The class TrieMap exposes the same interface as HashMap.
:::
:::note Assumptions
Runtime and space complexity assumes that hash, equal, and other function parameters execute in O(1) time and space.
Where applicable, runtimes also assume the trie is reasonably balanced.
:::
:::note Iterator performance
All iterator-related runtime and space costs refer to iterator construction. The iteration itself takes linear time and logarithmic space to execute. :::
Creating a map: The equality function is used to compare keys, and the hash function is used to hash keys. See the example below.
motoko name=initialize
import TrieMap "mo:base/TrieMap";
import Nat "mo:base/Nat";
import Hash "mo:base/Hash";
import Iter "mo:base/Iter";
let map = TrieMap.TrieMap<Nat, Nat>(Nat.equal, Hash.hash)Sets are partial maps from element type to unit type, i.e., the partial map represents the set with its domain.
:::warning Limitations
This data structure allows at most MAX_LEAF_SIZE = 8 hash collisions.
Attempts to insert more than 8 elements with the same hash value—either directly via put or indirectly via other operations—will trap.
This limitation is inherited from the underlying Trie data structure.
:::
Provides extended utility functions on Arrays.
:::warning
If you are looking for a list that can grow and shrink in size, it is recommended you use either the
BufferorListdata structure for those purposes.:::
:::note Assumptions
Runtime and space complexity assumes that
generator,equal, and other functions execute inO(1)time and space. :::Import from the base library to use this module.