Chain

enum Chain[t: Type] with SendableSource

case Emptycase One(t)case Chain(Chain[t], Chain[t])

The Chain type.

A chain is a list represented as an unbalanced binary tree. It supports efficient append and "snoc" - appending elements at the tail of the list.

Note - the constructors Empty, One and Chain should not be used directly.

Definitions

def ap(f: Chain[a -> b \ ef], x: Chain[a]): Chain[b] \ ef Source

Apply every function from f to every argument from x and return a chain with all results. For f = f1, f2, ... and x = x1, x2, ... the results appear in the order f1(x1), f1(x2), ..., f2(x1), f2(x2), ....

def append(c1: Chain[a], c2: Chain[a]): Chain[a] Source

Returns a new chain formed by appending the chains c1 and c2.

def compare(c1: Chain[a], c2: Chain[a]): Comparison with Order[a] Source

Compares chains c1 and c2 lexicographically.

def cons(x: a, c: Chain[a]): Chain[a] Source

Add element x to the left end of chain c.

def count(f: a -> Bool \ ef, c: Chain[a]): Int32 \ ef Source

Returns the number of elements in c that satisfy the predicate f.

def dropLeft(n: Int32, c: Chain[a]): Chain[a] Source

Returns c without the first n elements.

Returns Nil if n > length(c). Returns c if n < 0.

def dropRight(n: Int32, c: Chain[a]): Chain[a] Source

Returns c without the last n elements.

Returns Nil if n > length(c). Returns c if n < 0.

def dropWhileLeft(f: a -> Bool \ ef, c: Chain[a]): Chain[a] \ ef Source

Returns c without the longest prefix that satisfies the predicate f.

def dropWhileRight(f: a -> Bool \ ef, c: Chain[a]): Chain[a] \ ef Source

Returns c without the longest suffix that satisfies the predicate f.

def empty(_unit: Unit): Chain[a] Source

Return the empty chain.

def enumerator(rc: Region[r], c: Chain[a]): Iterator[(Int32, a), r, r] \ r Source

Returns an iterator over c zipped with the indices of the elements.

def equals(c1: Chain[a], c2: Chain[a]): Bool with Eq[a] Source

Returns true if and only if c1 and c2 and equal.

def exists(f: a -> Bool \ ef, c: Chain[a]): Bool \ ef Source

Returns true if and only if at least one element in c satisfies the predicate f.

Returns false if c is empty.

def filter(f: a -> Bool \ ef, c: Chain[a]): Chain[a] \ ef Source

Returns a list of every element in c that satisfies the predicate f.

The function f must be pure.

def filterMap(f: a -> Option[b] \ ef, c: Chain[a]): Chain[b] \ ef Source

Collects the results of applying the partial function f to every element in c.

def find(f: a -> Bool, c: Chain[a]): Option[a] Source

Alias for findLeft.

The function f must be pure.

def findLeft(f: a -> Bool, c: Chain[a]): Option[a] Source

Optionally returns the first element of c that satisfies the predicate f when searching from left to right.

The function f must be pure.

def findMap(f: a -> Option[b] \ ef, c: Chain[a]): Option[b] \ ef Source

Returns the first non-None result of applying the partial function f to each element of c.

Returns None if every element of c is None.

def findRight(f: a -> Bool, c: Chain[a]): Option[a] Source

Optionally returns the first element of c that satisfies the predicate f when searching from right to left.

The function f must be pure.

def flatMap(f: a -> Chain[b] \ ef, c: Chain[a]): Chain[b] \ ef Source

Returns the result of applying f to every element in c and concatenating the results.

def flatten(c: Chain[Chain[a]]): Chain[a] Source

Returns the concatenation of the elements in c.

def foldLeft(f: b -> (a -> b \ ef), s: b, c: Chain[a]): b \ ef Source

Applies f to a start value s and all elements in c going from left to right.

That is, the result is of the form: f(...f(f(s, x1), x2)..., xn).

def foldMap(f: a -> b \ ef, c: Chain[a]): b \ ef with Monoid[b] Source

Returns the result of mapping each element and combining the results.

def foldRight(f: a -> (b -> b \ ef), s: b, c: Chain[a]): b \ ef Source

Applies f to a start value s and all elements in c going from right to left.

That is, the result is of the form: f(x1, ...f(xn-1, f(xn, s))...).

def foldRightWithCont(f: a -> ((Unit -> b \ ef) -> b \ ef), z: b, c: Chain[a]): b \ ef Source

Applies f to a start value z and all elements in c going from right to left.

That is, the result is of the form: f(x1, ...f(xn-1, f(xn, z))...). A foldRightWithCont allows early termination by not calling the continuation.

def forAll(f: a -> Bool \ ef, c: Chain[a]): Bool \ ef Source

Returns true if and only if all elements in c satisfy the predicate f.

Returns true if c is empty.

def forEach(f: a -> Unit \ ef, c: Chain[a]): Unit \ ef Source

Applies f to every element of c.

def forEachWithIndex(f: Int32 -> (a -> Unit \ ef), c: Chain[a]): Unit \ ef Source

Applies f to every element of c along with that element's index.

def head(c: Chain[a]): Option[a] Source

Returns Some(x) if x is the first element of c.

Returns None if c is empty.

def indexOf(a: a, c: Chain[a]): Option[Int32] with Eq[a] Source

Optionally returns the position of a in c.

def init(c: Chain[a]): Option[Chain[a]] Source

Returns the subchain of c without the last element. Returns None if the chain c is empty.

def intersperse(a: a, c: Chain[a]): Chain[a] Source

Returns c with a inserted between every two adjacent elements.

def isEmpty(c: Chain[a]): Bool Source

Returns true if and only if c is the empty chain.

def iterator(rc: Region[r], c: Chain[a]): Iterator[a, r, r] \ r Source

Returns an iterator over c.

def join(sep: String, c: Chain[a]): String with ToString[a] Source

Returns the concatenation of the string representation of each element in c with sep inserted between each element.

def joinWith(f: a -> String \ ef, sep: String, c: Chain[a]): String \ ef Source

Returns the concatenation of the string representation of each element in c according to f with sep inserted between each element.

def last(c: Chain[a]): Option[a] Source

Returns Some(x) if x is the last element of c.

Returns None if c is empty.

def length(c: Chain[a]): Int32 Source

Returns the length of c.

def map(f: a -> b \ ef, c: Chain[a]): Chain[b] \ ef Source

Returns the result of applying f to every element in c.

That is, the result is of the form: f(x1) :: f(x2) :: ....

def mapAccumLeft(f: s -> (a -> (s, b) \ ef), start: s, c: Chain[a]): (s, Chain[b]) \ ef Source

mapAccumLeft is a stateful version of map. The accumulating paramter s is updated at each step in a left-to-right traversal.

def mapAccumRight(f: s -> (a -> (s, b) \ ef), start: s, c: Chain[a]): (s, Chain[b]) \ ef Source

mapAccumRight is a stateful version of map. The accumulating parameter s is updated at each step in a right-to-left traversal.

def mapWithIndex(f: Int32 -> (a -> b \ ef), c: Chain[a]): Chain[b] \ ef Source

Returns the result of applying f to every element in c along with that element's index.

That is, the result is of the form: f(x1, 0) :: f(x2, 1) :: ....

def memberOf(a: a, c: Chain[a]): Bool with Eq[a] Source

Returns true if and only if c contains the element a.

def range(b: Int32, e: Int32): Chain[Int32] Source

Returns a list of all integers between b (inclusive) and e (exclusive).

Returns Nil if b >= e.

def repeat(n: Int32, a: a): Chain[a] Source

Returns a list with the element a repeated n times.

Returns Nil if n < 0.

def reverse(c: Chain[a]): Chain[a] Source

Returns the reverse of c.

def scan(f: b -> (a -> b \ ef), s: b, c: Chain[a]): Chain[b] \ ef Source

Alias for scanLeft.

def scanLeft(f: b -> (a -> b \ ef), s: b, c: Chain[a]): Chain[b] \ ef Source

Accumulates the result of applying f to c going left to right.

That is, the result is of the form: s :: f(s, x1) :: f(f(s, x1), x2) ....

def scanRight(f: a -> (b -> b \ ef), s: b, c: Chain[a]): Chain[b] \ ef Source

Accumulates the result of applying f to c going right to left.

That is, the result is of the form: ... f(xn-1, f(xn, s)) :: f(xn, s) :: s.

def sequence(c: Chain[m[a]]): m[Chain[a]] with Applicative[m] Source

Returns the result of running all the actions in the chain c.

def shuffle(rnd: Random, c: Chain[a]): Chain[a] \ IO Source

Shuffles c using the Fisher–Yates shuffle.

def singleton(x: a): Chain[a] Source

Return the singleton chain with element x.

def snoc(c: Chain[a], x: a): Chain[a] Source

Add element x to the right end of chain c.

def sort(c: Chain[a]): Chain[a] with Order[a] Source

Sort chain c so that elements are ordered from low to high according to their Order instance.

The sort is not stable, i.e., equal elements may appear in a different order than in the input c.

The sort implementation is a Quicksort.

def sortBy(f: a -> b, c: Chain[a]): Chain[a] with Order[b] Source

Sort chain c so that elements are ordered from low to high according to the Order instance for the values obtained by applying f to each element.

The sort is not stable, i.e., equal elements may appear in a different order than in the input c.

The sort implementation is a Quicksort.

def sortWith(cmp: a -> (a -> Comparison), c: Chain[a]): Chain[a] Source

Sort chain c so that elements are ordered from low to high according to the comparison function cmp.

The sort is not stable, i.e., equal elements may appear in a different order than in the input c.

The sort implementation is a Quicksort.

def sum(c: Chain[Int32]): Int32 Source

Returns the sum of all elements in the chain c.

def sumWith(f: a -> Int32 \ ef, c: Chain[a]): Int32 \ ef Source

Returns the sum of all elements in the chain c according to the function f.

def takeLeft(n: Int32, c: Chain[a]): Chain[a] Source

Returns the first n elements of c.

Returns c if n > length(c). Returns Nil if n < 0.

def takeRight(n: Int32, c: Chain[a]): Chain[a] Source

Returns the last n elements of c.

Returns c if n > length(c). Returns Nil if n < 0.

def takeWhileLeft(f: a -> Bool \ ef, c: Chain[a]): Chain[a] \ ef Source

Returns the longest prefix of c that satisfies the predicate f.

def takeWhileRight(f: a -> Bool \ ef, c: Chain[a]): Chain[a] \ ef Source

Returns the longest suffix of c that satisfies the predicate f.

def toArray(rc: Region[r], c: Chain[a]): Array[a, r] \ r Source

Returns the chain c as an array.

def toList(c: Chain[a]): List[a] Source

Returns c as a list.

def toMap(c: Chain[(a, b)]): Map[a, b] with Order[a] Source

Returns the chain of pairs c that represents an association list as a map.

If c contains multiple mappings with the same key, toMap does not make any guarantees about which mapping will be in the resulting map.

def toMutDeque(rc: Region[r], c: Chain[a]): MutDeque[a, r] \ r Source

Returns c as a MutDeque.

def toMutList(rc: Region[r], c: Chain[a]): MutList[a, r] \ r Source

Returns c as a mutable list.

def toNec(c: Chain[a]): Option[Nec[a]] Source

Returns the chain c as a Nec.

def toNel(c: Chain[a]): Option[Nel[a]] Source

Returns the chain c as a Nel.

def toSet(c: Chain[a]): Set[a] with Order[a] Source

Returns the list c as a set.

def toVector(c: Chain[a]): Vector[a] Source

Returns the chain c as a vector.

def traverse(f: a -> m[b] \ ef, c: Chain[a]): m[Chain[b]] \ ef with Applicative[m] Source

Returns the result of applying the applicative mapping function f to all the elements of the chain c.

def unzip(c: Chain[(a, b)]): (Chain[a], Chain[b]) Source

Returns a pair of chains, the first containing all first components in c and the second containing all second components in c.

def viewLeft(c: Chain[a]): ViewLeft[a] Source

Deconstruct a Chain from left-to-right.

Returns ViewLeft(x, rs) if the chain is non-empty, where x is the leftmost element of the chain c, and rs is the rest of the chain.

Returns ViewLeft.NoneLeft if the chain is empty.

def viewRight(c: Chain[a]): ViewRight[a] Source

Deconstruct a Chain from right-to-left.

Returns ViewRight(rs, x) if the chain is non-empty, where x is the rightmost element of the chain c`, and rs is the front of the chain.

Returns ViewRight.NoneRight if the chain is empty.

def zip(c1: Chain[a], c2: Chain[b]): Chain[(a, b)] Source

Returns a chain where the element at index i is (a, b) where a is the element at index i in c1 and b is the element at index i in c2.

If either c1 or c2 becomes depleted, then no further elements are added to the resulting chain.

def zipWith(f: a -> (b -> c \ ef), c1: Chain[a], c2: Chain[b]): Chain[c] \ ef Source

Returns a chain where the element at index i is f(a, b) where a is the element at index i in c1 and b is the element at index i in c2.

If either c1 or c2 becomes depleted, then no further elements are added to the resulting chain.

def zipWithA(f: a -> (b -> m[c] \ ef), xs: Chain[a], ys: Chain[b]): m[Chain[c]] \ ef with Applicative[m] Source

Generalize zipWith to an applicative functor f.

def zipWithIndex(c: Chain[a]): Chain[(Int32, a)] Source

Returns a chain where each element e is mapped to (i, e) where i is the index of e.