带有 Y 组合器的列表函数没有递归，为什么？

Question

注意：这是一种家庭作业，而不是一种 - 最终目标是拥有一个函数，该函数生成一组数字的幂集，作为数字列表提供给该函数。我有函数的递归版本，但现在我需要找到解决方案我有（替换每个明确递归函数的一些方法append，mapm等等）与只相当于λ-表达。

因此，我从较小的问题开始，并希望将它们全部结合起来编写一个完整的函数。我已经设法使用纯 lambda（Y 组合子）提出了一个非递归阶乘函数，但我现在正在尝试提出一个很好的函数，该函数可以对列表中的每个数字进行平方——尝试在跳转之前解决较小的问题直到一个乘法递归函数：

(define (sqrlist numlist)
  (((lambda (f)
   ((lambda (x) (x x))
    (lambda (g)
     (f (lambda (x) ((g g) x))))))
  (lambda (f)
   (lambda (x)
    (cons (sqr (first x)) (rest x))))) numlist))

上面的代码不会递归，尽管在它之前存在 Y 组合器——我显然在将正确的参数传递给其中的函数时遇到了一些问题——有什么想法吗？

Answer 1

如果您有工作程序，则转换为匿名程序相对简单和机械。给每个 lambda 一个额外的参数，它是“本身”，并复制过程。所以

(define (add-list list) 
  (if (empty? list) 
      0 
      (+ (first list) (add-list (rest list)))))

成为

(?(list) (if (empty? list) 0 (+ (first list) (add-list (rest list)))))

这当然是一个问题，因为add-list没有定义。因此，我们必须确保每次都经过自己。

(?(self list) (if (empty? list) 0 (+ (first list) (self self (rest list)))))

但是，我们首先要在哪里找到自己？好吧，我们复制并粘贴（并给它一个参数）

((?(self list) (if (empty? list) 0 (+ (first list) (self self (rest list)))))
 (?(self list) (if (empty? list) 0 (+ (first list) (self self (rest list)))))
 '(1 2 3 4))

将这个“复制和粘贴”抽象到Y组合器在“Y 的原因” ^（PDF）中得到了很好的发展，你一定要检查一下。

但请记住，第一步是“让它发挥作用”。在抽象掉defines之前执行此操作。