你的代码
通常我们通过缩进来阅读Lisp代码,不需要全大写。因为我们通过缩进来阅读,所以不需要将右括号(或任何括号)放在单独的一行上。因此,您的代码应该这样格式化:
(defun split-list (l)
(cond
((null l) '())
((= 1 (length l)) (list (car l)))
(t (cons (cons (car l)
(split-list (cddr l)))
(cadr l)))))
正确处理基本情况
Split-list
应该始终返回两个列表。我们应该首先考虑这些基本情况。当l
为空时,左侧列表和右侧列表都没有任何内容,因此我们可以简单地返回'(() ())
。第一个条件变成了:
((null l) '(() ()))
根据您提供的第二个案例,我猜想您希望第二和第三种情况是:(i)如果只剩下一个元素,那么它必须是奇数,并属于左边结果;(ii)否则,至少还有两个元素,我们可以将每个元素加一。然后第二个条件应该是:
((= 1 (length l)) (list (car l) '()))
实际上,每一步检查
l
的长度是非常昂贵的。你只关心是否仅剩一个元素。你已经知道
l
不为空(来自第一个情况),因此您可以检查剩下的
l
是否为空列表。在处理cons单元作为列表时,我发现使用
first
和
rest
更易读,所以我会将第二个子句写成:
((endp (rest l)) (list (list (first l)) '()))
处理递归情况
现在,最终情况是至少有两个元素。这意味着l
看起来像 (x y . zs)
。你需要做的是在zs
上调用split-list
来获取形式为(odd-zs even-zs)
的一些结果,然后将其拆开并构造((x . odd-zs) (y . even-zs))
。代码如下:
(t (let ((split-rest (split-list (rest (rest l)))))
(list (list* (first l) (first split-rest))
(list* (second l) (second split-rest)))))
实际上,有一些方法可以使代码更加简洁。我们可以使用解构绑定同时提取odd-zs
和even-zs
。由于这是cond的最后一个子句,并且如果没有主体形式,子句将返回测试的值,因此我们不需要初始的t
。最后一条子句可以是:
((destructuring-bind (odd-zs even-zs)
(split-list (rest (rest l)))
(list (list* (first l) odd-zs)
(list* (second l) even-zs))))))
*我忽略了t
测试,因为如果cond
子句没有主体形式,则测试的值将被返回。在这里可以正常工作。
将所有内容组合起来,我们重新编写了您的代码:
(defun split-list (l)
(cond
((endp l) '(() ()))
((endp (rest l)) (list (list (first l)) '()))
((destructuring-bind (odd-zs even-zs)
(split-list (rest (rest l)))
(list (list* (first l) odd-zs)
(list* (second l) even-zs))))))
CL-USER> (split-list '(a b c 1 2 3))
((A C 2) (B 1 3))
CL-USER> (split-list '(a b c d 1 2 3))
((A C 1 3) (B D 2))
其他方法
我认为值得探索一些尾递归的方法,因为支持尾调用优化的实现可以将它们转换成循环。在Common Lisp中,尾递归函数通常也很容易转换成do
循环,这种循环更可能被实现为迭代。在这些解决方案中,我们会先以相反的顺序构建结果列表,然后在返回时再将其反转。
逐个元素进行递归
如果两个列表中的哪个先出现并不重要,您可以使用以下类似的方法:
(defun split-list (list &optional (odds '()) (evens '()))
(if (endp list)
(list (nreverse odds)
(nreverse evens))
(split-list (rest list)
evens
(list* (first list) odds))))
CL-USER> (split-list '(a b c 1 2 3))
((A C 2) (B 1 3))
CL-USER> (split-list '(a b c d 1 2 3))
((B D 2) (A C 1 3))
使用do
循环可以非常简洁地编写此代码,但通常被视为迭代而不是递归:
(defun split-list (list)
(do ((list list (rest list))
(odds '() evens)
(evens '() (list* (first list) odds)))
((endp list) (list (nreverse odds) (nreverse evens)))))
如果你需要始终将原列表的第一个元素放在列表的首位,就需要一些额外的逻辑。其中一种可能是:
(defun split-list (list &optional (odds '()) (evens '()) (swap nil))
(if (endp list)
(if swap
(list (nreverse evens)
(nreverse odds))
(list (nreverse odds)
(nreverse evens)))
(split-list (rest list)
evens
(list* (first list) odds)
(not swap))))
CL-USER> (split-list '(a b c 1 2 3))
((A C 2) (B 1 3))
CL-USER> (split-list '(a b c d 1 2 3))
((A C 1 3) (B D 2))
我认为
(if swap … …)
稍显丑陋。我们可以使用
cond
,这样我们就能得到多个表单(或者
if
和
progn
),在返回之前交换
odds
和
evens
的值。我认为这种方法更易读,但如果你的目标是一个纯递归解决方案(学术作业?),那么你可能会避免使用变量赋值,所以
rotatef
将不可用,而仅仅为了获取一些副作用而使用
when
可能会被人诟病。
(defun split-list (list &optional (odds '()) (evens '()) (swap nil))
(cond
((endp list)
(when swap (rotatef odds evens))
(list (nreverse odds) (nreverse evens)))
((split-list (rest list)
evens
(list* (first list) odds)
(not swap)))))
这同样适用于
do
:
(defun split-list (list)
(do ((list list (rest list))
(odds '() evens)
(evens '() (list* (first list) odds))
(swap nil (not swap)))
((endp list)
(when swap (rotatef odds evens))
(list (nreverse odds) (nreverse evens)))))
递归两个元素
另一种更直接的方法是通过cddr
(即(rest(rest…))
)向下递归列表,并在每次递归时向左右子列表添加元素。不过,我们需要小心,避免在输入元素数为奇数时意外地向right
列表中添加一个额外的nil
。
(defun split-list (list &optional (left '()) (right '()))
(if (endp list)
(list (nreverse left)
(nreverse right))
(split-list (rest (rest list))
(list* (first list) left)
(if (endp (rest list))
right
(list* (second list) right)))))
CL-USER> (split-list '(a b c 1 2 3))
((A C 2) (B 1 3))
CL-USER> (split-list '(a b c d 1 2 3))
((A C 1 3) (B D 2))
再来,一个 do
版本:
(defun split-list (list)
(do ((list list (rest (rest list)))
(left '() (list* (first list) left))
(right '() (if (endp (rest list)) right (list* (second list) right))))
((endp list) (list (nreverse left) (nreverse right)))))
cond
子句(基本情况)。首先修复这些问题,然后再继续处理最后一个子句。 - C. K. Young