function - 以某种方式添加括号的 Lisp 函数

Question

我正在尝试编写一个添加括号的函数，如下所示:(parens '(a b c d e)) 返回 (a (b (c (d (e)))))。我只是不太清楚这种模式。到目前为止，我只返回一个列表，每个元素都带有括号。我似乎无法弄清楚如何让它看起来像那样。

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

Answer 1

列表中没有括号。您从包含五个元素的列表 (a b c d e) 开始，然后返回包含两个元素的列表 (a (b (c (d (e)))))。第一个元素是a，第二个是另一个列表(b (c (d (e))))。

使用 reduce 很容易接近:

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

您可以将 reduce 视为将函数 list“注入(inject)”到 (a b c d e) 中以生成

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

这几乎就是您想要的。你实际上想要:

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

你会如何制作它？您可以向下递归列表，并且对于每个子列表 (x . ys) 您想要返回 (list x (recurse ys))，但当 ys 是 ()。您不想递归到 ()，因为您不想要包含两个元素的列表，您实际上什么都不想要。所以诀窍是比通常使用列表更早地停止递归。因此:

(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

^*在最后一个子句中省略 t 测试是有意的。如果 cond 子句中没有主体形式，则返回测试值。因此 (list …) 既作为测试形式又作为值形式。

我们实际上可以稍微清理一下。 ((endp l) '()) 的情况可能是 ((endp l) l) 因为 l 是空列表。但这意味着在第一种和第二种情况下，我们都可以返回 l。我们可以在 Common Lisp 中调用 (rest '()) 并返回 ()，所以 (rest l) 将是 ( ) 当 l 类似于 (e) 和 当 l 是 () 。这意味着我们可以使用:

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

不过，如果我们只有一个测试，我们不妨只使用 if:

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