Programming with lists

2.7 Programming with lists

There are several methods available to construct a list:

     u := nil;
     u :=1 . u;
     u :=2 . u;

Starting with an empty list, elements are pushed on its front one after the other, here giving (2 1). Please note the blank between the number and the dot: this is necessary as otherwise the dot would have been parsed as part of the number representing a floating point value.

     u := {9,10};
     u := 1 .u;
     u := 2 .u;

The same, here not starting with the empty list giving (2 1 9 10). The for statement has special forms to handle lists:

for each x in l performs an action elementwise for the elements in list l; the elements are accessible by the automatically declared local variable x one after the other.
the iterator actions collect and join allow you to construct lists:
- collect generates a list where each iteration step produces exactly one element,
- join expects that each iteration step produces a complete list (or nil) and joins them to one long list.

Examples: let e.g. l be a list of numbers (1 - 2 3 - 4 5 - 6):

m:=for each x in l sum x;

m will be the sum of the elements,

s:=for each x in l collect x*x;

s is computed as list with the numbers from x squared,

p:=for each x in l join
if x>0 then {x} else nil;

in this loop the positive numbers produce one element lists, while the negative numbers are mapped to nil; joined together the result is a list with only the positive elements,

r:=for i:=1:10 collect -r;

here the result is the list with numbers (-1 - 2 - 3 ⋅⋅⋅ - 10). The lists produced by collect and join are in “correct” order. Warning: In symbolic mode join links the lists in place for maximum speed ⁵: The last CDR pointer of the first list is modified to point to the head of the second list , and so on. This is no problem if the joined objects are freshly built structures, or if there are no other references to them. If the in – place operation is dangerous for your application, you must copy the structure before, e.g. by a call to append with NIL as second argument:

r:=for i:=1:10 join append(my_extract(u,r),nil);

In this example, the top level chain of the results of my_extract is copied such that the original structure is not modified when joining.

Another very common style for list operations is to use iterative or recursive programs. The following programs each sum the elements of the list:

   symbolic procedure sum_1(l);
    begin  integer n;
      while l do <<n:=n+car l; l:=cdr l>>;
      return n;
    end;

This program picks in each step of the the while loop one element from the list and sets the variable l to the successor position; the loop terminates as soon as the successor nil is found .

symbolic procedure sum_2(l);
if null l then 0 else car l + sum_2(cdr l);

This program uses recursion for the same task. The program will go down the list until nil is found, then set the sum to 0 and when coming back from the recursion add the elements to the sum so far.

   symbolic procedure sum_3(l); sum_31(l,0); % initializing
   symbolic procedure sum_31(l,n);
     if null l then n else sum_31(cdr l,car l+n);

The third example is a bit tricky: it initializes the sum to 0, and when stepping down in the recursion the sum is updated and passed to the next recursion level as a parameter.

It is also very common to produce lists in recursive style, e.g. inverting the signs in a list of numbers could be written as

symbolic procedure invertsgn(l);
if null l then nil else -car l . invertsgn(cdr l);

and with most LISP compilers this program would as efficient as the corresponding loop

for each x in l collect -x;

but produce less code. Note that as with for each - collect, the elements in the resulting list will be in the original order. The recursive programming style is typical for LISP and it is used for hundreds of REDUCE routines.

PrevTail

Front