递归分割列表的LISP函数

Question

分割列表函数接受一个列表并返回由输入交替元素组成的两个列表。我编写了以下代码：

(defun split-list (L)
  (cond
      ((endp L) (list NIL  NIL))
      (t (let ((X (split-list (cdr L))))
         (cond
             ((oddp (length L))
              (list (cons (first L) (first X)) (cadr X)))
             (t (list (first X) (cons (first L) (cadr X)))))))))

对于奇数长度的列表，输出结果如预期一般。第一个列表由第1、第3、第5等元素组成，而第二个部分则由第2、第4、第6等元素组成。然而，对于偶数长度的列表，返回的列表中，前1、2、3等元素在右侧，其余元素在左侧。

例如:

(SPLIT-LIST '(a b c 1 2 3))
(SPLIT-LIST RETURNED ((b 1 3) (a c 2))

这个顺序应该被交换。我的逻辑是否存在重大缺陷？我能否在不进行重大修改的情况下纠正这种情况？

- Bryan Charlie

---

编程问题/编码问题在这里不是主题，但可以在Stack Overflow上提问。 - D.W.

在每次递归调用中调用length不是一个好主意。它必须每次遍历列表l。 - Rainer Joswig

递归也不是一个好主意，因为它会受到可用堆栈大小的限制，从而限制处理能力。 - Rainer Joswig

一个可能有用的方法是逐个向下移动列表，跟踪“奇数或偶数位置”，并将元素添加到其中一个列表中。 - Joshua Taylor

递归作为一个概念工具，在开发解决方案时，总是一个好主意，可以帮助我们的思维。一旦正确的代码被制定出来，如果你的语言在处理递归方面受到限制，那么就重新编写它以使用其他方法。 - Will Ness

Answer 1

是的，您可以在不进行重大修改的情况下纠正问题。

1. 为 (endp (cdr L)) 添加一个情况
2. 对 cddr L 进行递归调用
3. 之后，else 情况将始终有两个新元素，一个要连接到每个列表上；不再需要 length 调用

- Doug Currie

Answer 2

首先，当你只有一个测试并且带有默认的t子句时，请使用if而不是cond。 此外，您正在使用first，但cadr；在您的上下文中，second比cadr更易读。

现在，对于偶数列表，顺序已经交换。尝试逐步执行。手动执行可能会有点繁琐，但这对于理解发生的事情非常有用。我个人更喜欢使用trace宏：(trace split-list)。然后，运行您的示例:

   0: (split-list (a b c 1 2 3))
    1: (split-list (b c 1 2 3))
      2: (split-list (c 1 2 3))
        3: (split-list (1 2 3))
          4: (split-list (2 3))
            5: (split-list (3))
              6: (split-list nil)
              6: split-list returned (nil nil)
            5: split-list returned ((3) nil)
          4: split-list returned ((3) (2))
        3: split-list returned ((1 3) (2))
      2: split-list returned ((1 3) (c 2))
    1: split-list returned ((b 1 3) (c 2))
  0: split-list returned ((b 1 3) (a c 2))

不清楚？尝试使用奇数长度的列表：

   0: (split-list (a b c 1 2))
    1: (split-list (b c 1 2))
      2: (split-list (c 1 2))
        3: (split-list (1 2))
          4: (split-list (2))
            5: (split-list nil)
            5: split-list returned (nil nil)
          4: split-list returned ((2) nil)
        3: split-list returned ((2) (1))
      2: split-list returned ((c 2) (1))
    1: split-list returned ((c 2) (b 1))
  0: split-list returned ((a c 2) (b 1))

看起来你总是把最里面的结果存储在左侧列表中！

一个可能的递归实现大致如下：

(defun split-list (list)
  (if (endp list)
      '(nil nil)
      (destructuring-bind (left right) (split-list (cddr list))
        (list (cons (first list) left)
              (if (second list)
                  (cons (second list) right)
                  right)))))

但是对于足够大的输入，这可能会导致堆栈溢出。以下是一种简单的非递归方法，使用 loop 实现：

(defun split-list (list)
    (loop for (a b) on list by #'cddr
          collect a into left
          when b 
            collect b into right
          finally (return (list left right)))

考虑到您可能需要在下个任务中将列表分成两个以上，这里提供一种更通用的版本，仍然使用循环：

(defun split-list (list &optional (n 2))
  (loop with a = (make-array n :initial-element nil)
        for e in list
        for c = 0 then (mod (1+ c) n)
        do (push e (aref a c))
        finally (return (map 'list #'nreverse a))))

(split-list '(a b c d e f g) 3)
=> ((a d g) (b e) (c f))

如果你想玩转循环列表，你也可以尝试这个方法，这适用于任何序列，不仅仅是列表：

(defun split-n (sequence &optional (n 2))
  (let* ((ring (make-list n :initial-element nil))
         (head ring)
         (last (last ring)))
    (setf (cdr last) ring)
    (map nil
         (lambda (u)
           (push u (first ring))
           (pop ring))
         sequence)
    (setf (cdr last) nil)
    (map-into head #'nreverse head)))

如果你计划调查这个功能，首先评估一下(setf *print-circle* t)。

- coredump

Answer 3

在递归列表处理中，一个常见的习语是以相反的顺序构建结果列表，然后在返回它们之前将它们反转。这个习语在这里可能很有用。你的任务的核心是返回两个列表，第一个列表应该包含偶数索引元素，第二个列表应该包含奇数索引元素。如果我要递归地解决这个问题，我会这样做。这个想法是维护一个偶数元素和奇数元素的列表，以及一个布尔值，指示我们是否处于整个列表的偶数或奇数位置。在每次递归时，我们向"evens"列表添加一个元素，因为当前列表的当前索引总是零，这总是偶数。诀窍在于，在每次递归调用时，我们交换偶数和奇数，并取反布尔值。最后，我们使用该布尔值来决定哪些列表是"真正的"偶数和奇数列表。

(defun split-list (list &optional (evens '()) (odds '()) (evenp t))
  "Returns a list of two lists, the even indexed elements from LIST
and the odd indexed elements LIST."
  (if (endp list)
      ;; If we're at the end of the list, then it's time to reverse
      ;; the two lists that we've been building up.  Then, if we ended
      ;; at an even position, we can simply return (EVENS ODDS), but
      ;; if we ended at an odd position, we return (ODDS EVENS).
      (let ((odds (nreverse odds))
            (evens (nreverse evens)))
        (if evenp
            (list evens odds)
            (list odds evens)))
      ;; If we're not at the end of the list, then we add the first
      ;; element of LIST to EVENS, but in the recursive call, we swap
      ;; the position of EVENS and ODDS, and we flip the EVENP bit.
      (split-list (rest list)
                  odds
                  (list* (first list) evens)
                  (not evenp))))

CL-USER> (split-list '())
(NIL NIL)
CL-USER> (split-list '(1))
((1) NIL)
CL-USER> (split-list '(1 2))
((1) (2))
CL-USER> (split-list '(1 2 3))
((1 3) (2))
CL-USER> (split-list '(1 2 3 4))
((1 3) (2 4))
CL-USER> (split-list '(1 2 3 4 5 6 7 8 9 10))
((1 3 5 7 9) (2 4 6 8 10))

- Joshua Taylor

Answer 4

递归总是一个好主意，作为一个概念工具，帮助我们思考问题的解决方案。一旦正确的代码被制定出来，如果你的语言在处理递归方面受限，就重新编写它以使用其他方法。

Scheme衍生语言的现代实现（Scheme是一种Lisp，对吧？），Racket具有无限递归，实现了堆上的调用栈。因此，递归算法的递归代码是完全可以的。

正确性/简单性优先，效率其次！

您的要求的简单解决方案是（在Haskell的可执行“伪代码”中）。

    foldr (\x [a, b] -> [x:b, a]) [[], []] 

我第一次看到这个巧妙的技巧是在旧的 F#（如果我没记错）答案中，由user ed'ka提供（如果我没记错）;已经有好几年了。但实际上，它似乎自从haskellwiki以来就一直存在。

用Scheme直接递归式编码，它是：

(define (split xs)
  (cond
    ((null? xs) (list '() '()))
    ((split (cdr xs)) => (lambda (acc) 
         (list (cons (car xs) (cadr acc))   ; always in the first subgroup!
               (car acc))))))               

列表的头元素必须出现在第一个子组中。不需要费力地安排它的出现，只需说出来，它就会自动发生，这是由于“递归”这种神奇的特性！

(split '(a b c 1 2 3))
(split '(a b c 1 2))

; '((a c 2) (b 1 3))
; '((a c 2) (b 1))

一件小事：我决定以后不再使用if，而是更喜欢使用cond，因为if的子句本身并没有说明它的激活条件 - 我们必须数一数所有的东西，才能知道哪个是哪个。使用cond就很明显了，在子句的开头就可以看到。

---

很容易修改这个程序，例如生成一个三分割，带有斜体。

(define (split3 xs)
  (cond
    ((null? xs) (list '() '() '()))
    (else (apply
           (lambda (a b c)             ; Scheme-style destructuring
             (list (cons (car xs) c)   ; rotate right:
                   a                   ;   xs's 2nd elt to appear in the 2nd group!
                   b))                 ;   head element of (cdr xs) is in `a`
           (split3 (cdr xs))))))       ; the recursive result

(split3 '(a b c 1 2 3))
(split3 '(a b c 1 2))

; '((a 1) (b 2) (c 3))
; '((a 1) (b 2) (c))

- Will Ness