% Copyright The Numerical Algorithms Group Limited 1992-94. All rights reserved.
% !! DO NOT MODIFY THIS FILE BY HAND !! Created by ht.awk.
\newcommand{\ListXmpTitle}{List}
\newcommand{\ListXmpNumber}{9.47}
%
% =====================================================================
\begin{page}{ListXmpPage}{9.47 List}
% =====================================================================
\beginscroll
A \spadgloss{list} is a finite collection of elements in a specified
order that can contain duplicates.
A list is a convenient structure to work with because it is easy
to add or remove elements and the length need not be constant.
There are many different kinds of lists in \Language{}, but the
default types (and those used most often) are created by the
\spadtype{List} constructor.
For example, there are objects of type \spadtype{List Integer},
\spadtype{List Float} and \spadtype{List Polynomial Fraction Integer}.
Indeed, you can even have \spadtype{List List List Boolean}
(that is, lists of lists of lists of Boolean values).
You can have lists of any type of \Language{} object.

\beginmenu
    \menudownlink{{9.47.1. Creating Lists}}{ugxListCreatePage}
    \menudownlink{{9.47.2. Accessing List Elements}}{ugxListAccessPage}
    \menudownlink{{9.47.3. Changing List Elements}}{ugxListChangePage}
    \menudownlink{{9.47.4. Other Functions}}{ugxListOtherPage}
    \menudownlink{{9.47.5. Dot, Dot}}{ugxListDotPage}
\endmenu
\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugxListCreateTitle}{Creating Lists}
\newcommand{\ugxListCreateNumber}{9.47.1.}
%
% =====================================================================
\begin{page}{ugxListCreatePage}{9.47.1. Creating Lists}
% =====================================================================
\beginscroll

The easiest way to create a list with, for example, the elements
\spad{2, 4, 5, 6} is to enclose the elements with square
brackets and separate the elements with commas.
\xtc{
The spaces after the commas are optional, but they do improve the
readability.
}{
\spadpaste{[2, 4, 5, 6]}
}
\xtc{
To create a list with the single element \spad{1}, you can use
either \spad{[1]} or the operation \spadfunFrom{list}{List}.
}{
\spadpaste{[1]}
}
\xtc{
}{
\spadpaste{list(1)}
}
\xtc{
Once created, two lists \spad{k} and \spad{m} can be
concatenated by issuing \spad{append(k,m)}.
\spadfunFrom{append}{List} does {\it not} physically join the lists,
but rather produces a new list with the elements coming from the two
arguments.
}{
\spadpaste{append([1,2,3],[5,6,7])}
}
\xtc{
Use \spadfunFrom{cons}{List} to append an element onto the front of a
list.
}{
\spadpaste{cons(10,[9,8,7])}
}

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugxListAccessTitle}{Accessing List Elements}
\newcommand{\ugxListAccessNumber}{9.47.2.}
%
% =====================================================================
\begin{page}{ugxListAccessPage}{9.47.2. Accessing List Elements}
% =====================================================================
\beginscroll

\labelSpace{4pc}
\xtc{
To determine whether a list has any elements, use the operation
\spadfunFrom{empty?}{List}.
}{
\spadpaste{empty? [x+1]}
}
\xtc{
Alternatively, equality with the list constant \spadfunFrom{nil}{List} can
be tested.
}{
\spadpaste{([] = nil)@Boolean}
}

\xtc{
We'll use this in some of the following examples.
}{
\spadpaste{k := [4,3,7,3,8,5,9,2] \bound{k}}
}
\xtc{
Each of the next four expressions extracts the \spadfunFrom{first}{List}
element of \spad{k}.
}{
\spadpaste{first k \free{k}}
}
\xtc{
}{
\spadpaste{k.first \free{k}}
}
\xtc{
}{
\spadpaste{k.1 \free{k}}
}
\xtc{
}{
\spadpaste{k(1) \free{k}}
}
The last two forms generalize to \spad{k.i} and \spad{k(i)},
respectively, where
\texht{$ 1 \leq i \leq n$}{\spad{1 <= i <= n}}
and
\spad{n} equals the length of \spad{k}.
\xtc{
This length is calculated by \spadopFrom{\#}{List}.
}{
\spadpaste{n := \#k \free{k}}
}
Performing an operation such as \spad{k.i} is sometimes
referred to as {\it indexing into k} or
{\it elting into k}.
The latter phrase comes about because the name of the operation
that extracts elements is called \spadfunFrom{elt}{List}.
That is, \spad{k.3} is just alternative syntax for \spad{elt(k,3)}.
It is important to remember that list indices
begin with 1.
If we issue \spad{k := [1,3,2,9,5]} then \spad{k.4}
returns \spad{9}.
It is an error to use an index that is not in the range from
\spad{1} to the length of the list.

\xtc{
The last element of a list is extracted by any of the
following three expressions.
}{
\spadpaste{last k \free{k}}
}
\xtc{
}{
\spadpaste{k.last \free{k}}
}
\xtc{
This form computes the index of the last element and then
extracts the element from the list.
}{
\spadpaste{k.(\#k) \free{k}}
}

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugxListChangeTitle}{Changing List Elements}
\newcommand{\ugxListChangeNumber}{9.47.3.}
%
% =====================================================================
\begin{page}{ugxListChangePage}{9.47.3. Changing List Elements}
% =====================================================================
\beginscroll

\labelSpace{4pc}
\xtc{
We'll use this in some of the following examples.
}{
\spadpaste{k := [4,3,7,3,8,5,9,2] \bound{k}}
}
\xtc{
List elements are reset by using the \spad{k.i} form on
the left-hand side of an assignment.
This expression resets the first element of \spad{k} to \spad{999}.
}{
\spadpaste{k.1 := 999 \free{k}\bound{k1}}
}
\xtc{
As with indexing into a list, it is an error to use an index
that is not within the proper bounds.
Here you see that \spad{k} was modified.
}{
\spadpaste{k \free{k1}}
}

The operation that performs the assignment of an element to a particular
position in a list is called \spadfunFrom{setelt}{List}.
This operation is {\it destructive} in that it changes the list.
In the above example, the assignment returned the value \spad{999} and
\spad{k} was modified.
For this reason, lists are called \spadglos{mutable} objects: it is
possible to change part of a list (mutate it) rather than always returning
a new list reflecting the intended modifications.
\xtc{
Moreover, since lists can share structure, changes to one list can
sometimes affect others.
}{
\spadpaste{k := [1,2] \bound{k2}}
}
\xtc{
}{
\spadpaste{m := cons(0,k) \free{k2}\bound{m}}
}
\xtc{
Change the second element of \spad{m}.
}{
\spadpaste{m.2 := 99 \free{m}\bound{m2}}
}
\xtc{
See, \spad{m} was altered.
}{
\spadpaste{m \free{m2}}
}
\xtc{
But what about \spad{k}?
It changed too!
}{
\spadpaste{k  \free{m2 k2}}
}

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugxListOtherTitle}{Other Functions}
\newcommand{\ugxListOtherNumber}{9.47.4.}
%
% =====================================================================
\begin{page}{ugxListOtherPage}{9.47.4. Other Functions}
% =====================================================================
\beginscroll

\labelSpace{3pc}
\xtc{
An operation that is used frequently in list processing is that
which returns all elements in a list after the first element.
}{
\spadpaste{k := [1,2,3] \bound{k}}
}
\xtc{
Use the \spadfunFrom{rest}{List} operation to do this.
}{
\spadpaste{rest k \free{k}}
}

\xtc{
To remove duplicate elements in a list \spad{k}, use
\spadfunFrom{removeDuplicates}{List}.
}{
\spadpaste{removeDuplicates [4,3,4,3,5,3,4]}
}
\xtc{
To get a list with elements in the order opposite to those in
a list \spad{k}, use \spadfunFrom{reverse}{List}.
}{
\spadpaste{reverse [1,2,3,4,5,6]}
}
\xtc{
To test whether an element is in a list, use \spadfunFrom{member?}{List}:
\spad{member?(a,k)} returns \spad{true} or \spad{false}
depending on whether \spad{a} is in \spad{k} or not.
}{
\spadpaste{member?(1/2,[3/4,5/6,1/2])}
}
\xtc{
}{
\spadpaste{member?(1/12,[3/4,5/6,1/2])}
}

As an exercise, the reader should determine how to get a
list containing all but the last of the elements in a given non-empty
list \spad{k}.\footnote{\spad{reverse(rest(reverse(k)))} works.}

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugxListDotTitle}{Dot, Dot}
\newcommand{\ugxListDotNumber}{9.47.5.}
%
% =====================================================================
\begin{page}{ugxListDotPage}{9.47.5. Dot, Dot}
% =====================================================================
\beginscroll

Certain lists are used so often that \Language{} provides an easy way
of constructing them.
If \spad{n} and \spad{m} are integers, then \spad{expand [n..m]}
creates a list containing \spad{n, n+1, ... m}.
If \spad{n > m} then the list is empty.
It is actually permissible to leave off the \spad{m} in the
dot-dot construction (see below).

\xtc{
The dot-dot notation can be used more than once in a list
construction and with specific elements being given.
Items separated by dots are called {\it segments.}
%-% \HDindex{segment}{ugxListDotPage}{9.47.5.}{Dot, Dot}
}{
\spadpaste{[1..3,10,20..23]}
}
\xtc{
Segments can be expanded into the range of items between the
endpoints by using \spadfunFrom{expand}{Segment}.
}{
\spadpaste{expand [1..3,10,20..23]}
}
\xtc{
What happens if we leave off a number on the right-hand side of
\spadopFrom{..}{UniversalSegment}?
}{
\spadpaste{expand [1..]}
}
What is created in this case is a \spadtype{Stream} which is a
generalization of a list.
See \downlink{`Stream'}{StreamXmpPage}\ignore{Stream} for more information.
\endscroll
\autobuttons
\end{page}
%