Sequence

type Sequence<X> = {#branch : Branch<X>; #leaf : X; #empty}

type Branch<X> = { left : Sequence<X>; right : Sequence<X>; level : Level; size : Nat }

type Pos = Nat

identify positions uniquely

(generally not sequential numbers)

type Level = Nat32

see POPL paper

type Stream<X> = Stream.Stream<X>

public func empty<X>() : Sequence<X>

public func make<X>(data : X) : Sequence<X>

public func branch<X>(
  l : Sequence<X>,
  midLev : Level,
  r : Sequence<X>
) : Sequence<X>

public func makeAppend<X>(levels : Stream<Level>) : <X>(Sequence<X>, Sequence<X>) -> Sequence<X>

public func defaultAppend<X>() : <X>(Sequence<X>, Sequence<X>) -> Sequence<X>

public func appendLevel<X>(
  s1 : Sequence<X>,
  midLev : Nat32,
  s2 : Sequence<X>
) : Sequence<X>

public func fromArray<X>(array : [X], levels : Stream<Level>) : 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 pushBack<X>(
  seq : Sequence<X>,
  level : Level,
  data : X
) : Sequence<X>

public func popFront<X>(seq : Sequence<X>) : ?(X, Sequence<X>)

public func popBack<X>(seq : Sequence<X>) : ?(Sequence<X>, X)

public func peekBack<X>(seq : Sequence<X>) : ?X

public func peekFront<X>(seq : Sequence<X>) : ?X

public func pushFront<X>(
  data : X,
  level : Level,
  seq : Sequence<X>
) : Sequence<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>

public func tokens<X>(
  s : Sequence<X>,
  isDelim : X -> Bool,
  levels : Stream<Level>
) : Sequence<Sequence<X>>

separate into (nested) sub-sequences by looking for sub-sequence delimiter elements (omitted from output)