LISP: Reversing a dotted list

user_5762682 0
Viewed 213

There is a question in Common Lisp: A Gentle Introduction. The question is to get the last element in the list instead of cons cell. The macro LAST returns the cons cell in a dotted list. The question asked is to use the macro reverse instead of last, but both clisp and sbcl are throwing error.

(reverse '(a b c . d))
=> error

CLHS documentation says that we can reverse only a proper list (sequence) and not a dotted list or a circular list.

EDIT

I have written the program using LAST.

(defun last-element (x)
 "x is a list with last element as dotted pair"
  (cdr (last x)))

I am not sure how to use reverse in such a situation.

cons common-lisp lisp list
1 Answers

The function last returns the last cons cell for any proper list or dotted list, so long as the list is not circular.

It sounds like the question is about Exercise 6.6:

Use the LAST function to write a function called LAST-ELEMENT that returns the last element of a list instead of the last cons cell. Write another version of LAST-ELEMENT using REVERSE instead of LAST. Write another version using NTH and LENGTH.

The exercise would have specified dotted list input if that was the intention. When list is used in an unqualified way, it almost always means proper list. For a proper list last will return a cons cell with nil in the cdr, e.g., (last '(a b c d) --> (d . nil), or just (d), so the last element of a proper list is the car of the last cons cell.

If you want to handle both proper and dotted lists, you need to determine which the input is and handle it accordingly: for a dotted list the last "element" would be the cdr of the last cons cell. Handling the inputs accordingly for the reverse version means that you must determine whether the input is a proper list or a dotted list before applying reverse. You could write a function to convert a dotted list to a proper list before using reverse.

Technically speaking, the Standard does not consider the atom which terminates a dotted list to be one of its elements:

element n. 1. (of a list) an object that is the car of one of the conses that comprise the list.

For a proper list like (a b c d), nil is the terminating atom (since (a b c d) is identical to (a b c d . nil)), and (d . nil) is the last cons; d is the car of the last cons, and is thus the last element of the list. For a dotted list like (a b c . d), d is the terminating atom, and (c . d) is the last cons. Since c is the car of the last cons, c is the last true element, in the sense defined in the Standard, of the dotted list. It would probably be more accurate to say that d is the last member of (a b c . d).

But, Exercise 6.6 in Common Lisp: A Gentle Introduction is meant for proper lists only.

user_68798260
Related