container

abstract type for 'Linked_List'

Map -- an abstract map from keys K to values V

an interface defining a mutable array

Mutable_Map -- an abstract mutable map from keys K to values V

Persistent_Map -- an abstract persistent map from keys K to values V

Set -- an abstract set of values

interface definition for stacks

float_sequence -- a Sequence whose elements inherit from float

hash_map -- an immutable hash map from keys HK to values V

numeric_sequence -- a Sequence whose elements inherit from numeric

ordered_map -- an immutable map from ordered keys OK to values V

Lookup performance is O(log size) since it uses binary search in a
sorted array. When deterministic performance is desired, an ordered map
should be preferred over a hash map.

performance of creation of the map is in O(n log n) where n is
keys.length.

searchable_sequence -- a Sequence whose elements inherit from property.equatable

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 peformance 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).

A stack implementation using local mutation

create a String from this instance. Unless redefined, `a.as_string` will
create `"instance[T]"` where `T` is the dynamic type of `a`

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 hierachy of types. So for Type values, dynamic_type is redefined
to just return Type.type.

map_of -- routine to initialize a map from an array of key value tuples

This feature creates an instance of a map.

example: map_of [(key1, value1), (key2, value2)]

map_of -- routine to initialize a map from arrays of ordered elements
and values

This feature creates an instance of a map.

name of this type, including type parameters, e.g. 'option (list i32)'.

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.

set_of_hashable -- routine to initialize a set from a Sequence of hashable elements

This feature creates an instance of a Set.

set_of_ordered -- routine to initialize a set from a Sequence of ordered elements

This feature creates an instance of a Set.

sorted_array_of -- sorted one-dimensional immutable array of ordered elements

This takes an unsorted array as an argument and returns a sorted one using
the order defined by the type of the elements T.

See sorted_array from less_or_equal for details

Buffer -- one-dimensional mutable buffer with effect

Buffer can be used to implement ranges of mutable memory that may be
visible to the outside or even may be modified by the outside. Examples
are memory mapped files, memory shared between processes, bitmaps on a
display, memory mapped I/O, etc.

To model the effects of reading or writing a buffer, an effect is given
as an argument to a buffer. This effect should implement the operations
required to implement the `index []` and `set []` features as needed by
the backend. This could be done via direct memory accesses, as for `mmap`
memory used in a native backend, or via an API such as `java.nio.ByteBuffer`
for a JVM backend.

Circular_Buffer -- a circular buffer-like structure

buffer to which elements can be enqueued and retrieved with a FIFO
logic.

it is usually backed by a fixed length array.

abstract type for 'Linked_List'

Map -- an abstract map from keys K to values V

an interface defining a mutable array

Mutable_Array2 -- two-dimensional mutable array with effect

a type for mutable singly linked lists

On call to `Mutable_Linked_List LM T data` creates a minimal list consisting
of only one single element. To create larger rings, you can either call
`append` to add single cells, or `concat` to concatenate two lists.

Mutable_Map -- an abstract mutable map from keys K to values V

Persistent_Map -- an abstract persistent map from keys K to values V

Set -- an abstract set of values

interface definition for stacks

float_sequence -- a Sequence whose elements inherit from float

hash_map -- an immutable hash map from keys HK to values V

mutable_tree_map -- a mutable map using an AVL tree

numeric_sequence -- a Sequence whose elements inherit from numeric

ordered_map -- an immutable map from ordered keys OK to values V

Lookup performance is O(log size) since it uses binary search in a
sorted array. When deterministic performance is desired, an ordered map
should be preferred over a hash map.

performance of creation of the map is in O(n log n) where n is
keys.length.

ps_map -- a partially sorted map

ps_map is a persistent map from an ordered key PK to a value V. This map is
generally well-behaved with respect to cumulative and average performance.

The keys and values are stored in arrays consisting of sorted sub-arrays,
with sub-arrays corresponding to the 1-bits in the binary representation
of the size.

This results in cumulative memory usage in O(size log² size), worst-case
lookup time in O(log² size) and average addition time in O(1) and worst-case
addition time in O(size log² size).

WARNING: Due to the high worst-case time for addition, this structure should
not be used in situations when adding a single element repeatedly to the same
instance of ps_map is performance critical. If the resulting map's size n is a
power of 2, this will trigger the worst-case addition time resulting in
O(m*n log² n) for adding an element m times.

This constructor is for internal use only, to create instance of ps_map, use
ps_map PK V without arguments.

ps_set -- a partially sorted set based on ps_map

ps_set is a persistent set of ordered values. This set is generally
well-behaved with respect to cumulative and average performance.

WARNING: Due to the high worst-case time for addition, this structure should
not be used in situations when adding a single element repeatedly to the same
instance of ps_set is performance critical. If the resulting set's size n is a
power of 2, this will trigger the worst-case addition time resulting in
O(m*n log² n) for adding an element m times.

searchable_sequence -- a Sequence whose elements inherit from property.equatable

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 peformance 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).

A stack implementation using local mutation

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`.