The Zeno Book Zeno 0.1 zeno-lang.org

9 Lists

A list holds several values in order. It can grow and shrink, and each of its items has a position, counted from 0.

9.1 Making a list and reading it

let primes = [2, 3, 5, 7]
print(primes, len(primes), primes[0], primes[3])
print([], [[1, 2], [3]])
[2, 3, 5, 7] 4 2 7
[] [[1, 2], [3]]

The type of a list says what its items are: primes is a list[int]. Zeno works it out from the items, or you write it, which you must do for an empty list that has nothing yet to work it out from:

let names: list[str] = []
let grid: list[list[int]] = [[1, 2], [3, 4]]
print(names, grid[1][0])
[] 3

A position outside the list is an IndexError, and so is a negative one (Text gives the reason):

let primes = [2, 3, 5, 7]
print(primes[4])
error: uncaught IndexError: index 4 is out of range for a list of length 4
 --> main.zeno:2:7
  |
2 | print(primes[4])
  |       ^

9.2 Changing a list

let xs = [3, 1, 2]
xs.append(4)           # at the end
xs.insert(0, 9)        # at position 0, moving the rest up
print(xs)
xs[1] = 30             # replace the item at position 1
print(xs)
let last = xs.pop()    # take out the last item, and give it
let first = xs.pop(0)  # take out the item at position 0
print(last, first, xs)
xs.clear()             # take out everything
print(xs)
[9, 3, 1, 2, 4]
[9, 30, 1, 2, 4]
4 9 [30, 1, 2]
[]

All of these change the list itself, which is why xs can be a let: the name always means the same list, while what the list holds changes. Values and Variables has the rule.

Every item must be of the list’s type:

let xs = [1, 2]
xs.append("three")
error: an item added to this list should be int, but this is str
 --> main.zeno:2:11
  |
2 | xs.append("three")
  |           ^

1 error found. Nothing was run.

9.3 Every method of a list

Method Does
append(x) puts x at the end
insert(at, x) puts x at position at, moving the rest up
pop() takes out the last item, and gives it
pop(at) takes out the item at at, and gives it
clear() takes out every item
reverse() turns the list round, where it is
sort() puts numbers or text in order, smallest first, where it is
find(x) the position of the first item equal to x, or none
slice(from, to) a new list of the items from from up to, not including, to
slice(from) a new list of the items from from to the end
join(sep) for a list of text: one text, with sep between the items
map(f) a new list of f of each item
filter(f) a new list of the items for which f is true
reduce(f, start) the items folded into one value with f, starting from start

Beside them stand the functions len(xs), sum(xs), min(xs) and max(xs), the operator x in xs, and + to join two lists into a new one.

let numbers = [5, 3, 9, 1]
numbers.sort()
print(numbers, numbers.find(9), numbers.find(4), 3 in numbers)
numbers.reverse()
print(numbers, numbers.slice(1, 3), numbers + [0])
print(["pear", "fig", "apple"].join(", "))
print(sum(numbers), min(numbers), max(numbers))
[1, 3, 5, 9] 3 none true
[9, 5, 3, 1] [5, 3] [9, 5, 3, 1, 0]
pear, fig, apple
18 1 9

What there is no method for

Some methods that other languages have are left out, because Zeno already says the thing in one short expression:

In other languages In Zeno
xs.contains(x) x in xs
sorted(xs) let ys = xs.slice(0), then ys.sort()
xs.remove(x) xs.find(x), then xs.pop(at)
xs.extend(ys) xs += ys
xs[1:3] xs.slice(1, 3)

A method gets into the library only if most programs in the big languages use it and Zeno cannot already say it in one short expression. That keeps one way to write each thing. (Decision 6.1.)

sort and reverse change the list

sort and reverse work where the list is and give back nothing. To keep the old order, sort a copy, which slice(0) makes:

let readings = [5, 3, 9, 1]
let in_order = readings.slice(0)
in_order.sort()
print(readings, in_order)
[5, 3, 9, 1] [1, 3, 5, 9]

sort knows how to order numbers and text, which have one order that nobody has to be told. Anything else it refuses, with the reason:

let flags = [true, false]
flags.sort()
error: `sort` puts numbers or text in order, smallest first, and this is list[bool]. There is no one order for those items, so write the loop that puts them in yours
 --> main.zeno:2:1
  |
2 | flags.sort()
  | ^

1 error found. Nothing was run.

A new list is new memory, which a program on a small board may not want to spend, and a method that gives the list back invites let ys = xs.sort(), where it is not clear whether xs changed. sort is heapsort in every engine: it needs no second list, never calls itself, and is never slow, which is what firmware wants. (Decisions 6.5 and 6.6.)

find, and taking out by value

find gives a position or none. To take out an item by its value, find it first, and say what happens when it is not there:

let names = ["Ada", "Grace", "Alan"]
let at = names.find("Grace")
if at is not none {
    names.pop(at)
}
print(names)
["Ada", "Alan"]

9.4 Joining lists

+ makes a new list from two, and += adds a list to the end of a list variable. Both lists must hold the same kind of thing:

var log: list[str] = ["start"]
log += ["read", "write"]
print(log + ["stop"])
["start", "read", "write", "stop"]
let xs = [1, 2]
print(xs + ["a"])
error: `+` joins two lists that hold the same kind of thing, and these are list[int] and list[str]
 --> main.zeno:2:7
  |
2 | print(xs + ["a"])
  |       ^

1 error found. Nothing was run.

9.5 Comprehensions

A comprehension builds a new list from another in one line: an expression for each item, a for, and if you like an if that keeps only some items:

let numbers = range(1, 11)
print([n * n for n in numbers])
print([n for n in numbers if n % 3 == 0])
print([word.upper() for word in ["a", "b"]])
[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
[3, 6, 9]
["A", "B"]

It reads the way it would be said: "n times n, for each n in numbers".

9.6 map, filter and reduce

The same work can be done by handing a function to a method. map applies it to each item, filter keeps the items it says true for, and reduce folds the list into one value:

function square(n: int) -> int {
    return n * n
}
function is_even(n: int) -> bool {
    return n % 2 == 0
}
function add(total: int, n: int) -> int {
    return total + n
}

let numbers = [1, 2, 3, 4, 5, 6]
print(numbers.map(square))
print(numbers.filter(is_even))
print(numbers.reduce(add, 0))
print(numbers.filter(is_even).map(square).reduce(add, 0))
[1, 4, 9, 16, 25, 36]
[2, 4, 6]
21
56

The last line reads left to right, in the order things happen: take the numbers, keep the even ones, square them, add them up.

As methods, map, filter and reduce read left to right. As plain functions, the same chain is reduce(add, map(square, filter(is_even, numbers))), which has to be read from the inside out. (Decision 3.6b.)

A function can also be written in place, with no name. Functions as Values covers that.

9.7 Two names, one list

A list is not copied when it is given another name, passed to a function or put in another list. Every name sees the one list:

function add_reading(readings: list[float], r: float) {
    readings.append(r)
}

let mine = [20.5]
let also_mine = mine
add_reading(also_mine, 21.0)
print(mine)
[20.5, 21.0]

When you want a separate list, make one: xs.slice(0) copies the whole list.

Sharing is what Python, Java and JavaScript programmers expect, and it is the cheapest thing to do. In an ordinary build a garbage collector makes it safe; a build with no collector gives each list one owner instead, and Building with No Collector explains how. (Decision 3.10.)

9.8 Equal lists

Two lists are equal when they have equal items in the same order:

print([1, 2] == [1, 2], [1, 2] == [2, 1])
true false

A list holds values of one type, in order, from position 0. It grows with append, insert and +=, shrinks with pop and clear, and is ordered with sort and reverse, all in place. find, slice, join, map, filter and reduce give new values. Comprehensions build lists in one line. A list is shared, never copied without being asked.

  1. Write function median(values: list[float]) -> float that does not change the list it is given.

  2. Take every second item of a list with a comprehension and range.

  3. Remove every 0 from a list of numbers, first with a loop and pop, then with filter. Which is easier to get right, and why?

  4. Write a list of lists that is a 3 by 3 grid of zeros, set the middle to 1, and print it row by row.