Arrays¶
Arrays in Kod are resizable, homogeneous sequences. The type is [T] where T is the element type.
An array is a value, like an int64 or a str: assigning it, passing it or
storing it in a field gives the other place the array as it is, and changing
one of them later leaves the others alone (see Arrays are values).
Literals¶
A literal with no type to go to takes its first element's type, and every
other element must have that type: let xs = [1, "a"] is an error
(expected `int64`, got `str`), and so is [Sq(s: 1), Circle(r: 1)]
even when both implement Shape. Annotate the array to mix structs behind
an interface: let shapes: [Shape] = [Sq(s: 1), Circle(r: 1)], which the
error suggests when the module has an interface both implement.
Indexing¶
let first: int64 = nums[0]
let last: int64 = nums[-1] // negative index counts from end
let third: int64 = nums[2]
Negative indices wrap around: arr[-1] is equivalent to arr[len(arr) - 1].
An index out of range either way panics. An index must be an int64:
nums["a"], nums[true] and an int64? index such as nums[m.get(k)] are
errors.
An array never shrinks, so in for i in 0..len(xs) (from any literal of 0 or
more) xs[i] is always in range, and the compiler leaves out the check when
xs is a let or a parameter, which nothing can point at another array.
Arrays nest: an element of a [[int64]] is an [int64], so grid[i][j]
and for row in grid { for x in row { ... } } work, and an element of a
[bool] is a bool.
A literal takes its element type from where it goes, at any depth: a
let, an assignment, an argument, a field, an enum payload, a return value
(including a match arm's), the rest of an array + chain (see
Concatenation), or an element or Map value it's stored
as. In let g: [[Shape]] = [[Sq(s: 3)]], shapes += [Sq(s: 4)],
[Sq(s: 1)] + shapes or return [none, 3] from a -> [int64?] function,
each struct is boxed as the interface and each value wrapped as the
optional. In a [Direction], [.North, .South] builds Direction
variants even when another enum declares variants of those names, and in a
[Maybe[int64]], [.Just(value: 1), .Nothing] builds Maybe[int64] ones.
Arrays, str and bytes can be indexed, and so can a struct that declares
an op_index method (Map does). Element assignment needs an array or a
struct with op_index_set, slicing needs an array, str or bytes, and
for … in needs an array, str, bytes, Map, Set or a..b (see
Control flow). Anything else is a compile
error.
An array can be changed, by assigning an element or appending, only through
a name that could be assigned: a mut binding or a mut parameter. On a
let array, a parameter not declared mut, a for variable or a pattern
binding, xs[0] = 1 and grid[i][j] = 1 are errors
(cannot change `xs`, an immutable binding; declare it with `mut`),
as xs += [1] is. An array kept in a field is changed through the field,
so self.xs[i] = v and p.items += [x] work however self or p is bound.
An assigned element must have the array's element type, with the same
conversions as a let: names[0] = 5 on a [str] is an error, while
xs[0] = 42 on an [int64?] and pets[0] = Cat() on a [Pet] wrap and
box the value. On a struct, the key of m[k] and the key and value of
m[k] = v must have the types of op_index's and op_index_set's
parameters (see Indexing a struct), so
m[5] on a Map[str, int64] is an error.
A store evaluates its parts left to right: in rows()[i()] = v() and
m[k()] = v() the receiver comes first, then the index or key, then the
value, and f().x = v() calls f before v. A compound
rows()[i()] += v() evaluates the receiver and the index once, reads the
element and then evaluates v(), so rows and i are each called once.
Indexing a struct calls its op_index, so it counts as a call too:
xs[a[k]] += b[k] calls a's op_index once, before b's.
Length¶
Slicing¶
let sub: [int64] = nums[1..4] // elements 1, 2, 3
let prefix: [int64] = nums[..3] // first three
let suffix: [int64] = nums[3..] // from index 3 onward
let all: [int64] = nums[..] // all of it
Both endpoints clamp to [0, len]: a negative bound becomes 0 and a bound past
the end becomes len, so [1, 2, 3][1..10] is [2, 3]. An end before the
start yields an empty slice. Unlike indexing, slice bounds never wrap.
Both bounds must be int64.
Concatenation¶
Use += to append elements or extend with another array:
Or + to produce a new array; neither operand is modified:
Every literal and match in a chain of + is built as the type the whole
chain goes to, or, without one, as its first operand that isn't a literal or
match. So [Sq(s: 1)] + [Sq(s: 2)] + shapes boxes both squares as Shape,
and let ms: [Maybe[str]] = [.Just(value: "a")] + [.Nothing] builds
Maybe[str] variants. The other operands must all have that one type:
squares + shapes (a [Sq] and a [Shape]) and nums + names are errors,
and so is names + [1], whose literal's element isn't a str.
+= grows the array's buffer geometrically, so appending in a loop is
amortized O(1) per element. + always copies both operands, so
xs = xs + [x] costs O(len(xs)); prefer xs += [x] in loops. xs += [x]
with one element builds no array for the literal: x goes straight onto the
end of xs.
Arrays are values¶
Each name, field and element holds an array of its own. After let a = xs,
xs += [3] leaves a as it was, and so does xs[0] = 9; the same goes for
an array stored in a field or in another array, or passed to a function:
mut xs = [1, 2]
let a = xs
xs += [3] // xs is [1, 2, 3], a is still [1, 2]
mut grid = [[0, 0], [0, 0]]
let row = grid[0]
grid[0][1] = 5 // grid is [[0, 5], [0, 0]], row is still [0, 0]
None of this copies anything until it has to: assigning or passing an array
shares its elements, and they are copied the first time one holder changes
them while another still has them. An array nobody else holds is changed in
place, so appending in a loop stays amortized O(1). A function changes its
caller's array only through a mut parameter.
A for x in xs loop goes over xs as it was when the loop started: what
the body appends or assigns to xs is in xs afterwards, but the loop
doesn't reach it.
Repetition¶
* with an int64 repeats an array, in a new array, which is the way to make
one of a given size:
mut seen = [false] * 1000 // 1000 times false
let zeros: [int64] = [0] * n
let ab = [1, 2] * 3 // [1, 2, 1, 2, 1, 2]
The count comes second, and zero or less gives an empty array. It is one
allocation and a copy, much faster than appending in a loop. Each element is
a value of its own, so the rows of mut grid = [[0] * 3] * 3 can be changed
one at a time.
Comparing¶
== and != compare two arrays of the same type element by element: they are
equal when they have the same length and each element is == to the one at
the same place in the other.
The elements must have an == of their own, so an array of structs without
op_eq, interface values or functions doesn't compare (see
Operators).
As text¶
An f-string, str(xs) and print(xs) show an array as its elements in
brackets, separated by ,, each as an f-string would show it:
A str element shows as its text, without quotes. The elements must have a
text of their own: an array of structs without to_str can't be shown.
Iterating¶
Index-based:
Foreach:
Memory layout (compiler)¶
Arrays are represented as a header struct on the heap:
The ptr field points to a block of elements, each 8 bytes wide except in a
[bool], whose elements are a byte each (a 1000-element [bool] takes 1000
bytes, not 8000). len is the number of live elements; cap is the
allocated capacity, in elements.
The header is counted like any other object, and the count says how many
places hold the array. Before changing an array, generated code checks that
the count is 1; if it isn't, _kod_arr_unique copies the header and the
elements, stores the copy where the array was, and lets go of the original.
Appending (+=) goes through _kod_arr_concat in the runtime, which
writes into the existing buffer and reallocates it with doubled capacity
only when cap runs out. + goes through _kod_arr_concat_new, which
allocates a fresh header and buffer, and * through _kod_arr_repeat. Each
takes the element width from the compiler, which knows the type.
Helpers¶
The arrays module has what's the same for an array of any type:
Elements compare with ==, so strs by content, and a type that == doesn't
take is an error (see Generic functions).
Sorting¶
The sort module's functions return a new array and leave the argument as it
is. They take O(n log n) comparisons and are stable: elements that compare equal
keep their order.
sorted orders by <, so it takes numbers, strs (by byte), and structs that
declare op_lt. sorted_by takes the order as a
function that says whether its first argument goes before its second: