我在使用这个函数时遇到了问题。 我们一开始被问到"编写一个 lisp 函数，它接受一个列表和一个整数 n，并返回列表的前 n 个元素，作为新列表。如果 n 小于 1，则返回 NIL。如果 n 超出长度，该函数将返回原始列表的副本。
(defun take-n (list n)
(cond
((= n 0) ())
((null list) list)
((cons(car list)(take-n(cdr list)(- n 1)))))
)
到目前为止，我从上面的问题中得到的是：
(defun cut-in-half(list)
(let (x (ceiling(/ (length list) 2)))(let* (reverse list))
(list (take-n list x)(cdr(take-n y x))))
)
我做错了什么？
看看你是否可以围绕这个想法建立你的家庭作业：
[1]> (loop with l = '(1 2 3 4 5 6 7)
for x on l
for y = x then (cddr y)
when (null y)
return (values (ldiff l x) x))
(1 2 3 4) ;
(5 6 7)
[2]> (loop with l = '(1 2 3 4 5 6 7 8)
for x on l
for y = x then (cddr y)
when (null y)
return (values (ldiff l x) x))
(1 2 3 4) ;
(5 6 7 8)
这是我过去在实现二进制合并排序时所做的那种事情(用于将列表切成两半，递归地对两半进行排序，合并)。基本上，我们有两个光标贯穿列表;一个步进双倍的时间，以两倍的速度点击列表的末尾(使用cddr步而不是cdr)，这使另一个光标位于中间。
注意在loop中，for x on l语法与执行for x = l then (cdr l)大致相同，外加终止测试，以便在x变为空时结束循环。我们可以这样做，因为我们不需要对x进行终止测试。即
[9]> (loop with l = '(1 2 3 4 5 6 7 8)
for x = l then (cdr x)
for y = x then (cddr y)
when (null y)
return (values (ldiff l x) x))
(1 2 3 4) ;
(5 6 7 8)
这很好，因为x和y子句遵循相同的形式，并且cdr和cddr之间的对比是明确的。
要返回两个列表的列表，请使用list而不是values。由于 Common Lisp 有多个值，因此利用它而不是分配额外的列表单元格是习惯性的。
这里有几个版本在概念上是干净的(没有破坏性操作，即使是隐含的)，但也许有点难以理解。 两者都比任何明显的(隐式)破坏性版本做更多的工作。 两者都尝试不使用具有非恒定时间复杂度的函数，除了它们自己定义的函数(因此，例如，没有调用reverse或length)。 两者都将迭代表示为尾递归。
这两者都是为了了解如何仅使用相当原始的操作而不使用破坏性操作来构建事物，并且不使用显式迭代构造，但这往往会花费您更多的共识和时间。
对我来说，目的也是为了表明这些"干净"的问题变体通常比"肮脏"变体更难理解。 然而，这是意见。
两者都将列表的两半作为多个值返回。 两者都不适合作为家庭作业答案。
第一个版本的工作原理是：
- 沿着列表向下走，计算其长度并构建反向副本;
- 沿着那个反向副本向下走，将其累积成另外两个反向副本之一，这就是结果。
这个版本有效地遍历了两次列表，并构建了一个完整的反向副本，然后构建了一个完整的反向副本。
(defun halfify (list)
;; Return two values: a copy of the first half of LIST and a copy of
;; the second half of LIST. 'half' is defined as by (round (length
;; list) 2).
;;
;; This works by walking down the list to accumulate a reversed copy
;; of it and its length: half/accum does this. When this is done,
;; rev/split then walks down the reversed copy accumulating a
;; further reversed copy into one of two accumulators.
;;
;; This walks the list twice, and conses essentially two copies of
;; it.
(labels ((half/accum (tail n accum)
(if (null tail)
(rev/split accum (round n 2) '() '())
(half/accum (rest tail) (1+ n) (cons (first tail) accum))))
(rev/split (tail n h1 h2)
(cond ((null tail)
(values h1 h2))
((> n 0)
(rev/split (rest tail) (1- n) (cons (first tail) h1) h2))
(t
(rev/split (rest tail) n h1 (cons (first tail) h2))))))
(half/accum list 0 '())))
第二个版本的工作原理是：
- 沿着列表向下移动以计算其长度;
- 使用计算的长度在 halg 中拆分列表，向后累积拆分(列表的前导部分);
- 使用累加器反转前导块。
这稍微更有效：它有效地遍历列表两次(一次用于计算长度，然后是两次半遍)，但它只与列表一样多，因为它将前半部分合并两次，一次向后，然后一次反转它。
请注意，此函数返回的列表尾部与原始列表的尾部共享结构：对于第一个函数，情况并非如此。
(defun halfify (list)
;; Return two values: a copy of the first half (rounded) of the
;; list, and the remainder of it.
;;
;; This does essentially two walks down the list (once to compute
;; the length, half to build a reversed of the first half and then
;; half again to reverse it, and conses as much as the whole list
;; (half for the reversed half-copy, half to reverse it). I don't
;; think you can do better than this without code which is
;; implicitly destructive, or not tail-recursive.
(labels ((half (tail n)
(if (null tail)
(split list (round n 2) '())
(half (rest tail) (1+ n))))
(split (tail m results)
(if (zerop m)
(values (rev results '()) tail)
(split (rest tail) (1- m) (cons (first tail) results))))
(rev (tail result)
(if (null tail)
result
(rev (rest tail) (cons (first tail) result)))))
(half list 0)))
最后，我读到了 Kaz 的聪明提示，这里有一个使用这个技巧的版本。如果长度为奇数，此版本将始终在其中间点之前剪切列表。
(defun halfify (list)
(labels ((half/step (fast slow a)
(if (null fast)
(values (rev a '()) slow)
(let ((fast-tail (rest fast)))
(if (null fast-tail)
(values (rev a '()) slow)
(half/step (rest fast-tail) (rest slow)
(cons (first slow) a))))))
(rev (tail result)
(if (null tail)
result
(rev (rest tail) (cons (first tail) result)))))
(half/step list list '())))