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

Question

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

因此，我从较小的问题开始，希望将它们全部结合起来编写一个完整的函数。我已经设法使用纯 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)，您一定要查看一下。

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

Answer 2

这是一个可能的答案，我知道你已经解决了它，但有第二个意见可能会很有用:)

((lambda (X)
    ((lambda (proc)
       (proc proc))
     (lambda (proc)
       (X (lambda (arg)
            ((proc proc) arg))))))
  (lambda (sqrlist)
    (lambda (lst)
      (if (null? lst)
          '()
          (cons (* (car lst) (car lst))
                (sqrlist (cdr lst)))))))

它是“仅限 lambda”，因为它专门用匿名函数编写，它甚至不使用 定义。调用方法如下：

(((lambda (X)
     ((lambda (proc)
        (proc proc))
      (lambda (proc)
        (X (lambda (arg)
             ((proc proc) arg))))))
   (lambda (sqrlist)
     (lambda (lst)
       (if (null? lst)
           '()
           (cons (* (car lst) (car lst))
                 (sqrlist (cdr lst)))))))
 '(1 2 3 4 5))