Lisp function which adds parentheses in a certain way

Question

I'm trying to write a function which adds parentheses like this: (parens '(a b c d e)) returns (a (b (c (d (e))))). I'm just not seeing the pattern very well. What I have so far just returns a list with parentheses around each element. I can't seem to figure out how to make it look like that.

(DEFUN PARENS (L)
   (COND ((NULL L) NIL)
   (T (CONS (LIST (CAR L)) (PARENS (CDR L))))))

Answer 1

There are no parenthesis in a list. You're starting with a list of five elements, (a b c d e), and getting back a list of two elements, (a (b (c (d (e))))). The first element is a, and the second is another list, (b (c (d (e)))).

It's very easy to get close to this using reduce:

CL-USER> (reduce 'list '(a b c d e) :from-end t)
(A (B (C (D E))))

You can think of reduce as "injecting" the function list into (a b c d e) to produce

(list a (list b (list c (list d e))))

It's almost what you want. You actually want:

(list a (list b (list c (list d (list e)))))

How would you produce that? You can recurse down the list, and for each sublist (x . ys) you want to return (list x (recurse ys)), with the exception being when ys is (). You don't want to recurse into (), because you don't want a list with two elements, you actually want nothing. So the trick is stop recursing earlier than you typically do with a list. Thus:

(defun parens (l)
  (cond
    ((endp l) '())
    ((endp (rest l)) l)
    ((list (first l) (parens (rest l))))))      ; *

CL-USER> (parens '(a b c d e))
(A (B (C (D (E)))))
CL-USER> (parens '(a b))
(A (B))
CL-USER> (parens '(a))
(A)
CL-USER> (parens '())
NIL

^*Omitting the t test in the last clause is intentional. If there are no body forms in a cond clause, then the value of the test is returned. Thus (list …) serves both as the test form and the value form.

We can actually clean that up a little bit. The case of ((endp l) '()) could be ((endp l) l) since l is the empty list. But that means that in both the first and second cases, we can return l. We can call (rest '()) in Common Lisp and get back (), so (rest l) will be () when l is something like (e) and when l is (). This means that we can use:

(defun parens (l)
  (cond
    ((endp (rest l)) l)
    ((list (first l) (parens (rest l))))))

If we just have one test, though, we might as well just use if:

(defun parens (l)
  (if (endp (rest l))
      l
      (list (first l) (parens (rest l)))))

Answer 2

You can actually do it with reduce and some special consideration for the end:

(defun unflatten (list)
  (reduce #'list list
          :from-end t
          :end (1- (length list))
          :initial-value (last list)))

Note that last returns a list of the last n (default 1) elements.