std/sequence
Finite persistent indexed deques, implemented as strict measured finger
trees. End edits, indexing, splitting, and concatenation take O(log(n+1))
node work in every history. Whole walks and bottom-up construction are O(n).
equal compares elements; ordinary ==, inspect, and hash also observe
the private shape. Equal element lists need not give interchangeable dict
keys. Use to_list as a key when element equality is required.
Sequence
An immutable sequence of elements. Its constructors and cached sizes are private. Old versions remain usable after every edit.
Sequence(A) = (Tree(A)) new
An empty sequence. This function may be used at any element type.
new = <A>() -> Sequence(A) { Sequence(EmptyTree) } wrap
A sequence of one item.
wrap = <A>(item : A) -> Sequence(A) { Sequence(Single(Leaf(item))) } from_list
Builds a sequence in O(n) work, grouping nodes from the bottom up.
from_list = <A>(items : List(A)) -> Sequence(A) { to_list
Lists all elements in order with one tree walk.
to_list = <A>(sequence : Sequence(A)) -> List(A) { length
The cached number of elements, in O(1) work.
length = <A>(sequence : Sequence(A)) -> Int { is_empty
Whether there are no elements.
is_empty = <A>(sequence : Sequence(A)) -> Bool { length(sequence) == 0 } first
The first item, or None.
first = <A>(sequence : Sequence(A)) -> Option(A) { last
The last item, or None.
last = <A>(sequence : Sequence(A)) -> Option(A) { push_front
Adds an item at the front, preserving the old sequence.
push_front = <A>(to : Sequence(A), item : A) -> Sequence(A) { push_back
Adds an item at the back, preserving the old sequence.
push_back = <A>(to : Sequence(A), item : A) -> Sequence(A) { pop_front
Removes the first item. The item comes before the remaining sequence.
pop_front = <A>(from : Sequence(A)) -> Option((A, Sequence(A))) { pop_back
Removes the last item. The item comes before the remaining sequence.
pop_back = <A>(from : Sequence(A)) -> Option((A, Sequence(A))) { at
The item at a zero-based index. Negative and out-of-range indices miss.
at = <A>(sequence : Sequence(A), index : Int) -> Option(A) { set
Replaces one item, preserving length. Invalid indices give None.
set = <A>(in : Sequence(A), index : Int, value : A) -> Option(Sequence(A)) { append
Concatenates two sequences by joining their fringes and sharing subtrees.
append = <A>(first : Sequence(A), second : Sequence(A)) -> Sequence(A) { split
Splits before at, clamped to [0, length].
split = <A>(sequence : Sequence(A), at : Int) -> (Sequence(A), Sequence(A)) { take
The first up_to items, clamping negative counts to zero.
take = <A>(from : Sequence(A), up_to : Int) -> Sequence(A) { drop
Drops the first up_to items, clamping negative counts to zero.
drop = <A>(from : Sequence(A), up_to : Int) -> Sequence(A) { reverse
Reverses element order by mirroring the tree once.
reverse = <A>(sequence : Sequence(A)) -> Sequence(A) { map
Eagerly transforms every item, left to right, stopping on the first error.
map = <A, B, N>(over : Sequence(A), with : (A) <- N -> B) -> Sequence(B) { fold
Combines items left to right, passing (accumulator, item) to the callback.
fold = <A, Acc, N>( each
Calls a function on each item left to right and discards its result.
each = <A, B, N>(over : Sequence(A), with : (A) <- N -> B) -> Nil { equal
Compares lengths and elements using ==, independently of tree shape.
equal = <A>(first : Sequence(A), second : Sequence(A)) -> Bool {