Fuzion Logo
fuzion-lang.dev — The Fuzion Language Portal
JavaScript seems to be disabled. Functionality is limited.

sorted_array

container.sorted_array

(T 
type
:
Type, from Sequence T, less_or_equal Binary bool T T)
:
array T
 is
sorted_array -- sorted one-dimensional immutable array

This takes an unsorted array and a compare function as an arguments and
returns a sorted one.

Non-mutating heap sort is used internally. This gives guaranteed performance in
O(n log n) comparisons and assignments for an array of size n.

This is a little wasteful on allocated memory, which is also O(n log n) since
partially sorted arrays are thrown away. This might be improved to use an
in-place heap sort to bring allocated memory down to O(n).

Type Parameters

array element type

Functions

convert a Sequence's head into a 3-tuple.

ex.

chop this Sequence into tuples of size 3. In case
the number of elements is not a multiple of 3,
the last count % 3 elements will be dropped silently.

ex.

convert a Sequence's head into a 4-tuple.

ex.

chop this Sequence into tuples of size 4. In case
the number of elements is not a multiple of 4,
the last count % 4 elements will be dropped silently.

ex.

convert a Sequence's head into a 5-tuple.

ex.

chop this Sequence into tuples of size 5. In case
the number of elements is not a multiple of 5,
the last count % 5 elements will be dropped silently.

ex.

convert a Sequence's head into a 6-tuple.

ex.

chop this Sequence into tuples of size 6. In case
the number of elements is not a multiple of 6,
the last count % 6 elements will be dropped silently.

ex.

 => 
array T
[Inherited from  Sequence]
collect the contents of this Sequence into an array
create an array backed version of this sequence in case this is not array
backed. This will ensure that operations like index[] or drop perform
in constant time.

returns Sequence.this if is_array_backed.
wrap this sequence into an equatable type.

This requires the underlying element type to be equatable.
 => 
list T
[Inherited from  abstract_array]
create a list from this array

redefines:

(i i32)
 => 
list T
[Inherited from  abstract_array]
create a list from this array starting at the given index
(LM 
type
:
Type)
 => 
LM.array T
[Inherited from  abstract_array]
returns a copy of this array as a mutable array
wrap this sequence into an orderable type.

This requires the underlying element type to be orderable.

An empty `Sequence` is always less or equal to any other `Sequence`. Two non
empty `Sequence`s whose first elements are unequal are ordered by the
order of those two elements. If those two elements are equal, the tail
of both `Sequence`s will be used to find the order.
 => 
String
[Inherited from  Sequence]
create a string representation of this Sequence including all the string
representations of its contents, separated by ',' and enclosed in '['
and ']'.

In case this Sequence is known to be `finite` or has at most (Sequence T).type
.AS_STRING_NON_FINITE_MAX_ELEMENTS elements, all elements will be shown in the
resulting string. Otherwise, only the first elements will be shown followed by
",…" as in "[1,2,3,4,5,6,7,8,9,10,…]".

To force printing of all elements of a finite `Sequence` for which `finite` is
false (which may be the case since a Sequence in general might not know that it
if finite), you may use `as_string_all`.

redefines:

(sep String)
 => 
String
[Inherited from  Sequence]
create a string representation of this Sequence including all the string
representations of its contents, separated by 'sep'.

NOTE: In case this Sequence is not finite, this will attempt to create an
infinitely long string resulting in failure due to resource exhaustion.
 => 
String
[Inherited from  Sequence]
create a string representation of this Sequence including all the string
representations of its contents, separated by ", " and enclosed in '['
and ']'.

NOTE: In case this Sequence is not finite, this will attempt to create an
infinitely long string resulting in failure due to resource exhaustion.
call 'as_string' on the elements
 => 
tuple T T
[Inherited from  Sequence]
convert a Sequence's head into a 2-tuple.

ex.

chop this Sequence into tuples of size 2. In case
the number of elements is not a multiple of 2,
the last count % 2 elements will be dropped silently.

ex.

 => 
option T
[Inherited from  Sequence]
the arithmetic mean of the sequence
https://en.wikipedia.org/wiki/Arithmetic_mean
create a new Sequence that contains the first elements of
this Sequence for which 'f e' is false
(chunk_size i32)
 => 
Sequence (Sequence T)
[Inherited from  Sequence]
chop this Sequence into chunks of `chunk_size`.
the last chunk may be smaller than `chunk_size`.
(U 
type
:
Type, V 
type
:
Type, b Sequence U, f Binary V T U)
 => 
Sequence V
[Inherited from  Sequence]
create a new Sequence from the result of applying 'f' to the
elements all combinations of elements of this Sequence and
all elements of 'b' iterating of 'b' repeatedly as follows

(s Sequence T)
 => 
Sequence T
[Inherited from  Sequence]
create a Sequence that consists of all the elements of this Sequence followed
by all the elements of s

General case: This will perform `as_list.concat_list` in case one of
`Sequence.this` or `s`is not known to be finite (`finite != trit.yet`) or
`s.count` is larger than `count`.

Otherwise, if `Sequence.this` or `s` is empty, the result will be `s` or
`Sequence.this`, respectively.

In all other cases, an instance of `container.expanding_array` will be
created and the elements of `this` and `s` will be added. Note that
`concat` is redefined for `container.expanding_array` to achieve
average `O(1)` performance for repeated concatenation with `s.count < c`
for some constant `c`.

Performance: O(count + s.count) worst case, O(s.count) average case

NOTE: For repeated concatenation `a.concat b` that fall into the general
case the resulting sequence will have iteration performance in `O(n²)`
for `n` concatenation. Explicitly use `container.expanding_array` to
avoid this. This implementation cannot do this automatically since
repeated wrapping of `a` into an `expanding_array` would result
in `O(n²)` performance for the concatenations.
(x T)
 => 
bool
[Inherited from  Sequence]
does the Sequence contain element x?
(f Unary bool T)
 => 
i32
[Inherited from  Sequence]
count the number of elements in this Sequence that match the
given predicate. Note that this typically
runs forever if executed on an endless Sequence.
 => 
i32
[Inherited from  abstract_array]
redefines Sequence.count for array,
reducing complexity from O(n) to O(1).
(l Sequence T)
 => 
i32
[Inherited from  Sequence]
get the number of non-overlapping matches of l within this
get the number of matches of l
 => 
Sequence T
[Inherited from  Sequence]
create a Sequence that repeats the current Sequence indefinitely. In case 'Sequence.this'
is empty, returns 'nil'
 => 
Sequence T
[Inherited from  Sequence]
filter out consecutive duplicate elements.

Keep the order of elements unchanged.

ex.

filter out consecutive duplicate elements using the
given relation.

Keep the order of elements unchanged.

ex.

(n i32)
 => 
Sequence T
[Inherited from  abstract_array]
create a list that consists of the elements of this Sequence except the first
n elements

For arrays, this has performance in O(1).

redefines:

Lazily drop the first elements of this Sequence for which predicate 'p' holds.
 => 
Type
[Inherited from  Any]
Get the dynamic type of this instance. For value instances `x`, this is
equal to `type_of x`, but for `x` with a `ref` type `x.dynamic_type` gives
the actual runtime type, while `type_of x` results in the static
compile-time type.

There is no dynamic type of a type instance since this would result in an
endless hierarchy of types. So for Type values, dynamic_type is redefined
to just return Type.type.
get a list of tuples of indices and elements in this array
 => 
T
[Inherited from  Sequence]
the euclidean norm of this sequence
i.e. the square of the sum of squares of this sequence
filter elements using predicate f
values for which f is false are dropped
(pattern Sequence T)
 => 
option i32
[Inherited from  Sequence]
get the index of pattern within this Sequence or nil if it does not exist

uses the Knuth-Morris-Pratt algorithm
port of racket code from this paper:
https://www.cambridge.org/core/services/aop-cambridge-core/content/view/8EFA77D663D585B68630E372BCE1EBA4/S0956796824000017a.pdf/knuth-morris-pratt-illustrated.pdf

worst-case performance: O( seq_length ) + O( pattern_length )
worst-case space complexity: O( pattern_length )
find index of key for which cmp returns 0

The guaranteed performance is in O(log n) comparisons.

result is the index where cmp results in 0 or nil if no such index
was found in this array. In case several instance equal match,
the index of one matching key will be returned, but is not
specified which one.

NYI: CLEANUP: find better name
find index of given key using binary search

The guaranteed performance is in O(log n) comparisons.

result is the index where key was found or nil if key is not
in this array. In case several instance equal to key are in
this sorted_array, the index of one of the matching keys will be
returned, but is not specified which one.
 => 
trit
[Inherited from  abstract_array]
is this sequence known to be finite? For infinite sequences, features like
count diverge.
 => 
option T
[Inherited from  Sequence]
get the first element of this Sequence
(default T)
 => 
T
[Inherited from  Sequence]
get the first element of this Sequence or default if sequence is empty
(B 
type
:
Type, f Unary (Sequence B) T)
 => 
Sequence B
[Inherited from  Sequence]
map each element of this Sequence to Sequence
Then flatten the result by one level,
essentially combining all the sequences.
(m Monoid T)
 => 
T
[Inherited from  abstract_array]
fold the elements of this array using the given monoid.

e.g., to sum the elements of an array of i32, use a.fold i32.sum

redefines:

(i i32, s T, m Monoid T)
 => 
T
[Inherited from  abstract_array]
fold the elements of this array using the given monoid and initial value

Used to fold an array tail-recursively
(f Binary T T T)
 => 
T
[Inherited from  Sequence]
fold the elements of this non-empty Sequence using the given function

e.g., to find the minimum of a Sequence of i32, use `s.fold1 (<=)`
(B 
type
:
Type, e B, f Binary B B T)
 => 
B
[Inherited from  Sequence]
fold the elements of this Sequence using the given function and initial
value.

In case this Sequence is empty, the result is `e`.

e.g., to find the product of a Sequence of i32, use `s.foldf (*) 1`
(m Monoid T)
 => 
T
[Inherited from  Sequence]
fold the elements of this Sequence using the given monoid right-to-left.

e.g., to concat the elements of a Sequence `s` of Strings, use `s.foldr String.concat`
(s T, m Monoid T)
 => 
T
[Inherited from  Sequence]
fold the elements of this Sequence using the given monoid and initial value right-to-left.

Used to fold a Sequence tail-recursively
(f Binary T T T)
 => 
T
[Inherited from  Sequence]
fold the elements of this non-empty Sequence using the given function right-to-left

e.g., to concat the elements of a non-empty Sequence of Sequeces, use `foldr1 (++)`
(B 
type
:
Type, e B, f Binary B T B)
 => 
B
[Inherited from  Sequence]
fold the elements of this Sequence using the given function right-to-left.

e.g., to concat the elements of a Sequence of Sequences, use `foldrf [] (++)`
apply f to all elements in this array

redefines:

(f Unary bool T)
 => 
unit
[Inherited from  Sequence]
apply 'f' to each element 'e' as long as 'f e'
group the elements of this sequence by a key of type K
using a mutable_tree_map

f determines the key of an element
group the elements of this sequence by a key of type K
using a custom Mutable_Map

f determines the key of an element
(K 
type
:
Type, B 
type
:
Type, key_f Unary K T, f Unary B T)
 => 
container.Map K (Sequence B)
[Inherited from  Sequence]
group the elements of this sequence by a key of type and applies function f to all elements

example: group characters by category and add underscores around each character

values array codepoint := ["A", "1", "b", "?", "X", "4"]

classify (c codepoint) String => c.is_ascii_letter ? "letter" : c.is_ascii_digit ? "digit" : "other"

values.group_map String String classify (x->"_{x}_")

=> {(digit => [_1_, _4_]), (letter => [_A_, _b_, _X_]), (other => [_?_])}
(K 
type
:
Type, B 
type
:
Type, key_f Unary K T, f Unary B T, reduce_f Binary B B B)
 => 
container.Map K B
[Inherited from  Sequence]
group elements using key_f and
reduce elements within a group by first applying f and then using reduce_f to reduce

example: count occurrences of letters, numbers and other characters


=> {(digit => 2), (letter => 3), (other => 1)}
(K 
type
:
Type, key_f Unary K T, reduce_f Binary T T T)
 => 
container.Map K T
[Inherited from  Sequence]
group elements using key_f and reduce elements within a group using reduce_f
in contrast to the more general version, values in the resulting map must have the same type as in the input

example: sum even and odd numbers individually

(0..10).group_reduce String (x -> x%%2 ? "even" : "odd") (+)

=> {(even => 30), (odd => 25)}
get a function that, given an index, returns the element at that index
(i i32)
 => 
T
[Inherited from  array]
get the contents of this array at the given index
(x T)
 => 
option i32
[Inherited from  Sequence]
determine the index of element x within this list. 0 if x is at the
head of the list, 1 if it comes directly after head, etc. nil if x is
not in the list.
adds the corresponding index to
every element in the sequence
(I 
type
:
Type, start_idx I)
 => 
Sequence (tuple I T)
[Inherited from  Sequence]
adds an index to every element
in the sequence starting at start_idx
a sequence of all valid indices to access this array. Useful e.g., for
`for`-loops:

(n i32)
 => 
Sequence T
[Inherited from  Sequence]
create a Sequence that repeats the current Sequence `n` times.
infix operand synonym for concat
(B 
type
:
Type, f Unary B T)
 => 
Sequence B
[Inherited from  Sequence]
map the Sequence to a new Sequence applying function f to all elements

This is an infix operator alias of map enabling piping code like


to obtain 290,280,270,...200

Note that map and therefore also this operator is lazy, so


will not print anything while


will print the elements since `for_each` is not lazy.
(f Unary bool T)
 => 
bool
[Inherited from  Sequence]
check if predicate f holds for all elements
(f Unary bool T)
 => 
bool
[Inherited from  Sequence]
check if predicate f holds for at least one element
(at i32, v T)
 => 
Sequence T
[Inherited from  Sequence]
insert element v at position at
apply transducer to sequence, returning a sequence of results

example usage:
human(age i32) is
ages := map (Sequence i32) human i32 (x -> x.age)
gt_ten := filter (Sequence i32) i32 (x -> x > 10)
xf := ages ∘ gt_ten
say ([human 4, human 12, human 30].into xf) # [12,30]
is this Sequence known to be array backed? If so, this means that operations
like index[] are fast.
 => 
bool
[Inherited from  Sequence]
is this Sequence empty?
 => 
bool
[Redefinition of  Sequence.is_sorted]
is this Sequence sorted?

redefines:

(i i32)
 => 
bool
[Inherited from  abstract_array]
check if argument is a valid index in this array.

Unlike for general Sequences, this performs in O(1).
 => 
option T
[Inherited from  Sequence]
get the last element of this Sequence

This may take time in O(count), in particular, it may not terminate
for an infinite Sequence.
(default T)
 => 
T
[Inherited from  Sequence]
get the last element of this Sequence or default if sequence is empty
 => 
i32
[Inherited from  array]
the length of the array
(B 
type
:
Type, f Unary B T)
 => 
Sequence B
[Inherited from  Sequence]
map the Sequence to a new Sequence applying function f to all elements

This performs a lazy mapping, f is called only when the elements
in the resulting list are accessed.
(B 
type
:
Type, f Binary B T i32)
 => 
array B
[Inherited from  abstract_array]
variant of map which additionally passes the index to
the mapping function f
(B 
type
:
Type, f Binary B T T)
 => 
Sequence B
[Inherited from  Sequence]
Map this Sequence to f applied to neighboring pairs of values
in this Sequence.

In case this Sequence has less than two elements, the result will
be the empty list.

ex. to obtain a Sequence of differences, you may use `map_pairs (-)`:


results in `[1,2,2,4,2,4,2,4,6]`
(B 
type
:
Type, f Unary B T)
 => 
array B
[Inherited from  abstract_array]
map the array to a new array applying function f to all elements
 => 
option T
[Inherited from  Sequence]
maximum value in the sequence
 => 
option T
[Inherited from  Sequence]
the median of the sequence
https://en.wikipedia.org/wiki/Median
 => 
option T
[Inherited from  Sequence]
minimum value in the sequence
(n i32)
 => 
option T
[Inherited from  Sequence]
the nth element in the sequence if it exists, wrapped in an option,
nil otherwise.

Complexity: if Sequence is array backed O(1) otherwise O(n)
(U 
type
:
Type, b Sequence U)
 => 
Sequence (tuple T U)
[Inherited from  Sequence]
create a new Sequence from tuples of all combinations of elements
of this Sequence and all elements of 'b' iterating of 'b' repeatedly
as follows

(f Unary unit T)
 => 
Sequence T
[Inherited from  Sequence]
calls `f` for each element in the Sequence.

Unlike `for_each` this returns itself
allowing easier composition with
other Sequence features.

example:

 => 
String
[Inherited from  Any]
convenience prefix operator to create a string from a value.

This permits usage of `$` as a prefix operator in a similar way both
inside and outside of constant strings: $x and "$x" will produce the
same string.
 => 
T
[Inherited from  Sequence]
generic product of the elements of a Sequence of numeric.

This allows multiplying the elements of a list, as in

(i i32, v T)
 => 
array T
[Inherited from  array]
create a new array with element i set to v. Grow the array in case i == length.

Complexity: O(array.this.length)
(i i32, v T, z T)
 => 
array T
[Inherited from  array]
create a new array with element i set to v. Grow the array in case i >= length.
New array elements at indices array.this.length..i-1 will be set to z.

Complexity: O(max(i, array.this.length))
(R 
type
:
Type, init R, f Binary (choice R (abort R)) R T)
 => 
R
[Inherited from  Sequence]
reduce this Sequence to R with an initial value init
and a reducing function f.
the reduction is finished once f yields abort or
if the end of the sequence is reached.
reduce this Sequence to `outcome R`
with an initial value `init` and a reducing function `f`.
the reduction is finished once `f` yields `abort` or
if the end of the sequence is reached.
(old Sequence T, new Sequence T)
 => 
Sequence T
[Inherited from  Sequence]
replace all occurrences of old by new
(old Sequence T, new Sequence T, n u64)
 => 
Sequence T
[Inherited from  Sequence]
replace the first n occurrences of old by new
reverse the order of the elements in this array

redefines:

reverse the order of the elements in this array
(m Monoid T)
 => 
list T
[Inherited from  Sequence]
map this Sequence to a list that contains the result of folding
all prefixes using the given monoid.

e.g., for a Sequence of i32 s, s.scan i32.sum creates a list of
partial sums (0..).map x->(s.take x).fold i32.sum
(R 
type
:
Type, a R, f Binary R R T)
 => 
Sequence R
[Inherited from  Sequence]
map this Sequence to a Sequence that contains the result of folding
all prefixes using the given function and initial value.

e.g., for a Sequence s `[3,8,10]`, `s.scan 0 (+)` creates a Sequence of
partial sums `[0, 3, 11, 21]`
scan1 works like its counterpart with an initial value, except
that the initial value is taken to be the first element of the given
Sequence.

for example, (1::id).scan (+) would create [1, 2, 3, 4, ...], while
(1..).scan (+) would create [1, 3, 6, 10, ...].
(from i32, to i32)
 => 
Sequence T
[Inherited from  abstract_array]
create a slice from this array's elements at index 'from' (included)
up to 'to' (excluded).

Complexity:
index access : O(1)
count : O(1)

redefines:

(size i32)
 => 
Sequence (Sequence T)
[Inherited from  Sequence]
sliding window with step size one
blocks of size elements, each is offset by one element to the previous one

example:
`(0..5).sliding 3`
=> `[[0, 1, 2], [1, 2, 3], [2, 3, 4], [3, 4, 5]]`
(size i32, step i32)
 => 
Sequence (Sequence T)
[Inherited from  Sequence]
sliding window
blocks of size elements, each is offset by step elements to the previous one

examples:
`(0..5).sliding 3 1`
=> `[[0, 1, 2], [1, 2, 3], [2, 3, 4], [3, 4, 5]]`

`(0..9).sliding 3 2`
=> `[[0, 1, 2], [2, 3, 4], [4, 5, 6], [6, 7, 8]]`
sort this Sequence
sort this Sequence using the order defined by less_or_equal
create a tuple of two Sequences by splitting this at the given index, i.e.,
a Sequence of length 'at' and one of length 'count-at'.

at may be <= 0 or >= count, in which case the resulting tuple will be the
(empty list, Sequence.this.as_list) or (Sequence.this.as_list, empty list), resp.
(l Sequence T)
 => 
bool
[Inherited from  Sequence]
does this sequence start with l?
 => 
option T
[Inherited from  Sequence]
the standard deviation of the sequence
https://en.wikipedia.org/wiki/Standard_deviation
 => 
T
[Inherited from  Sequence]
generic sum of the elements of a Sequence of numeric.

This allows summing the elements of a list, as in

 => 
list (list T)
[Inherited from  Sequence]
create a lazy list of all the tails of this Sequence, including the complete Sequence
as a list and the empty list 'nil'.
(n i32)
 => 
Sequence T
[Inherited from  Sequence]
create a Sequence that consists only of the first n elements of this
Sequence, fewer if this Sequence has fewer elements
Lazily take the first elements of this Sequence for which predicate 'p' holds.
(TA 
type
:
Type, U 
type
:
Type, xf transducer TA U T, rf Binary TA TA U, init TA)
 => 
TA
[Inherited from  Sequence]
takes a transducer xf, a reducer f and an initial value
returns the result of applying the reducer xf f to the Sequence
 => 
Sequence T
[Inherited from  Sequence]
filter out duplicate elements.

Keep the order of elements unchanged.

Other languages call this 'distinct' (eg., Java, C# or Kotlin)
or `nub` (Haskell).

ex.

 => 
option T
[Inherited from  Sequence]
the variance of the sequence
https://en.wikipedia.org/wiki/Variance
(U 
type
:
Type, V 
type
:
Type, b Sequence U, f Binary V T U)
 => 
Sequence V
[Inherited from  Sequence]
create a new Sequence from the result of applying 'f' to the
elements of this Sequence and 'b' in order.

Type Functions

 => 
String
[Inherited from  Type]
string representation of this type to be used for debugging.

result has the form "Type of '<name>'", but this might change in the future

redefines:

Maximum number of elements shown for on a call to `as_string` for a non-finite
Sequence.
monoid of Sequences with infix concatenation operation.
 => 
Type
[Inherited from  Type]
There is no dynamic type of a type instance since this would result in an
endless hierarchy of types, so dynamic_type is redefined to just return
Type.type here.

redefines:

(T 
type
:
Type)
 => 
bool
[Inherited from  Type]
Is this type assignable to a type parameter with constraint `T`?

The result of this is a compile-time constant that can be used to specialize
code for a particular type.


it is most useful in conjunction with preconditions or `if` statements as in


or

 => 
i32
[Inherited from  array]
return the maximum length of an array
 => 
String
[Inherited from  Type]
name of this type, including type parameters, e.g. 'option (list i32)'.
(length i32, init Unary T i32)
 => 
array T
[Inherited from  array]
array -- create initialized one-dimensional immutable array
 => 
String
[Inherited from  Type]
convenience prefix operator to create a string from a value.

This permits usage of `$` as a prefix operator in a similar way both
inside and outside of constant strings: $x and "$x" will produce the
same string.

NYI: Redefinition allows the type feature to be distinguished from its normal counterpart, see #3913

redefines:

 => 
Type
[Inherited from  Any]
Get a type as a value.

This is a feature with the effect equivalent to Fuzion's `expr.type` call tail.
It is recommended to use `expr.type` and not `expr.type_value`.

`type_value` is here to show how this can be implemented and to illustrate the
difference to `dynamic_type`.
0.095dev (2025-08-15 12:02:22 GIT hash 301b5b75e77076d091b38f555473f9f0e31e5b5c built by fridi@fzen)