```Search                        Top                                  Index
```
```REF LISTS                                           John Gibson Mar 1994

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
<<<<<<<<<<<<<<<<<<<<<                             >>>>>>>>>>>>>>>>>>>>>>
<<<<<<<<<<<<<<<<<<<<<       LISTS AND PAIRS       >>>>>>>>>>>>>>>>>>>>>>
<<<<<<<<<<<<<<<<<<<<<                             >>>>>>>>>>>>>>>>>>>>>>
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

This REF file provides information on the 'list' data structure: how  it
is constructed from pairs, the two  types of lists: normal and  dynamic,
as well as detailing the predicates for use on pairs and lists, pair and
list constructor and access procedures, and other list utilities.

CONTENTS - (Use <ENTER> g to access required sections)

1   Introduction

2   Predicates on Pairs and Lists

3   Pair Constructor and Access Procedures

4   List Constructor Procedures

5   List Access Procedures

6   Other List Utilities

7   Generic Data Structure Procedures on Lists

8   Miscellaneous

---------------
1  Introduction
---------------

A pair  is a  record which  contains two  arbitrary Poplog  data  items,
called the front and the back of the pair: these structures may be  used
in their own right for any purposes.

The most frequent use of pairs, however, is to represent lists of items.
A list is represented in Poplog as a chain of pairs, where the front  of
each pair in the chain is used to hold the next element of the list, and
the back to  hold the  continuation of the  chain, which  may be  either
another pair or the special item [] (the value of nil) at the end of the
list. The two parts of the pair are then known respectively as the  head
and the tail (of  the list represented by  the pair). Thus, whereas  the
head of a list can be any item, the tail must always be another list.

Lists in Poplog can  also be dynamic:  a dynamic list  is one where  the
final element-holding pair in the chain contains in its back not []  but
another (special)  pair,  this pair  having  in its  back  a  procedure.
Whenever an attempt is made to access  the head or tail of this  special
pair, the procedure is called with the expectation that it will  produce
as result the next element of the list (or the item termin if there  are
no more to come).  The result is then  added to the end  of the list  by
placing it in  the front of  the special pair  and constructing  another
special pair to go in  its back (thus the  old special pair becomes  the
last proper pair of the list).

A pair whose  back is  a procedure  is therefore  a valid  list, as  yet
unexpanded, and  which  will be  expanded  by the  application  of  list
procedures like hd, tl, etc. The front of such a pair will contain  true
until the procedure in its back produces termin, at which time the front
becomes false. This indicates that the list is now null (and application
of hd, tl etc will produce an error).

See TEACH * PAIRS, * LISTS for tutorial introductions to pairs and lists
in Pop-11. HELP * LISTS overviews the on-line documentation relating  to
list processing in Pop-11.

--------------------------------
2  Predicates on Pairs and Lists
--------------------------------

atom(item) -> bool                                           [procedure]
Returns true if item is not a pair, false otherwise.  Equivalent
to not(ispair(item)).

isdynamic(item) -> p                                         [procedure]
Returns the generator procedure p underlying a dynamic list,  or
false if item is not a dynamic list.

ispair(item) -> bool                                         [procedure]
Returns true if item is a pair, false otherwise.

islist(item) -> bool                                         [procedure]
Returns true if item is a  list, false otherwise. A list is  one
of:

# The value of the constant nil, i.e. [].

# A pair whose back is [], a procedure, or another pair.

# A pair  whose  front  is  a boolean,  and  whose  back  is a
procedure, i.e. a dynamic list.

Returns true if item is a non-null pair.

null(list) -> bool                                           [procedure]
Returns true if the list list is empty, false otherwise. list is
empty if it is either

# The value of the constant nil, i.e. [].

# A pair with front false and back a procedure, i.e a  dynamic
list whose procedure has returned termin.

Note that  applying  null to  an  unexpanded dynamic  list  pair
causes it to be expanded.

lmember_=(item, list) -> sublist_or_false                    [procedure]
If item is  an element of  the list list,  returns the  trailing
portion of  list starting  with that  element, otherwise  false.
E.g.

lmember_=(2, [1 5 4 6 2 3 7 9]) =>
** [2 3 7 9]

lmember_=([3 4 5], [1 2 [3 4 5] 6 7]) =>
** [[3 4 5] 6 7]

Note that equality is  determined with the  operator =, that  is
the result will be  a list if list  contains an element that  is
structurally equal to item.

lmember(item, list) -> sublist_or_false                      [procedure]
If item is  an element of  the list list,  returns the  trailing
portion of  list starting  with that  element, otherwise  false.
E.g.

lmember(2, [1 5 4 6 2 3 7 9]) =>
** [2 3 7 9]

Note that, unlike lmember_=, equality is determined by using the
operator  ==  (absolute  equality),  which  generally  makes  it
faster. But

lmember([3 4 5], [1 2 [3 4 5] 6 7]) =>
** <false>

returns false because although the item argument is structurally
equal to a member of list, it is not the actual same structure.

member(item, list) -> bool                          [procedure variable]
The default procedure in this variable is the same as lmember_=,
but returns true instead of a sublist, i.e. member is defined as

lmember_=(item, list) and true

For example:

member(2, [1 5 4 6 2 3 7 9]) =>
** <true>

member([3 4 5], [1 2 [3 4 5] 6 7]) =>
** <true>

-----------------------------------------
3  Pair Constructor and Access Procedures
-----------------------------------------

conspair(item1, item2) -> pair                               [procedure]
Constructs and returns  a pair  whose front is  item1 and  whose
back is item2.

front(pair) -> item                                          [procedure]
item -> front(pair)
Returns or updates the front of the pair pair.

back(pair) -> item                                           [procedure]
item -> back(pair)
Returns or updates the back of the pair pair.

destpair(pair) -> (item1, item2)                             [procedure]
Returns two results, the front item1  and the back item2 of  the
pair pair.

recursive_front(item1) -> item2                              [procedure]
Repeatedly applies front to item1 while a pair, and then returns
whatever (non-pair) value results.

(This procedure is used by  syspr to extract a procedure's  name
from its pdprops  when printing the  procedure. The pdprops  can
thus contain (e.g) a pair whose front is the name and whose back
is some other data.)

lastpair(pair) -> item                                       [procedure]
item -> lastpair(pair)
Where pair is the first in a chain of pairs (usually a non-empty
list), returns  or  updates the  last  pair in  the  chain.  For
example:

vars l = [a b c d e];
lastpair(l) =>
** [e]
"f" -> lastpair(l);
l =>
** [a b c d|f]

(Note that in  this example, the  update operation has  replaced
the last pair in the list with a word -- hence it is no longer a
valid list.)

Since it operates at the pair level, lastpair will not  expand a
dynamic list, or even recognise one as such. (The last pair of a
dynamic list has the generator procedure in its back.)

------------------------------
4  List Constructor Procedures
------------------------------

nil -> list                                                   [constant]
Constant containing the unique item [], the empty list. Thus

nil -> x;

is equivalent to

[] -> x;

conslist(item1, item2, ..., itemN, N) -> list                [procedure]
Returns a list  list constructed  from the  top N  items on  the
stack.

cons(item, list1) -> list2                                   [procedure]
Constructs and returns a list whose head is item and whose  tail
is the list list1 (exactly like ::).

item :: list1 -> list2                                      [operator 4]
This operator constructs and returns  a list whose head is  item
and whose tail is the list list1.

initl(len) -> list                                           [procedure]
Constructs a list of length  len. Initially each element is  the
empty list nil.

pdtolist(p) -> list                                          [procedure]
Constructs and returns a dynamic list from the procedure p, i.e.
a pair whose front is true and whose back is the procedure  p. p
should produce  exactly one  item each  time it  is called,  and
<termin> (the value of the constant termin) as the last item.

expandlist(list) -> list                                     [procedure]
Returns  list  unchanged.  If  list  is  a  dynamic  list   then
expandlist will  expand  all  its elements  and  make  the  list
static. This  procedure will  loop  forever if  the list  is  of
infinite length.

sysconslist_onto(list1) -> list2                             [procedure]
The result list2 of this procedure  is a list consisting of  all
the  elements  on  the  user   stack  up  to  the  unique   item
<popstackmark>  (the  value   of  the  constant   popstackmark),
followed by the argument list list1.

Pop-11 list constructors use this with a trailing ^^ followed by
a variable, e.g,

[% 5, 6, 7, 8 %] -> list;
[% 1, 2, 3, 4 % ^^list ]

is equivalent to

popstackmark, 1, 2, 3, 4;
sysconslist_onto(list);

and produces the list [1 2 3 4 5 6 7 8].

sysconslist() -> list                                        [procedure]
Same as sysconslist_onto([]). Pop-11 list constructors use this,
i.e,

[% 1, 2, 3, 4 %]

is equivalent to

popstackmark, 1, 2, 3, 4;
sysconslist();

-------------------------
5  List Access Procedures
-------------------------

dest(list) -> tail_list -> head_item                         [procedure]
Returns two results,  the tail and  the head of  the list  list,
which must not be null.

Returns or updates the head of the list list, which must not  be
null.

tl(list) -> tail_list                                        [procedure]
tail_list -> tl(list)
Returns or updates the tail of the list list, which must not  be
null.

subscrl(N, list) -> item                                     [procedure]
item -> subscrl(N, list)
Returns or updates the N-th element of the list list (where  the
first element 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)

destlist(list) -> (item1, item2, ..., itemN, N)              [procedure]
Puts the N elements of the list list on the stack, together with
the number N.

dl(list) -> (item1, item2, ..., itemN)                      [procedure]
(item1, item2, ..., itemN) -> dl(list)
Puts the N elements of the list list on the stack, e.g.

dl([1 2 3 4])

is equivalent to 1, 2, 3, 4. The updater fills list with the top
N items from the stack, e.g.

vars list = [a b c d];
1, 2, 3, 4 -> dl(list);
list =>
** [1 2 3 4]

oneof(list) -> item                                          [procedure]
Returns a  randomly chosen  element of  list (using  the  random
number generator * random). For example:

vars list = [cat dog goat];
oneof(list) =>
** cat
oneof(list) =>
** goat

(list must not be empty.)

-----------------------
6  Other List Utilities
-----------------------

applist(list, p)                                             [procedure]
-> applist(list, p)
Applies the procedure p  to each element of  the list list.  The
updater applies  the  updater  of  p to  each  element  of  list
backwards, i.e.

-> applist(list, p)

is functionally the same as

applist(rev(list), updater(p))

Compare with maplist.

copylist(list1) -> list2                                     [procedure]
Returns a copy of the list, list1, i.e. list2 is a list in which
all the pairs are  copies of those in  list1. copylist does  not
copy elements of list1 which are themselves lists, see  copytree
for a recursive copier.

copytree(list1) -> list2                                     [procedure]
This makes a list, list2, which is a copy of list1. Any elements
of list1 which are themselves lists are recursively copied.

delete(item, list1)          -> list2                        [procedure]
delete(item, list1, eq_p)    -> list2
delete(item, list1, N)       -> list2
delete(item, list1, eq_p, N) -> list2
Deletes occurrences of  item from  list1, producing  a new  list
list2 (which shares the largest possible trailing sublist of the
original).

eq_p  is  an  optional  argument;  if  supplied,  it  must  be a
procedure of the form

eq_p(list_element, item) -> bool

eq_p is  used to  compare each  list element  against item,  and
those for which  it returns  true are deleted.  If not  supplied
eq_p defaults to nonop = (i.e. structure equality).

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]

(In this example, the  trailing sublist [9  8] is unaffected  by
the delete and will be shared with the original list.)

ncdelete(item, list1)          -> list2                      [procedure]
ncdelete(item, list1, eq_p)    -> list2
ncdelete(item, list1, N)       -> list2
ncdelete(item, list1, eq_p, N) -> list2
Same as delete (see  above), but does not  copy list pairs  that
need to  be changed,  and thus  (may) destructively  change  the
original list. The result list2 will be == to list1 unless there
are one or more  leading matching occurrences  of item that  are
deleted.

flatten(item) -> list                                        [procedure]
Returns a  list  of  all  the  items  produced  by  'recursively
list-destructing' item, where this means:

# if   item   is   a   list,   the   result   of   recursively
list-destructing each element;

# item otherwise.

In other words, 'flattens' every tree of lists or sub-lists that
can be traced from item.

listlength(list) -> N                                        [procedure]
Returns the number of elements n in the list list.

maplist(list1, p) -> list2                                   [procedure]
list2 -> maplist(list1, p)
Applies the procedure p to each element of the list list1,  and
returns a list  of all  results produced  in so  doing. This  is
equivalent to

[% applist(list1, p) %] -> list2

The action of the updater is

dl(list2) -> applist(list1, p)

ncmaplist(list, p) -> list                                   [procedure]
Applies procedure  p to  every element  of its  first  argument,
replacing that element with the  result of calling p.  ncmaplist
is destructive  in  that  it  re-uses the  pairs  of  its  first
argument. For example:

vars l = [0.6 2.2 2.9 4.0];
ncmaplist(l, round) =>
** [1 2 3 4]
l =>
** [1 2 3 4]

Compare with maplist.

rev(list1) -> list2                                          [procedure]
Returns a new list which is the list list1 reversed.

ncrev(list) -> list                                          [procedure]
Destructively reverses the order of  the elements of list,  i.e.
it re-uses the links of its argument.

setfrontlist(item, list1) -> list2                           [procedure]
Returns list2 formed by moving the  item to the front of  list1,

shuffle(list1) -> list2                                      [procedure]
Returns list2,  a  copy of  the  list list1  with  the  elements
randomly re-ordered.

nc_listsort(list, p) -> list                                 [procedure]
Sorts the argument list according  to the ordering procedure  p,
using a merge sort  algorithm. nc_listsort is Non-Copying  (i.e.
it re-uses the  list pairs  in list  in building  up the  sorted
result, and Non-Checking  (no checks  are made  to confirm  that
list is indeed a list, and dynamic lists are not expanded).

The ordering procedure p should be of the form

p(item1, item2) -> bool

i.e. a procedure which  takes two items  and returns true  (non-
false actually) if item1 should come before item2 in the  sorted
list. <= (for  numbers) and alphabefore  (for words or  strings)
are examples of this kind of procedure.

syssort(list, p) -> list                                     [procedure]
syssort(list, copy, p) -> list
Uses * nc_listsort to produce a sorted copy of list, unless  the
optional boolean argument copy is false, in which case the  sort
is non-copying. Dynamic  lists are expanded  before the  sorting
takes place.

sort(list1) -> list2                                         [procedure]
Returns a list of sorted items, using

syssort(list1, p) -> list2

If list1 begins with  a number, the operation  <= (less than  or
equal) is used for the ordering procedure p; otherwise, list1 is
assumed  to  contains  words  or  strings,  and  the   procedure
alphabefore is  used.  (If  the list  contains  both  words  and
numbers then a mishap will occur).

insertsort(list, p) -> list                                  [procedure]
Sorts list according  to the  comparison procedure  p, using  an
insert sort algorithm. insert_sort is non-copying.

flatlistify(list1) -> list2                                  [procedure]
Given a  list list1,  whose  elements include  sub-lists  and/or
vectors embedded  arbitrarily, flatlistify  will return  another
list list2 in which every sub-list or vector is replaced by  the
sequence of words  required to  compile it as  Pop-11 code  with
pop11_compile. For example:

vars x = [a [ b c { d e [ f ] g }] h];
vars y = flatlistify(x);
x =>
** [a [b c {d e [f] g}] h]
y =>
** [a [ b c { d e [ f ] g } ] h]
length(x) =>
** 3
length(y) =>
** 14

---------------------------------------------
7  Generic Data Structure Procedures on Lists
---------------------------------------------

The  following   generic  data   structure  procedures   (described   in
REF * DATA) are applicable to a list list:

length(list) -> N
Same as listlength(list).

explode(list) -> (item1, ..., itemN)
(item1, item2, ..., itemN) -> explode(list)
Applied to a list, explode is the same as dl.

last(list) -> item
item -> last(list)
Returns or updates the last element  of list (which must not  be
null).

allbutfirst(N, list) -> sub_list
allbutlast(N, list) -> sub_list
Return the sublist consisting of all the elements of list except
the first N (allbutfirst) or last N (allbutlast). In the case of
allbutfirst  this  will  be  an  actual  sublist  of  list;  for
allbutlast it will be a newly-constructed list.

datalength, appdata and fill treat lists as their first pair, i.e.  as a
data structure having two elements.

----------------
8  Miscellaneous
----------------

pair_key -> key                                               [constant]
nil_key -> key                                                [constant]
Constants holding key structures for  pairs and the unique  item
[] (see REF * KEYS).

assoc(list) -> assoc_p                                       [procedure]
Creates a procedure assoc_p  encoding an association table.  The
argument list  supplies initial  associations in  the form  of a
list of  two element  lists.  assoc_p when  given an  item  will
return its associated value, or false if there isn't one, i.e.

assoc_p(item) -> value

For anything but  very tiny association  tables, you should  use
properties rather than this procedure - see REF * PROPS.

appassoc(assoc_p, p)                                         [procedure]
Applies the  procedure  p  to  each  entry  in  the  association
structure assoc_p (which must have  been created by assoc).  The
procedure p is applied as:

p(item, value)

for each item/value association in assoc_p.

For convenience, appassoc  can also  be used  on properties.  In
this case, it is equivalent to calling appproperty.

--- C.all/ref/lists