在 Scheme 中递归拆分列表

Question

我想要做的是定义一个列表，例如 (define lst '(1 2 3 4 5 6)) 然后调用 (split lst) 它将返回 '((1 3 5) (2 4 6))。

一些例子：

• 如果lst是'(1 2 3 4 5 6)，它应该返回'((1 3 5) (2 4 6))
• 如果lst是'(1 2 3 4 5 6 7)，它应该返回'((1 3 5 7) (2 4 6))
• 如果lst是'("a" "little" "bit" "of" "that" "to" "spice" "things" "up")，它应该返回'(("a" "bit" "that" "spice" "up") ("little" "of" "to" "things"))

它应该在构建两个列表时交替。所以第一个索引应该在第一个列表中，第二个索引在第二个列表中，第三个索引在第一个列表中，依此类推。

这是我当前的脚本。

(define (split lst)
  (cond ((null? lst) lst)
        ((null? (cdr lst)) lst)
        ((cons (cons (car lst) (split (cddr lst))) (cons (cadr lst) (split (cddr lst)))))))

目前，这是我拆分列表时的输出 '(1 2 3 4 5 6)

((1 (3 (5) 6) 4 (5) 6) 2 (3 (5) 6) 4 (5) 6)

Answer 1

让我们逐步修复您的代码：

(define (split lst)
  (cond ((null? lst) lst)
        ((null? (cdr lst)) lst)
        ((cons (cons (car lst) (split (cddr lst))) (cons (cadr lst) (split (cddr lst)))))))

我注意到的第一件事是else在cond. 条件应该是这样的：

(cond (question-1 answer-1)
      (question-2 answer-2)
      ...
      (else else-answer))

随着else插入您的代码如下所示：

(define (split lst)
  (cond ((null? lst) lst)
        ((null? (cdr lst)) lst)
        (else
         (cons (cons (car lst) (split (cddr lst))) (cons (cadr lst) (split (cddr lst)))))))

接下来是第一个基本情况，或(null? lst)cond 问题的答案。在一个空列表上它应该返回什么？

似乎无论列表有多长，它都应该返回一个正好包含两个内部列表的列表。因此，何时lst为空，合乎逻辑的答案是(list '() '()).

(define (split lst)
  (cond ((null? lst) 
         (list '() '()))
        ((null? (cdr lst)) lst)
        (else
         (cons (cons (car lst) (split (cddr lst))) (cons (cadr lst) (split (cddr lst)))))))

接下来是第二个基本情况，即(null? (cdr lst))条件问题的答案。同样，它应该返回一个包含两个内部列表的列表：

(list ??? ???)

第一个索引应该放在第一个列表中，然后在第二个列表中没有任何内容。

(list (list (car lst)) '())

在您的代码上下文中：

(define (split lst)
  (cond ((null? lst)
         (list '() '()))
        ((null? (cdr lst))
         (list (list (car lst)) '()))
        (else
         (cons (cons (car lst) (split (cddr lst))) (cons (cadr lst) (split (cddr lst)))))))

现在，这个函数的行为是什么？

 > (split '(1 2 3 4 5 6))
 '((1 (3 (5 () ()) 6 () ()) 4 (5 () ()) 6 () ()) 2 (3 (5 () ()) 6 () ()) 4 (5 () ()) 6 () ())

仍然不是你想要的。那么最后一种情况，递归情况，应该做什么？

考虑您“给予”什么以及您需要“生产”什么。

鉴于：

• (car lst) 第一个元素
• (cadr lst) 第二个元素
• (split (cddr lst)) 正好两个内部列表的列表

你应该生产：

• (list ??? ???)

其中第一个???孔包含两个内部列表中的第一个元素和第一个元素，第二个???孔包含两个内部列表中的第二个元素和第二个元素。

这表明代码如下：

(list (cons (car lst)  (first (split (cddr lst))))
      (cons (cadr lst) (second (split (cddr lst)))))

或者，由于car获得第一个并cadr获得第二个：

(list (cons (car lst)  (car (split (cddr lst))))
      (cons (cadr lst) (cadr (split (cddr lst)))))

在您的代码上下文中：

(define (split lst)
  (cond ((null? lst)
         (list '() '()))
        ((null? (cdr lst))
         (list (list (car lst)) '()))
        (else
         (list (cons (car lst)  (car (split (cddr lst))))
               (cons (cadr lst) (cadr (split (cddr lst))))))))

使用它会产生你想要的：

> (split '(1 2 3 4 5 6))
'((1 3 5) (2 4 6))
> (split '(1 2 3 4 5 6 7))
'((1 3 5 7) (2 4 6))
> (split '("a" "little" "bit" "of" "that" "to" "spice" "things" "up"))
'(("a" "bit" "that" "spice" "up") ("little" "of" "to" "things"))

现在这和你以前的有什么区别？

您之前的代码：

(cons (cons (car lst)  (split (cddr lst)))
      (cons (cadr lst) (split (cddr lst))))

固定版本：

(list (cons (car lst)  (car (split (cddr lst))))
      (cons (cadr lst) (cadr (split (cddr lst)))))

第一个区别是您的原始版本cons在外面使用，而固定版本则使用list。这是因为(list ??? ???)总是返回一个正好包含两个元素的列表，而(cons ??? ???)可以返回一个任何大小大于 1 的列表，它将第一项合并到现有的第二个列表中。(list ??? ???)是您在这里想要的，因为您指定它应该返回正好包含两个内部列表的列表。

第二个区别在于您如何使用递归调用(split (cddr lst))。

这与您如何解释递归案例的“给定”部分有关。您假设第一次调用 tosplit会给您第一个“内部”列表，第二次调用 tosplit会给您第二个“内部”列表。事实上，它给你的清单都那些两次。因此，对于第一个，您必须获得“第一个”或“第一个” car，而对于第二个，您必须获得“第二个”或“第二个” cadr。