list - 方案:返回一个表达式的所有元素，可以使用car和cdr的任意组合得到

Question

我正在尝试在我的 CS 类的 Scheme (R5RS) 中编写一个过程，该过程将表达式(符号或列表)作为参数并返回 (1) 所有可能的表达式的列表通过在表达式 and (2) 上使用 car 和 cdr 以及演示如何获得原始表达式的这些组件中的每一个的表达式形成。如果一件作品可以通过多种方式获得，则应多次归还。

Examples

(pieces '()) => ((() x))

(pieces 'apple) =>  ((apple x))

(pieces '(apple)) => (((apple) x) (apple (car x)) (() (cdr x)))

(pieces '(a (b c))) =>
               (((a (b c)) x)
                (a (car x))
                (((b c)) (cdr x))
                ((b c) (car (cdr x)))
                (b (car (car (cdr x))))
                ((c) (cdr (car (cdr x))))
                (c (car (cdr (car (cdr x)))))
                (() (cdr (cdr (car (cdr x)))))
                (() (cdr (cdr x))))

由于我们刚刚开始使用 Scheme，因此我们只能使用相当基本的语法来完成这项任务。这是我到目前为止所拥有的:

(define pieces
  (lambda (exp)
    (cond
      ((symbol? exp)
       (list exp 'x))
      ((null? exp)
       (list '() 'x))
      ((list? exp)
       (let ((b (pieces (car exp))) (c (pieces (cdr exp))))
          (list exp 'x b c))))))

(pieces '()) => (() x)

(pieces 'apple) => (apple x)

(pieces '(apple)) => ((apple) x (apple x) (() x))

(pieces '(a (b c))) => ((a (b c)) x (a x) (((b c)) x ((b c) x (b x) ((c) x (c x) (() x)))
                       (() x)))

该过程返回所有正确的元素，但每次递归都会导致组件嵌套在一个附加列表中。有什么办法可以避免吗？

此外，对于问题的第二部分，我不知道从哪里开始(显示每个元素是如何使用 car 和 cdr 从原始元素中获取的)。我已经尝试了上百万种不同的方法，但没有一种接近奏效。如果有人对如何实现该功能有任何提示或建议，我将不胜感激。非常感谢。

Answer 1

(pieces 'apple) => (apple x)

但它应该是((apple x))，对吧？您应该得到一个列表，其中第一个也是唯一一个元素是列表 (apple x)。

终止递归的 cond 子句(exp 是一个符号或 null)返回应该进入列表的项目，而在 car 和 cdr 上重复出现的子句尝试创建项目列表。由于 pieces 可以返回项目和项目列表，因此很难从它返回的值中创建项目列表:当您执行 (list exp 'x b c) 你不知道 b 和 c 是应该进入列表还是项目列表的项目。

如果您确保 pieces 始终返回项目列表(例如 (list (list exp 'x)))，事情就会变得容易得多。当您重复使用 car 和 cdr 时，您想要执行类似 append 列表 a 和 b 的操作 并将“当前”((list exp 'x)) 项添加到该列表(可能带有 cons 或其他内容)。

对于第二部分，pieces 必须知道它是如何到达当前项目的。您可以使 pieces 将当前项目的“路径”作为(可能是可选的)参数。如果路径是一个列表，那么当您在 (car exp) 上调用 pieces 时，您可以向您要访问的路径添加一个 car 符号作为参数发送，对于 (cdr exp)，您可以添加符号 cdr。然后你使用路径创建一些很好的东西来替代 (list exp 'x) 中的 'x。