identify positions uniquely
(generally not sequential numbers)
see POPL paper
public func empty<X>() : Sequence<X>
public func make<X>(data : X) : Sequence<X>
public func size<X>(s : Sequence<X>) : Nat
public func get<X>(s : Sequence<X>, pos : Nat) : ?X
public func split<X>(s : Sequence<X>, size1 : Nat) : (Sequence<X>, Sequence<X>)
split sequence into a pair where the first has the given size
for insufficient sequence values, the first result is the full input, and the second result is empty
public func slice<X>(
s : Sequence<X>,
start : Nat,
size : Nat
) : (Sequence<X>, Sequence<X>, Sequence<X>)
public func peekBack<X>(seq : Sequence<X>) : ?X
public func peekFront<X>(seq : Sequence<X>) : ?X
public func binaryOp<X>(
s : Sequence<X>,
zero : X,
bop : (X, X) -> X
) : X
Perform an associative, binary operation over the binary tree.
Like monoid, but simpler (common input and output type).
public func monoid<X, Y>(
s : Sequence<X>,
id : Y,
leaf : X -> Y,
binOp : (Y, Y) -> Y
) : Y
Transform sequence into monoid structure
The monoid's id element stands in for empty sequences.
The leaf function maps a leaf element to a monoid element.
The function binOp gives the monoid's binary operation over elements.
public func foldUp<X, Y>(
s : Sequence<X>,
empty : Y,
leaf : X -> Y,
branch : (Branch<X>, Y, Y) -> Y
) : Y
Like monoid, except that branch function gets full branch node info
public func branchChild<X>(
b : Branch<X>,
rank : {#fst; #snd},
dir : {#fwd; #bwd}
) : Sequence<X>
Relate child order and iteration order.
(all defined here, in code)
public func foldDir<X, Y>(
s : Sequence<X>,
dir : {#fwd; #bwd},
empty : Y,
leaf : ?((Y, X) -> Y),
preBranch : ?((Y, Branch<X>) -> Y),
midBranch : ?((Y, Branch<X>) -> Y),
postBranch : ?((Y, Branch<X>) -> Y)
) : Y
Fold with directed sequential dependencies.
Folds the binary tree into an accumulated value, forward or backward.
Each function is optional, and behaves like the identity function when null
.
Branch case accumulates across five steps:
- two subtrees of the branch, and
- three points surrounding them (pre, mid, post branch).
Leaf case accepts an accumulator, initially empty
.
public func iter<X>(s : Sequence<X>, dir : {#fwd; #bwd}) : Iter.Iter<X>
public func fromAssocList<K, V, T>(l : List.List<(Trie.Key<K>, V)>, kv : (Trie.Key<K>, V) -> T) : Sequence<T>
public func fromTrie<K, V, T>(t : Trie.Trie<K, V>, kv : (Trie.Key<K>, V) -> T) : Sequence<T>