The main functions and their definitions. For a complete list of functions and their arguments, please check the library. Many of the definitions are also informal, formal definitions can be found in the PAM paper [PPoPP2018].

For Sequences:

M is the set type. E = K. Z is the integer set.

rank(m, k)	M × E → K	The rank of key k in m
first(m)	M → E	The first element in m
last(m)	M → E	The last element in m
filter(m, φ)	M × (E → bool) → M	All elements in m that satisfy φ
map_reduce(m, map, reduce, zero)	M × (E → B) × (B × B → B) × B → B	Mapping all elements in m using the function "map" and then reduce all result using the function "reduce", with an identity of "zero"
pam_seq()	∅ → M	Constructor. Create an empty sequence (tree)
pam_seq(e)	E → M	Constructor Create a sequence (tree) from a single entry
pam_seq(a)	array → M	Constructor. Construct a sequence (tree) from an array.
for_each_index(m, φ)	M × (E × Z → B) → ∅	Apply φ to all entries and their ranks in the map
to_seq(m)	M → array	Output all elements in m to an array
keys(m)	M → array	Output all keys in m to an array
insert(m, e)	M × E → M	Insert an entry e in m
join2(m1, m2)	M × M → M	Concatenate two sequences
size(m)	M → Z	The size of m
clear(m)	M → M	Clear m to an empty sequence (tree)
reserve(n)	Z → ∅	Reserve n tree nodes
finish		Static function. Collect related tree nodes at the end

For Ordered Sets:

M is the sequence type. E = K. Z is the integer set.
All functions on sequences can also be applied on sets with the same definition.

select(m,i)	M × Z → E	The i-th element in m
first(m)	M → E	The first element in m
last(m)	M → E	The last element in m
previous(m, k)	M × K → E	The largest element in m with key smaller than k
next(m, k)	M × K → E	The smallest element in m with key larger than k
find(m, k)	M × K → bool	Determine if k is in m
insert(m, e)	M × E → M	Insert an entry e in m
delete(m, k)	M × K → M	Delete they key k in m
map_union(m1, m2)	M × M → M	Take the union of two sets
map_intersection(m1, m2)	M × M → M	Take the intersection of two sets
map_difference(m1, m2)	M × M → M	Take the difference of two sets
multi_insert(m, a)	M × array → M	Insert an array of entries into m
range(m, k1, k2)	M × K × K → M	All entries in m in the key range [k1, k2]
upTo(m, k)	M × K × K → M	All entries in m in with keys no greater than k
DownTo(m, k)	M × K × K → M	All entries in m with keys no less than k

For Ordered Maps:

M is the sequence type. E = K × V. Z is the integer set.
All functions on sequences and ordered sets can also be applied on maps with the same definition.

find(m, k)	M × K → V	The value of k in m
insert(m, e, φ)	M × E × (V × V) → M	Insert an entry e in m. If the key of e already exists in m, combine the the original value in the map with the value of e
map_union(m1, m2, φ)	M × M × (V × V) → M	Take the union of two sets. If there are duplicate keys in both m1 and m2, combine their values using φ
map_intersection(m1, m2, φ)	M × M × (V × V) → M	Take the intersection of two sets. If there are duplicate keys in both m1 and m2, combine their values using φ
map_difference(m1, m2)	M × M → M	Take the difference of two sets
multi_insert(m, a, φ)	M × array → M	Insert an array of entries into m. If there are duplicate keys in a, or any key in a has already appeared in m, combine their values using φ
pam_map(a, φ)	M × array → M	Constructor. Build an ordered map (tree) from an array of entries. If there are duplicate keys in a, combine their values using φ

For Augmented Maps:

M is the augmented map type. E = K × V. Z is the integer set.
All functions on sequences, ordered sets and ordered maps can also be applied on augmented maps with the same definition.

aug_val(m)	M → A	The augemented value of m
aug_left(m, k)	M × K → A	The augmented value of all entries with keys no more than k
aug_right(m, k)	M × K → A	The augmented value of all entries with keys no less than k
aug_range(m, k1, k2)	M × K × → A	The augmented value of all entries within key range [k1, k2]
aug_select(m, φ)	M × (A → bool) → E	The first entry e that makes φ(aug_left(m, key(e))) true. Only applicable when φ(a1) ⇒ φ(f(a1, a2)). E.g., when the combine function is addition and φ(x) determines if x is greater than some constant.
aug_filter(m, h)	M × (A → bool) → M	Equivalent to filter(m,h') for h': K × V → bool, where h(g(k,v)) ⇒ h'(k,v). Only applicable when h(a) or h(b) → h(f(a,b)).
aug_sum_range(m, k1, k2, h1, h2, zero)	M × K × K × (V × B → B) × (A × B → B) × B → M	For all entries in m within key range [k1, k2], add their values to "zero" by h1. Only applicable when adding values using h1 is equivalent to adding augmented values by h2.