0

如果我有这样的递归函数：

(define (double-n-times x n)
  (if (= n 0)
      x
      (double-n-times (* 2 x) (- n 1))))

我怎样才能制作它的 lambda 版本并且从不给它命名？...就像我想在某处内联它一样。那可能吗？（我的意思是在这种情况下我可以使用 fold - 所以这个例子可能不是那么好） - 是否有某种我无法找到的“自我”符号或占位符？或者你只需​​要给它一个名字。

4

3 回答 3

1

您的问题的答案是肯定的，通过使用宏。但在我说这个之前，我必须先问这个：你问是因为你只是好奇吗？或者你问是因为有一些问题，比如你不想用名字污染命名空间？

如果您不想用名称污染命名空间，您可以简单地使用局部构造，如 named let、letrec甚至 Y 组合器。或者，您可以define将(let () ...).

(let ()
  (define (double-n-times x n)
    (if (= n 0)
        x
        (double-n-times (* 2 x) (- n 1))))
  (double-n-times 10 10))

;; double-n-times is not in scope here

对于实际答案：这是一个rlam类似于的宏lambda，但它允许您使用self来引用自身：

#lang racket

(require syntax/parse/define)

(define-syntax-parse-rule (rlam args body ...+)
  #:with self (datum->syntax this-syntax 'self)
  (letrec ([self (λ args body ...)])
    self))

;; compute factorial of 10
((rlam (x)
   (if (= 0 x)
       1
       (* x (self (sub1 x))))) 10) ;=> 3628800
于 2021-12-17T18:23:42.053 回答
1

是的。作为名称的占位符是lambda 函数的参数的用途：

(define (double-n-times x n)
  (if (= n 0)
      x
      (double-n-times (* 2 x) (- n 1))))
=
(define double-n-times (lambda (x n)
  (if (= n 0)
      x
      (double-n-times (* 2 x) (- n 1)))))
=
(define double-n-times (lambda (self)   ;; received here
                         (lambda (x n)
  (if (= n 0)
      x
      (self (* 2 x) (- n 1))))))       ;; and used, here

但是这个“ ”参数是什么？self它是 lambda 函数本身：

= ;; this one's in error...
(define double-n-times ((lambda (u)   ;; call self with self
                          (u u))   ;; to receive self as an argument
                  (lambda (self)
                    (lambda (x n)
  (if (= n 0)
      x
      (self (* 2 x) (- n 1)))))))
  ;; ...can you see where and why?

= ;; this one isn't:
(define double-n-times ((lambda (u) (u u))
                  (lambda (self)
                    (lambda (x n)
  (if (= n 0)
      x
      ((self self) (* 2 x) (- n 1)))))))

 ;; need to call self with self to actually get that 
 ;; (lambda (x n) ... ) thing to be applied to the values!

现在它起作用了：(double-n-times 1.5 2)返回6.0.

这已经很好了，但我们不得不在((self self) ... ...)那里写来表达二进制递归调用。我们能做得更好吗？(self ... ...)我们可以像以前一样使用常规调用语法编写 lambda 函数吗？让我们来看看。是吗

= ;; erroneous
(define double-n-times ((lambda (u) (u u))
                  (lambda (self)
                    (lambda (x n)
                      (lambda (rec body) (self self)
  (if (= n 0)
      x
      (rec (* 2 x) (- n 1))))))))

（不）或者是

= ;; also erroneous...
(define double-n-times ((lambda (u) (u u))
                  (lambda (self)
                    (lambda (x n)
                      ((lambda (rec body) body)
                          (self self)
  (if (= n 0)
      x
      (rec (* 2 x) (- n 1))))))))   ;; ...can you see why?

（还是没有）或者也许

= ;; still erroneous...
(define double-n-times ((lambda (u) (u u))
                  (lambda (self)
                    ((lambda (rec)
                       (lambda (x n)
  (if (= n 0)
      x
      (rec (* 2 x) (- n 1)))))
                             (self self) ))))

（再次没有......以一种有趣的方式）或者实际上是

=
(define double-n-times ((lambda (u) (u u))
                  (lambda (self)
                    ((lambda (rec)
                       (lambda (x n)
  (if (= n 0)
      x
      (rec (* 2 x) (- n 1)))))
                             (lambda (a b) ((self self) a b)) ))))

（是的！）这样它就可以被抽象并分离成

(define (Y2 g) ((lambda (u) (u u))
                  (lambda (self)
                    (g
                             (lambda (a b) ((self self) a b))))))

(define double-n-times (Y2
                    (lambda (rec)      ;; declare the rec call name
                       (lambda (x n)
  (if (= n 0)
      x
      (rec (* 2 x) (- n 1)))))))       ;; and use it to make the call

我们有了它，在Scheme 的严格评估策略下的二元函数的Y组合子。

因此，我们首先使用我们选择的递归调用名称关闭我们的二进制 lambda 函数，然后使用Y2组合器将这个“rec spec” 嵌套的 lambda转换为一个普通的可调用二进制 lambda 函数（即，它需要两个参数）。

或者当然名称rec本身并不重要，只要它不干扰我们代码中的其他名称。特别是上面也可以写成

(define double-n-times                          ;; globally visible name
                  (Y2
                    (lambda (double-n-times)    ;; separate binding,
                       (lambda (x n)            ;;    invisible from
  (if (= n 0)                                   ;;    the outside
      x
      (double-n-times (* 2 x) (- n 1)))))))     ;; original code, unchanged

定义与结果完全相同的函数。

这样，我们根本不必更改原始代码，只需用另一个lambda与我们预期的递归调用名称相同的参数将其关闭double-n-times，从而使此绑定匿名，即使该名称无法从外部观察到; 然后通过Y2组合器传递它。

当然，Scheme 已经有了递归绑定，我们可以通过使用来达到同样的效果letrec：

(define double-n-times           ;; globally visible name
  (letrec ((double-n-times       ;; internal recursive binding:
             (lambda (x n)       ;; its value, (lambda (x n) ...)
                (if (= n 0)   
                  x
                  (double-n-times (* 2 x) (- n 1))))))
     double-n-times))            ;; internal binding's value

内部名称和全局名称再次相互独立。

于 2021-12-17T23:25:09.973 回答
1

Racket 中的 Y-Combinator 是：

(lambda (f)
    ((lambda (h) (h h))
     (lambda (g) (f (lambda args (apply (g g) args))))))

该函数可以采用任何匿名函数并将其递归地应用于自身。

让我们定义您的功能部分。double-n-times-部分仅用 lambdas 编写：

(lambda (f)
    (lambda (x n)
      (if (= n 0) x (f (* 2 x) (- n 1))))))

f我们可以随心所欲地命名——所以我们也可以这样称呼它double-n-part。

如果我们对此应用 Y-Combinator，我们得到：

((lambda (f)
    ((lambda (h) (h h))
     (lambda (g) (f (lambda args (apply (g g) args))))))
  (lambda (f)
    (lambda (x n)
      (if (= n 0) x (f (* 2 x) (- n 1))))))

这会吐出一个函数，该函数接受参数x并将n第二个定义的内部函数应用于它们。

所以现在，没有任何命名函数 - 只使用lambda表达式 - 你可以应用你的参数 - 让我们说x=3and n=4：

(((lambda (f)
    ((lambda (h) (h h))
     (lambda (g) (f (lambda args (apply (g g) args))))))
  (lambda (f)
    (lambda (x n)
      (if (= n 0) x (f (* 2 x) (- n 1))))))
 3 4)
;;=> 48 ; as expected (3 * 2 * 2 * 2 * 2)

这样阅读更方便。但是我们也可以定义Y combinatorwithoutapply和argswhen 我们只允许单子函数（只有一个参数的函数）而不是可变参数。然后它看起来像这样（我们必须像这样一个接一个地给出参数）：

((((lambda (f)
      ((lambda (h) (h h))
        (lambda (g) (f (lambda (x) ((g g) x))))))
    (lambda (f)
      (lambda (x)
        (lambda (n)
          (if (= n 0) x ((f (* 2 x)) (- n 1)))))))
 3) 4)
;;=> 48
于 2021-12-17T09:35:24.987 回答