如何在 Racket 中仅使用 lambda 进行递归？

Question

我需要一些帮助来弄清楚如何仅使用 lambda 使下面的代码递归。

(define (mklist2 bind pure args)
  (define (helper bnd pr ttl lst)
    (cond [(empty? lst) (pure ttl)]
          [else (define (func t) (helper bnd pr (append ttl (list t)) (rest lst)))
           (bind (first lst) func)])
    )
  (helper bind pure empty args))

Answer 1

给定一个示例fact口头程序 -

(define fact
  (lambda (n)
    (if (= n 0)
        1
        (* n (fact (- n 1)))))) ;; goal: remove reference to `fact`

(print (fact 7)) ; 5040

上面fact是(lambda (n) ...)当我们调用时fact我们要求这个 lambda，所以我们可以用新的参数重新应用它。lambda是无名的，如果我们不能使用顶级define绑定，那么绑定变量的唯一方法是使用 lambda 的参数。想象一下——

(lambda (r)
  ; ...lambda body...
  ; call (r ...) to recur this lambda
)

我们只需something要让我们的(lambda (r) ...)行为这样——

(something (lambda (r)
  (print 1)
  (r)))

; 1
; 1
; 1
; ... forever

这something非常接近U组合器 -

(define u
  (lambda (f) (f f)))

(define fact
  (lambda (r)     ;; wrap in (lambda (r) ...)
    (lambda (n)
      (if (= n 0)
          1
          (* n ((r r) (- n 1))))))) ;; replace fact with (r r)

(print ((u fact) 7))

; => 5040

现在递归是通过使用参数发生的，我们可以有效地删除所有define绑定并仅使用lambda-

; ((u fact) 7)
(print (((lambda (f) (f f))  ; u
         (lambda (r)         ; fact
           (lambda (n)
             (if (= n 0)
                 1
                 (* n ((r r) (- n 1)))))))
        7))

; => 5040

U-combinator 很简单，但必须((r r) ...)在函数内部调用很麻烦。如果您可以(r ...)直接调用recur就好了。这正是 Y 组合器所做的 -

(define y
  (lambda (f)
    (f (lambda (x) ((y f) x))))) ;; pass (y f) to user lambda

(define fact
  (lambda (recur)
    (lambda (n)
      (if (= n 0)
          1
          (* n (recur (- n 1))))))) ;; recur directly

(print ((y fact) 7))

; => 5040

但是看看如何y有一个按名称递归定义？我们可以使用u删除按名称引用并使用lambda参数重复。和我们上面做的一样——

(define u
  (lambda (f) (f f)))

(define y
  (lambda (r)      ;; wrap in (lambda (r) ...)
    (lambda (f)
      (f (lambda (x) (((r r) f) x)))))) ;; replace y with (r r)

(define fact
  (lambda (recur)
    (lambda (n)
      (if (= n 0)
          1
          (* n (recur (- n 1)))))))

(print (((u y) fact) 7)) ;; replace y with (u y)

; => 5040

我们现在可以只使用lambda-

; (((u y) fact) 7)
(print ((((lambda (f) (f f))   ; u
          (lambda (r)          ; y
            (lambda (f)
              (f (lambda (x) (((r r) f) x))))))
         (lambda (recur)       ; fact
           (lambda (n)
             (if (= n 0)
                 1
                 (* n (recur (- n 1)))))))
        7))

; => 5040

通过使用柯里化，我们可以扩展我们的函数以支持更多参数，如果需要的话——

(define range
  (lambda (r)
    (lambda (start)
      (lambda (end)
        (if (> start end)
            null
            (cons start ((r (add1 start)) end)))))))

(define map
  (lambda (r)
    (lambda (f)
      (lambda (l)
        (if (null? l)
            null
            (cons (f (car l))
                  ((r f) (cdr l))))))))

(define nums
  ((((u y) range) 3) 9))

(define squares
  ((((u y) map) (lambda (x) (* x x))) nums))

(print squares)
; '(9 16 25 36 49 64 81)

作为一个单一的lambda表达 -

; ((((u y) map) (lambda (x) (* x x))) ((((u y) range) 3) 9))
(print (((((lambda (f) (f f)) ; u
           (lambda (r)        ; y
             (lambda (f)
               (f (lambda (x) (((r r) f) x))))))
          (lambda (r)         ; map
            (lambda (f)
              (lambda (l)
                (if (null? l)
                    null
                    (cons (f (car l))
                          ((r f) (cdr l))))))))
         (lambda (x) (* x x))) ; square
        (((((lambda (f) (f f)) ; u
            (lambda (r)        ; y
              (lambda (f)
                (f (lambda (x) (((r r) f) x))))))
           (lambda (r)         ; range
             (lambda (start)
               (lambda (end)
                 (if (> start end)
                     null
                     (cons start ((r (add1 start)) end)))))))
          3)   ; start
         9)))  ; end

; => '(9 16 25 36 49 64 81)

看看这些y使用惰性的很酷的实现

#lang lazy

(define y
  (lambda (f)
    (f (y f))))

#lang lazy

(define y
  ((lambda (f) (f f)) ; u
   (lambda (r)
     (lambda (f)
       (f ((r r) f))))))

#lang lazy

(define y
  ((lambda (r)
    (lambda (f)
      (f ((r r) f))))
  (lambda (r)
    (lambda (f)
      (f ((r r) f))))))