21. Lists

Many sections in this book begin by introducing a new kind of value. Reading through in order, the possibilities mount up: numbers, times, texts, and so on. (See the Kinds page of the Index for a convenient list of the options.) This section is a little different: rather than showing a single new kind of value, it shows how to make a new kind out of any existing one.

If K is any kind of value, then "list of K" is also a kind of value. For instance, we could write:

and this would create a new "let" variable, called L, whose kind of value is "list of numbers". On the other hand, we are not allowed to write:

because "list" by itself is not a kind of value. (Inform always needs to know what kinds the values entered in a list are going to have.)

Lists are like flexible-length table columns, but that probably makes them sound more mysterious than they really are. A list is simply a sequence of values, called its "entries", numbered from 1 upwards. The number of entries is called its "length". If we try

then we find

This is because all lists start out empty when created: that is, they initially have 0 entries. Inform has two built-in adjectives "empty" and "non-empty" which can apply to lists, and they mean just what they ought to mean: a list is empty if its length is 0, and otherwise non-empty.

We can add entries very easily:

We can now, for instance, try saying the list:

with the result

Note that only numbers can be added to L: if we try

Inform will produce a problem message, because L has kind "list of numbers", whereas "clock" is text. In this way, Inform ensures that a list always contains values of the same kind throughout. So it's not possible to construct a list whose entries are:

Such a list would be very hazardous to deal with, in any case. If what we need is a combination of different kinds of values, tables are a better option.

Finally, note that since "list of numbers" is a kind of value in its own right, so is "list of lists of numbers", and so on - though such lists are trickier to deal with, they are sometimes handy.

It is convenient to have a concise way to write down a constant list. Just as we could write "231", say, or "7:01 AM" to refer to particular number and time constants, so we can write list constants:

Inform recognises that "{1, 2, 3, 4}" is a list because of the braces, and looks at the entries inside, sees that they are numbers, and deduces that it is a constant whose kind of value is "list of numbers". L is then a temporary list variable and we can add to it, remove things, and so on as we please - {1, 2, 3, 4} is merely its initial value.

When constructing lists, it is worth noting that Inform requires spaces after the commas (which seems a little harsh, but is necessary because otherwise many sensible literal specifications for units would be impossible - anyway, the reason isn't important here). So

would produce problem messages. But Inform does not require spaces round its braces.

We call this way of writing a list "brace notation". In mathematics, braces are usually used for sets, and properly speaking these are sequences not sets - so that "{1, 2, 3, 4}" is different from "{4, 3, 2, 1}" - but it is still a familiar notation. Similarly,

makes L a list of texts; and

makes a global variable ("list of prohibited items") with kind of value "list of objects", and whose initial value is to contain two things: the firework and the stink bomb. More exotically, if we need to make lists of lists:

gives L the kind of value "list of lists of numbers", with (initially) two entries: the list {1, 2} (a list of numbers), then the list {6, 7, 8} (ditto).

Constant lists are convenient, too, when a column in a table needs to contain lists:

A special word about the constant list "{ }". This means the list with no entries - the empty list. If we try to create a new "let" variable M with

then Inform will produce a problem message, because it cannot tell what sort of list M will be: a list of numbers, or texts, or times, or…? On the other hand, writing

is fine if M already exists, and then does the obvious thing - empties M. Similarly, a table column in which every entry is "{ }" produces a problem message unless the heading for that column spells out the kind of value stored within it: for instance, "ingredients (list of texts)".

All of this is a notation for constant lists only, not some sort of gluing-things-together operation. So this, for instance:

is not allowed, even though "the turn count" is a number: because it is a number that varies, the braces do not contain constants, and therefore this is not a list constant.

Any list L can be said, provided that its contents can be said. For example:

produces the text "2, 3, 5, 7 and 11" - unless we have "Use serial comma." set, in which case a comma appears after the 7. We also have the option of using the more formal notation:

If we say a list of lists, then the individual entry lists are always printed in brace notation: the ordinary sentence way would be incomprehensible.

Of course, the values in L1 are written out in number form because L1 is a list of numbers: we could alternatively try

which produces "piano and music stand". Lists of objects can be said in two additional ways:

If L is a list, we can interrogate it to see whether it does or does not contain (at least one instance of) any compatible value V:

We can also repeat running through a list (just as we can with table rows). Thus:

In the next sections, we shall see that it is possible to change, reorder and resize lists. But it's important never to change a list that's being repeated through. The following:

leaves L1 containing {2, 4}, since the removals from the list cause it to shuffle back even while we repeat through it - a bad, bad idea.

We have already seen "add… to…". This in fact comes in two forms:

If we don't want to add new entries at the end, we can instead say where they should go:

A list is allowed to contain duplicates, and the order matters. For instance:

makes L into "2, 2 and 3". This is a different list to the one made by:

even though L and M have the same values, repeated the same number of times - for two lists to be equal, they must have the same kind of entry, the same number of entries, and the same entries in each position.

We can also strike out values:

Again, we can also remove from specific positions:

Lists can be made of values of any kind (including other lists), but lists of objects are especially useful. We could always make these "by hand":

But it is usually easier and clearer to use descriptions.

While that works nicely for many kinds of value ("list of recurring scenes", say), it's particularly useful for objects:

means that L now contains the open containers (if any) followed by the open doors (if any). Or, for example:

makes a list of all non-backdrops.

As mentioned above, lists of objects can be said in two additional ways:

And as mentioned below, they can be sorted in property value order:

where P is any value property. In all other respects, lists of objects are no different to other lists.

The useful "list of …" syntax can also be used to produce lists of the values matching a description, too. Thus:

There is little to say here except for the usual warning that some kinds of value have a range which is too large to make this possible. For instance, Inform could not sensibly represent:

It would just be too large to hold. In general, if we can repeat through, or find the number of, values matching a description, then we can also use "list of" to bring them all together. See the chart of kinds of value in the Kinds index for a project for which kinds of value allow this.

Any list L can be reversed:

And any list can similarly be sorted:

Lists of objects can also be sorted in property value order. For instance,

Rotating a list means moving all of its entries along by one place, and then moving the one on the end back to the start. For instance, if L is {1, 2, 3, 4}, then

The length of a list can change as values are added or removed, and can in principle be any number from 0 upwards. A list with 0 entries is empty. We can find the length with:

If the length is N then the entries are numbered from 1 (the front) to N (the back). These entries can be accessed directly by their numbers. For instance,

refers to the second entry of L: it can be used as a value, or changed, just as if it were a named variable. For instance, we could write:

which would (untruthfully) print "The rain in Spain stays mainly in the plain", but only if L had an entry 7 to make use of: if L were a list of 5 entries, say, then a run-time problem results. (And if L cannot hold text, a problem message means that we never get as far as run-time.) Because entries number from 1, this is always incorrect:

and if L is currently empty, then there is no entry which can be accessed, so that any use of "entry … of L" would produce a run-time problem. There are programming languages in the world where accessing entry 100 in a 7-entry list automatically extends it to be 100 entries long: Inform is not one of them. But see the next section for how to change list lengths explicitly.

We can explicitly change the length of a list like so:

We can also write the equivalent phrases:

But we don't have to truncate: we can also -

For example,

builds a list of N numbers (initially all 0), fills it with the numbers 1, 2, 3, …, N, then randomly reorders them, then sorts them back again, recovering the original order. The text produced by "check sorting 10" depends partly on chance but might for instance be:

As with text in the previous chapter, a project which needs really long lists should use the Glulx virtual machine - "check sorting 10000", for instance, would break the default memory environment on the Z-machine, which is very tight, but works fine (if not very rapidly) on Glulx.

Lists are highly adaptable, and many other collection-like constructions can be made using them. This section introduces no new material, but simply suggests some of the variations which are possible.

1. The traditional computing term array means a list of values accessed by their entry numbers, often used in mathematical computations. The difference between an array and a list is mostly one of attitude, but usually arrays are fixed in length whereas lists can expand or contract.

2. A log is a list which records the most recently arrived values, but does not allow itself to grow indefinitely. In the following, which remembers the seven most recently taken items, new values arrive at the end while old ones eventually disappear from the front:

Note that the most-recently-taken list begins play as the empty list, grows as the first few items are taken, but then stabilises at length 7 thereafter. If we need to remember recent history, but only recent history, then a log is better than a list which can grow indefinitely, because there is no risk of speed reduction or memory exhaustion in a very long story.

3. A queue is a list of values which are waiting for attention. New values join at the back, while those being dealt with are removed from the front (whereupon the whole queue moves up one). An empty queue means that nobody is waiting for attention: but there is, in principle, no upper limit to the size of a queue, as anyone who has tried to make a couchette reservation at Roma Termini will know.

Queues typically form when two independent processes are at work, but going at different or variable speeds. An empty queue looks just like any other list:

(Invariably people, in what follows, but we'll make it a "list of objects" to allow for other possibilities too.) Once we identify a "new customer", we can join him to the queue thus:

The process of serving the customers needs to make sure there is actually somebody waiting in the queue before it does anything:

Of course queues can also be constructed which empty from other positions, rather than the front: or we could make what computer scientists sometimes call a deque, a "double-ended queue" where new values arrive at both ends.

4. A stack is like a queue except that values arrive at, and are removed from, the same end. Stacks are slightly faster if the active end is the back rather than the front, though this will only be noticeable if they grow quite large.

To put a value V onto a stack S (which is known as "pushing") is simple:

And to remove a value from the top of the stack (which is known as "pulling"):

Note that the middle line, accessing entry N, will fail if N = 0, that is, if the stack is empty: Inform's list routines will produce a run-time problem message.

Stacks are useful if some long-term process is constantly being interrupted by newer and more urgent demands, but they can also be used in planning. If a character has a long-term goal, which needs various short-term goals to be achieved along the way, then a stack can represent the goals currently being pursued. The top of the stack represents what the character is trying to achieve now. If the character realises that it needs to achieve something else first, we put that new goal onto the top of the stack, and it becomes the new current goal. When the character completes a task, it can be removed, and we can go back to trying to finish whatever is now on top. When the stack is empty, the character has achieved the original goal.

5. Notoriously, set has 464 distinct meanings in the Oxford English Dictionary, making it the single most ambiguous word in the language. Here we mean not the home of a badger or the Egyptian god of the desert, but the mathematical sense: a collection of values (sometimes called "elements") without duplicates, and which is normally written in brace notation and in some natural order for the reader's convenience.

The trick here is to maintain the principle that, at all times, our list is sorted in order and contains no duplicates. To provide an example, we start with two sets of numbers:

Here we add an element to T:

The "if absent" clause ensures that no duplicate can occur, and by sorting T afterwards, we maintain the principle that a set must remain in order - so T is now {2, 4, 6, 8, 10}, not {2, 4, 6, 10, 8}. (Inform's sorting algorithm is fast on nearly-sorted lists, so frequent sorting is not as inefficient as it might look.)

We next take the union of T and S, that is, the set containing everything which is in either or both:

This makes U = {2, 4, 6, 8, 10, 16, 32, 64}, and once again no duplicates occur and we preserve the sorting. The intersection of T and S, the set of elements in both of them, is a little trickier:

(Faster methods could be devised which exploit the sortedness of T and S, but are not worth it for shortish lists.) This produces I = {2, 4, 8}. Lastly, we can form the set difference, consisting of those elements which are in S but not in T:

Here, as with intersection, since all we do is to strike out unwanted elements, the surviving ones remain in order and there is no need to sort when we are finished. This produces D = {16, 32, 64}.

6. A sieve is used to make a complicated choice where there are many constraints, by ruling out impossible cases to see what is left. The term derives from the kitchen utensil (for sieving fine grains of flour), but via the name of the "sieve of Eratosthenes", an ancient Greek method for determining the prime numbers.

Using a sieve is much like using a set, and the difference is mainly one of outlook - we are interested in what does not belong, rather than what does.

7. A ring is not so much a row of values, more a circle, with the last and first entries thought of as adjacent. One position is usually thought of as special, and is the place where new items are added: this may as well be entry 1. For instance, to add "new item" to the ring:

To set "item" to the frontmost value and extract it from the ring:

And we can rotate the ring in either direction, making a different entry the new entry 1 and therefore the new frontmost value:

A last note to conclude the chapter on lists. Lists, like almost all other values in Inform, can be passed to phrases as parameters. However, note that they are genuine values, not what some programming languages call "references" or "pointers". So the following:

does nothing, in practice. If given a list, it adds 7 to the list, but then throws it away again, so the longer list is never seen; it's exactly like

which can never affect anything other than its own temporary value "N", which expires almost immediately in any case.

If we want a phrase which changes a list in a useful way and gives it back to us, we need a phrase which both takes in and gives back:

And then, for example -

produces: