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

Question

注意:这是一种家庭作业，但又不是——最终目标是拥有一个函数，该函数可以生成一组数字的幂集，这些数字作为数字列表提供给该函数。我有一个函数的递归版本，但我现在需要找到一些方法来替换我的解决方案中的每个显式递归函数(append、mapm 等)等效的 lambda-only 表达式。

因此，我从较小的问题开始，希望将它们全部组合起来编写一个完整的函数。我已经设法使用纯 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 组合器在 "The Why of Y" ^(PDF) 中得到了很好的发展。你一定要检查一下。

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