list - Simply Scheme Lisp 中的子集/子序列递归过程

Question

我正在结合伯克利 2011 年夏季 CS3 类(class)学习 Simply Scheme。我正在努力理解 subset/subsequence 过程。看到解决方案代码后，我了解了基 native 制，但我很难掌握足够的概念来自己提出解决方案。

谁能给我指明方向，帮助我更好地理解它？或者也许他们自己有不同的解释？

这是我目前理解的基础:

因此，在下面的过程中，作为 prepend 参数的 subsequences 递归调用正在将 word 分解为其最基本的元素，prepend 将 word 的 first 添加到每个元素。

; using words and sentences

(define (subsequences wd)
  (if (empty? wd)
      (se "")
      (se (subsequences (bf wd))
          (prepend (first wd) 
                   (subsequences (bf wd))))))

(define (prepend l wd)
  (every (lambda (w) (word l w))
         wd))

; using lists

(define (subsequences ls)
  (if (null? ls)
      (list '())
      (let ((next (subsequences (cdr ls))))
        (append (map (lambda (x) (cons (car ls) x))
                     next)
                next)))) 

所以第一个，当输入 (subsequences 'word) 时，将返回:

    ("" d r rd o od or ord w wd wr wrd wo wod wor word)

第二个，当输入 (subsequences '(1 2 3)) 时，将返回:

    ((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) ())

因此，正如我所说，这段代码有效。我分别了解代码的每个部分，并且在大多数情况下了解它们如何相互协作。嵌套的递归调用给我带来了麻烦。我只是不太了解它，无法自己编写此类代码。任何可能帮助我理解它的东西都将不胜感激。我想我只需要一个新的视角来思考它。

提前感谢任何愿意为我指出正确方向的人。

编辑:

所以第一条评论要求我尝试解释一下我目前所理解的内容。开始了:

对于单词/句子过程，我认为它通过出现在第二位的递归调用将变量分解为它的“最基本”情况(可以这么说)。

然后它基本上是在最基本的情况下，通过前置。

我真的不明白为什么首先出现的递归调用需要在那里。

在列表中，当我自己写的时候，我得到了这个:

(define (subseq lst)
  (if (null? lst)
      '()
      (append (subseq (cdr lst))
              (prepend (car lst)
                       (subseq (cdr lst))))))

(define (prepend i lst)
  (map (lambda (itm) (cons i itm)) 
       lst))

在我看来，如果使用正确的解决方案，列表中的 car 就会掉落而不会被计入，但显然情况并非如此。我不明白这两个递归调用是如何协同工作的。

Answer 1

您的替代解决方案大部分都很好，但是您犯了很多人在第一次实现此(列表的幂集)函数时犯的同样错误:您的基本情况是错误的。

有多少种方法可以从 0 元素列表中选择 0 项或更多项的子集？ “0”可能感觉很明显，但实际上有一种方法:不选择任何项目。因此，与其返回空列表(意思是“没有办法完成它”)，您应该返回 (list '()) (意思是，“一种方法的列表，即不选择任何元素”)。等效地，您可以返回 '(())，它与 (list '()) 相同 - 我不知道好的 Scheme 样式，所以我会离开对你来说。

一旦您进行了更改，您的解决方案就会起作用，这证明您毕竟确实理解了递归!

---

至于解释提供给您的解决方案，我不太明白您认为列表中的 car 会发生什么。它实际上与您自己编写的算法几乎完全相同:要查看它有多接近，请内联您对 prepend 的定义(也就是说，将其主体替换为您的子序列 功能)。然后从提供的解决方案中扩展 let 绑定(bind)，在它出现的两个地方替换它的主体。最后，如果需要，您可以将参数的顺序交换为 append - 或者不交换；没关系。此时，它与您编写的函数相同。