时间戳

首页 > 解决方案 > 在 Scheme 中递归拆分列表

scheme - 在 Scheme 中递归拆分列表

问题描述

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

一些例子：

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

这是我当前的脚本。

(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)

标签： schemeracket

解决方案

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

(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))cond 问题的答案。同样，它应该返回一个正好包含两个内部列表的列表：

(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))。

这与您如何解释递归案例的“给定”部分有关。你假设第一次调用split会给你第一个“内部”列表，第二次调用split会给你第二个“内部”列表。事实上，它为您提供了这两个时间的列表。所以对于第一个你必须得到“第一个”或car它，而对于第二个你必须得到“第二个”或cadr它。

推荐阅读