LISP defines a function (nth NL) that returns the
N'th member of list L (assuming that the elements are numbered
from zero onwards):
A D V E R T I S E M E N T
USER(59): (nth 0 '(a b c d))
A
USER(60): (nth 2 '(a b c d))
C
We could implement our own version of nth by linear recursion. Given N and L, either L is nil or it is constructed by cons.
Case 1: L is nil.
Accessing the N'th element is an undefined operation, and our
implementation should arbitrarily return nil to indicate this.
Case 2: L is constructed by a cons.
Then L has two components: (first L) and
(rest L). There are two subcases: either N = 0 or
N > 0:
Case 2.1: N = 0.
The zeroth element of L is simply (first L).
Case 2.2: N > 0.
The N'th member of L is exactly the (N-1)'th
member of (rest L).
The following code implements our algorithm:
(defun list-nth (N L)
"Return the N'th member of a list L."
(if (null L)
nil
(if (zerop N)
(first L)
(list-nth (1- N) (rest L)))))
Recall that (1- N) is merely a shorthand for (- N 1). Notice
that both our implementation and its correctness argument closely follow the
standard pattern of structural recursion. Tracing the execution of the function,
we get:
USER(61): (list-nth 2 '(a b c d))
0: (LIST-NTH 2 (A B C D))
1: (LIST-NTH 1 (B C D))
2: (LIST-NTH 0 (C D))
2: returned C
1: returned C
0: returned C
C
USER(62): (last '(a b c d))
(d)
USER(63): (last '(1 2 3))
(3)
Implement your own version of last using linear recursion. You may
assume that (last nil) returns nil. Compare your
implementation with the standard pattern of structural recursion.
Notice that we have a standard if-then-else-if structure in our
implementation of list-nth. Such logic can alternatively be implemented
using the cond special form.
(defun list-nth (n L)
"Return the n'th member of a list L."
(cond
((null L) nil)
((zerop n) (first L))
(t (list-nth (1- n) (rest L)))))
The cond form above is evaluated as follows. The condition (null L)
is evaluated first. If the result is true, then nil is returned.
Otherwise, the condition (zerop n) is evaluated. If the condition
holds, then the value of (first L) is returned. In case neither of the
conditions holds, the value of (list-nth (1- n) (rest L)) is returned.
Example: member
LISP defines a function (member EL) that returns
non-NIL if E is a member of L.
USER(64): (member 'b '(perhaps today is a good day to die)) ; test fails
NIL
USER(65): (member 'a '(perhaps today is a good day to die)) ; returns non-NIL
'(a good day to die)
We implement our own recursive version as follows:
(defun list-member (E L)
"Test if E is a member of L."
(cond
((null L) nil)
((eq E (first L)) t)
(t (list-member E (rest L)))))
The correctness of the above implementation is easy to justify. The list L
is either constructed by nil or by a call to cons:
Case 1: L is nil. L is empty, and there is no way E is in L.
Case 2: L is constructed by cons
Then it has two components: (first L) and (rest L).
There are two cases, either (first L) is E
itself, or it is not.
Case 2.1: E equals (first L).
This means that E is a member of L,
Case 2.2: E does not equal (first L).
Then E is a member of L iff E is a member of
(rest L).
Tracing the execution of list-member, we get the following:
USER(70): (list-member 'a '(perhaps today is a good day to die))
0: (LIST-MEMBER A (PERHAPS TODAY IS A GOOD DAY TO DIE))
1: (LIST-MEMBER A (TODAY IS A GOOD DAY TO DIE))
2: (LIST-MEMBER A (IS A GOOD DAY TO DIE))
3: (LIST-MEMBER A (A GOOD DAY TO DIE))
3: returned T
2: returned T
1: returned T
0: returned T
T
In the implementation of list-member, the function call (eq
xy) tests if two symbols are the same. In fact, the
semantics of this test determines what we mean by a member:
USER(71): (list-member '(a b) '((a a) (a b) (a c)))
0: (LIST-MEMBER (A B) ((A A) (A B) (A C)))
1: (LIST-MEMBER (A B) ((A B) (A C)))
2: (LIST-MEMBER (A B) ((A C)))
3: (LIST-MEMBER (A B) NIL)
3: returned NIL
2: returned NIL
1: returned NIL
0: returned NIL
NIL
In the example above, we would have expected a result of t. However,
since '(a b) does not eq another copy of '(a b) (they
are not the same symbol), list-member returns nil. If we want
to account for list equivalence, we could have used the LISP built-in function
equal instead of eq. Common LISP defines the following set of
predicates for testing equality:
(= xy)
True if x and y evaluate to the same number.
(eq xy)
True if x and y evaluate to the same symbol.
(eql xy)
True if x and y are either = or eq.
(equal xy)
True if x and y are eql or if they
evaluate to the same list.
(equalp xy)
To be discussed in Tutorial 4.
Example: append
LISP defines a function append that appends one list by another:
USER(72): (append '(a b c) '(c d e))
(A B C C D E)
We implement a recursive version of append. Suppose we are given two
lists L1 and L2. L1 is either nil or
constructed by cons.
Case 1: L1 is nil.
Appending L2 to L1 simply results in L2.
Case 2: L1 is composed of two parts: (first L1)
and (rest L1). If we know the result of appending L2
to (rest L1), then we can take this result, insert
(first L1) to the front, and we then have the list we want.
USER(73): (list-append '(a b c) '(c d e))
0: (LIST-APPEND (A B C) (C D E))
1: (LIST-APPEND (B C) (C D E))
2: (LIST-APPEND (C) (C D E))
3: (LIST-APPEND NIL (C D E))
3: returned (C D E)
2: returned (C C D E)
1: returned (B C C D E)
0: returned (A B C C D E)
(A B C C D E)
