Converting a dotted pair to a two-element list in LISP

Question

I am new to lisp and working on a homework problem to flatten a nested list. I have my funciton working except it needs to 'remove' dotted pairs. So given (1 (2 3) (4 . 5) ((6 7) (89))) my function should output (1 2 3 4 5 6 7 8 9).

So.. my actual question..

Given a dotted pair e.g (1 . 2), how can I get the list '(1 2)?

Answer 1

A cons cell is a structure that has two parts, called its car and its cdr. The pair (1 . 2) is a cons cell whose car is 1 and whose cdr is 2. Lists in Lisps are built up from cons cells and nil. How this works is described in lots of places, including the answer to Recursive range in Lisp adds a period? A list is either the empty list () (also called nil), or a cons whose car is the first element of the list and whose cdr is another list which is the rest of the list. That means that a list

(1 2)

is built of cons cells and nil as

(cons 1 (cons 2 nil))

If you've already got (1 . 2), then you can get 1 and 2 with car and cdr. You'd put them back together as just described. That is,

(let ((x '(1 . 2)))
  (cons (car x) (cons (cdr x) nil)))

Alternatively, you could just use list:

(let ((x '(1 . 2)))
  (list (car x) (cdr x)))

If you want to reuse the same cons cell, you could replace the cdr of the cell with (cons 2 nil). For instance (and note that we're not quoting the pair anymore, because modifying literal data is undefined behavior):

(let ((x (cons 1 2)))
  (setf (cdr x) (cons (cdr x) nil))
  x)

That could also be

(let ((x (cons 1 2)))
  (setf (cdr x) (list (cdr x)))
  x)

You could also use rplacd:

(let ((x (cons 1 2)))
  (rplacd x (list (cdr x)))
  x)