TAOCP 2.3 Exercise 19

The List $L = (a,(L))$ consists of two elements: the first element is the atom $a$, and the second element is a List identical to $L$ itself.

taocpmathematicsalgorithmsvolume-1

Section 2.3: Trees

Exercise 19. [**] [15] Draw a List diagram analogous to (7) for the List $L = (a,(L))$. What is L[2] in this List? What is L[2,1,1]?

Verified: no
Solve time: 35s

The List $L = (a,(L))$ consists of two elements: the first element is the atom $a$, and the second element is a List identical to $L$ itself. In List diagram notation, $L$ is represented as a node whose head points to $a$ and whose tail points to a sublist whose head points back to $L$ and whose tail is empty (or null). Thus L[2] refers to the second element of $L$, which is the sublist $(L)$. The first element of this sublist is L itself; therefore L[2,1,1] is the first element of the first element of L[2], which reduces to a.

Explicitly:

  • L[2] = (L)
  • L[2,1] = L
  • L[2,1,1] = L[1] = a

This completes the proof.

∎

$\boxed{L[2] = (L),\ L[2,1,1] = a}$