7.2 Construction of List Structure

The following simple example has been included to illustrate the exact construction of list structures. Two types of list structures are shown, and a function for deriving one from the other is given in LISP.

We assume that we have a list of the form

$l_{1} = ((A B C) (D E F),\ldots ,(X Y Z)),$

which is represented as

|  .---.---.  .---.---.      .---.---.
`->|   |   |->|   |   |->- ->|   |***|
   `---'---'  `---'---'      `---'---'
     |          |              |
     |          |            .-V-.---.  .---.---.  .---.---.
     |          |            | X |   |->| Y |   |->| Z |***|
     |          |            `---'---'  `---'---'  `---'---'
     |          |
     |        .-V-.---.  .---.---.  .---.---.
     |        | D |   |->| E |   |->| F |***|
     |        `---'---'  `---'---'  `---'---'
     |
   .-V-.---.  .---.---.  .---.---.
   | A |   |->| B |   |->| C |***|
   `---'---'  `---'---'  `---'---'

and that we wish to construct a list of the form

$l_{2} = ((A (B C)) (D (E F)), \ldots , (X (Y Z)))$

which is represented as

|  .---.---.  .---.---.      .---.---.
`->|   |   |->|   |   |->- ->|   |***|
   `---'---'  `---'---'      `---'---'
     |          |              |
     |          |  .-----------'
     |          |  |  .---.---.  .---.---.  .---.---.  .---.---.
     |          |  `->| X |   |->|   |***|  | Y |   |->| Z |***|
     |          |     `---'---'  `---'---'  `---'---'  `---'---'
     |          |                  `----------^
     |        .-V-.---.  .---.---.  .---.---.  .---.---.
     |        | D |   |->|   |***|  | E |   |->| F |***|
     |        `---'---'  `---'---'  `---'---'  `---'---'
     |                     `----------^
   .-V-.---.  .---.---.  .---.---.  .---.---.
   | A |   |->|   |***|  | B |   |->| C |***|
   `---'---'  `---'---'  `---'---'  `---'---'
                `----------^

We consider the typical substructure, (A (B C)) of the second list $l_{2}$. This may be constructed from A, B, and C by the operation

        cons[A;cons[cons[B;cons[C;NIL]];NIL]]

or, using the list function, we can write the same thing as

        list[A;list[B;C]]

In any case, given a list, x, of three atomic symbols,

        x = (A B C),

the arguments A, B, and C to be used in the previous construction are found from

        A = car[x] 
        B = cadr[x] 
        C = caddr[x]

The first step in obtaining $l_{2}$ from $l_{1}$ is to define a function, grp, of three arguments which creates (X (Y Z)) from a list of the form (X Y Z).

        grp[x] = list[car[x];list[cadr[x];caddr[x]]]

Then grp is used on the list $l_{1}$, under the assumption that $l_{1}$ is of the form given. For this purpose, a new function, mitgrp, is defined as

        mltgrp[l] = [null[l] $\rightarrow$ NIL; 
                        T $\rightarrow$ cons[grp[car[l]];mltgrp[cdr[l]]]]

So mltgrp applied to the list $l_{1}$ takes each threesome, (X Y Z), in turn and applies grp to it to put it in the new form, (X (Y Z)) until the list $l_{1}$ has been exhausted and the new list $l_{2}$ achieved.