3

注意：这是一种家庭作业，有点不是——最终目标是让一个函数产生一组数字的幂集，作为数字列表提供给函数。我有该函数的递归版本，但我现在需要找到一些方法，用等效的 lambda-only 表达式替换我拥有的解决方案（等）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 组合器——我显然在将正确的参数传递给其中的函数时遇到了一些问题——有什么想法吗？

4

2 回答 2

5

如果您有一个工作程序，转换为匿名程序相对简单和机械。给每个 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）中得到了很好的开发，您一定要检查一下。

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

于 2011-12-01T16:12:34.453 回答
1

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

((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”，因为它是专门根据匿名函数编写的，它甚至不使用define. 以下是如何调用它：

(((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))
于 2011-11-24T18:43:28.677 回答