We have already met some expressions denoting lists. This section will introduce some of the procedures used for manipulating lists, including new procedures for creating new lists, or modified versions of old ones.
cons(ITEM, LIST) -> LISTThis is strictly equivalent to ITEM :: LIST. It is included in Pop-11 merely as an analogue for the function CONS in Lisp.
conslist(ITEM1, ITEM2, ..., ITEMN, N) -> LISTReturns a list constructed from the top N items on the stack. E.g.
conslist("a", "b", [c d], 3) =>
** [a b [c d]]
conslist(#| vars i; for i from 2 to 13 do i*i endfor|#) =>
** [4 9 16 25 36 49 64 81 100 121 144 169]
initl(N) -> LISTThis constructs a list of empty lists, of length N. E.g.
initl(6) =>
** [[] [] [] [] [] []]
sysconslist() -> LISTCollects all items placed on the stack since the last stackmark, into a list. This is used by Pop-11 list constructor syntax. E.g.
[% 1, 2, 3, 4 %]
is equivalent to
popstackmark, 1, 2, 3, 4; sysconslist();
See REF LISTS, for a description of sysconslist_onto(LIST_1), which
is used when ^^ precedes the last item in a list expression.
allbutfirst(N, LIST) -> SUB_LIST allbutlast(N, LIST) -> SUB_LISTThese two can be used to "chop off" an initial or final segment of a list, of length N.
allbutfirst(2, [a b c d e]) =>
** [c d e]
allbutlast(2, [a b c d e]) =>
** [a b c]
In the first case, the result will share list links with the input list.
The procedure dest (or destpair) when given a list puts its and its tail on the stack. Sometimes it is necessary to put all the elements of a list on the stack, e.g. in order to use them to make a copy of the original list. The procedure explode will do this.
explode([a b [c d] e f]) =>
** a b [c d] e f
However, explode works on a variety of different structures, including
words, strings, vectors and lists. A version specific to lists is also
available, known as "dl".
dl([a b [c d] e f]) =>
** a b [c d] e f
destlist is similar, except that it also returns the number of
items in the list. It's the reverse of conslist.
destlist([a b [c d] e f]) =>
** a b [c d] e f 5
Both of these take a list and a procedure and apply the procedure to every element of the list. The only difference is that maplist makes a list of everything put on the stack.
applist([1 2 3 4 5], nonop +(% 10 %)) =>
** 11 12 13 14 15
maplist([1 2 3 4 5], nonop *(% 10 %)) =>
** [10 20 30 40 50]
ncmaplist, non-constructive maplist, is like maplist, except that it
re-uses the links of its first argument.
This procedure can be applied to any object. If it's a list or pair, it repeatedly applies the procedure front, until a non-pair is found, and returns that as its result. This is useful for digging out items deeply embedded in lists.
recursive_front([[[[[a] b ] c]] d]) =>
** a
expandlist(LIST) -> LISTReturns LIST unchanged, unless the list is dynamic, in which case it runs the generator procedure to completion and makes the list static. It will loop forever if the list is of infinite length.
rev(LIST) -> LISTrev, when given a list, produces a new version which has the same elements in reverse order:
rev([1 2 3 4]) =>
** [4 3 2 1]
The procedure does not alter the order of elements in the original list:
that is left unchanged.
ncrev(LIST) -> LISTThis is like rev, except that it re-uses the list links of the original list, so that it does not use any new store. This can reduce garbage collections but is dangerous if there is any risk that something else was dependent on the original list surviving unchanged.
vars list1 = [a b c], list2 = ncrev(list1);
list2 =>
** [c b a]
list1 =>
** [a]
setfrontlist(ITEM, LIST_1) -> LIST_2Returns LIST_2 formed by moving the ITEM to the front of LIST_1, or adding the ITEM if not already present. (This is used by the editor VED whenever a file in vedbufferlist becomes "current".)
sort(LIST_1) -> LIST_2The list should contain either numbers only or words only or strings only or a mixture of words and strings. Any other items will produce an error. It returns a list of sorted items. If it contains numbers only, then the result is equivalent to
syssort(LIST_1, nonop <)otherwise
syssort(LIST_1, alphabefore)
sort([the cat sat on the mat]) =>
** [cat mat on sat the the]
sort([ 111 222 33 ]) =>
** [33 111 222]
syssort(LIST, P) -> LIST
syssort(LIST, BOOL, P) -> LIST
The first argument is a list, the last argument is a procedure which
takes two items and returns a boolean result (e.g., nonop < for numbers
or -alphabefore- for string and words, etc). The items in the list are
compared using the procedure and the result is a list with elements
sorted in accordance with the procedure. If the optional boolean
argument is <false>, then the sorting is non-copying, and merely
re-arranges the elements of the argument list, like ncrev. A merge sort
algorithm is used. Example
syssort([[the] [cat] [sat] [on] [the] [mat]],
procedure(l1, l2);
alphabefore(hd(l2), hd(l1))
endprocedure) =>
** [[the] [the] [sat] [on] [mat] [cat]]
last finds or updates the final element of a list:
last([cat dog mouse]) =>
** mouse
last([[tom brown] [mary green] [suzy white]]) =>
** [suzy white]
Note that in the latter example, the procedure LAST was applied to a
list of lists, and produced as its result a list, i.e. the last
list.
vars list = [a b c d];
list =>
** [a b c d]
999 -> last(list);
list =>
** [a b c 999]
NOTE: last can also work on words, vectors and strings, though the
updater cannot be used with words.
lastpair(LIST) -> PAIR PAIR -> lastpair(LIST)Returns or updates the last PAIR of the list LIST, i.e. the last link in the chain. LIST cannot be null. Having a pointer to the last pair of a list, instead of the last item in the list makes various things much simpler. For example, here is one way to define a queue:
vars queue = [a b c d], queue_start = lastpair(queue);
queue_start =>
** [d]
To add something to the queue at the far end, do this:
conspair("e", []) -> back(queue_start);
back(queue_start) -> queue_start;
queue =>
** [a b c d e]
queue_start =>
** [e]
Remove something at the left end:
tl(queue) -> queue;
queue =>
** [b c d e]
oneof applied to a list chooses an element at random. Thus using it repeatedly on the same list may or may not produce different results:
repeat 4 times
oneof([ [you are gorgeous]
[everyone loves you]
[how masterful you are]
[you are quite stunning]
]) =>
endrepeat;
** [you are quite stunning]
** [everyone loves you]
** [you are quite stunning]
** [you are quite stunning]
shuffle(LIST_1) -> LIST_2
Returns a copy of its argument with the elements randomly re-ordered.
It uses -oneof-.
repeat 4 times shuffle([a b c d e]) => endrepeat;
** [b d c a e]
** [b d a c e]
** [b e c d a]
** [d c e b a]
Since oneof and shuffle are defined in terms of random, illustrated
previously, (in Chapter 5) their behaviour can be controlled by
assigning to the variable ranseed, as in the case of random.
delete produces copies of a list which do not contain a certain element. It has several different formats
delete(ITEM, LIST_1) -> LIST_2 delete(ITEM, LIST_1, EQ_P) -> LIST_2 delete(ITEM, LIST_1, N) -> LIST_2 delete(ITEM, LIST_1, EQ_P, N) -> LIST_2These all delete occurrences of ITEM from LIST_1, producing a new list LIST_2 (which shares the largest possible trailing sublist of the original).
The parameter EQ_P is an optional argument; if supplied, it must be a procedure of the form
EQ_P(ITEM, LIST_ELEMENT) -> BOOLEQ_P is then used to compare ITEM against each list element, and those for which it returns true are deleted. If not supplied EQ_P defaults to nonop = (i.e. structure equality). (See HELP EQUAL)
N is a second optional argument: if supplied, it is an integer >= 0 which specifies how many matching elements should be deleted (e.g, if 1 then only the first occurrence will be removed). If not supplied, all occurrences are deleted.
For example,
delete(1, [1 2 3 4 5 6 1 9 8]) =>
** [2 3 4 5 6 9 8]
delete(1, [1 2 3 4 5 6 1 9 8], 1) =>
** [2 3 4 5 6 1 9 8]
delete("cat", [mouse cat dog flea], nonop == ) =>
** [mouse dog flea]
delete('cat', ['mouse' 'cat' 'dog' 'flea'], nonop == ) =>
** [mouse cat dog flea]
delete('cat', ['mouse' 'cat' 'dog' 'flea'], nonop = ) =>
** [mouse dog flea]
(The difference between the last two is due to the fact that two strings
can be "=" but never "==").
ncdelete(ITEM, LIST_1) -> LIST_2 ncdelete(ITEM, LIST_1, EQ_P) -> LIST_2 ncdelete(ITEM, LIST_1, N) -> LIST_2 ncdelete(ITEM, LIST_1, EQ_P, N) -> LIST_2Non-constructive delete. Same as delete, but does not copy list pairs that need to be changed, and thus (may) destructively change the original list. The result LIST_2 will be == to LIST_1 unless there are one or more leading matching occurrences of ITEM that are deleted.
flatten(LIST_1) -> LIST_2Explodes LIST_1 and all sub-lists in LIST_1. I.e. it converts a tree into "flat" list of elements at the "fringe" of the tree.
flatten([ a [ b c [d e] [f]] g [ h [i] ] j]) =>
** [a b c d e f g h i j]
flatlistify(STRUCT) -> LISTGiven a structure, STRUCT, made of lists and/or vectors embedded arbitrarily, -flatlistify- will return a list, LIST. The result contains all the words needed to create a list isomorphic with the original one, if given to compile.
flatlistify([ a [ b c [d e] [f]] g [ h [i] ] j]) =>
** [a [ b c [ d e ] [ f ] ] g [ h [ i ] ] j]
NB. That is a 20 item list containing "a", "[", "b", etc.
These can both be applied to a list and will return the number of elements. The difference is that length can be applied to many other types of objects besides lists, e.g. strings, vectors.
listlength([a [ b c d] e ]) =>
** 3
listlength({ a b c }) =>
;;; MISHAP - LIST NEEDED
;;; INVOLVING: {a b c}
The procedure copy when given a Pop-11 data-structure returns a copy that is = to the original. In the case of lists, it merely copies the first link, returning a new pair with the same front as the oldone and the same back as the old one. This means that the two lists share tails.
vars list1 = [a b c d], list2 = copy(list1);
list2 =>
** [a b c d]
33 -> list1(3);
list1 =>
** [a b 33 d]
list2 =>
** [a b 33 d]
An assignment to the first element of a will not affect list2, and
vice-versa, but replacing any other element of either will affect the
other.
In order to avoid this what is needed is a complete copy of the original list, made entirely of new list links. The procedure copylist is provided for that purpose. The above example may be tried with copylist instead of copy.
Even if copylist did not exist, there are several ways it could be defined by users, including the following:
define copylist1(list);
maplist(list, identfn)
enddefine;
define copylist2(list);
[% appplist(list, identfn) %]
enddefine;
define copylist3(list);
[% explode(list) %]
enddefine;
define copylist4(list);
conslist(#| explode(list) |#)
enddefine;
define copylist5(list);
conslist(destlist(list))
enddefine;
copytree(LIST_1) -> LIST_2This makes a list, LIST_2, which is a copy of LIST_1. Any elements of LIST_1 which are themselves lists are recursively copied.
copydata is a generalisation of copytree that works on arbitrary datastructures. Thus if a list contains vectors containing lists, etc. then, in order to obtain a completely new copy use copydata, not copylist.
subscrl(N, LIST) -> ITEM ITEM -> subscrl(N, LIST)Returns or updates the N-th element of the list LIST (where the first element is has subscript 1). Because this procedure is the -class_apply- procedure of pairs, this can also be used in the form
LIST(N) -> ITEM
ITEM -> LIST(N)
fast_subscrl(N, LIST) -> ITEM
ITEM -> fast_subscrl(N, LIST)
This is like subscrl, but does not check argument data types, and does
not expand dynamic lists.