gpt4 book ai didi

lambda - Scheme 中的 Y 组合器,使用惰性求值?

转载 作者:行者123 更新时间:2023-12-05 03:01:18 25 4
gpt4 key购买 nike

有谁知道如何在 Scheme 中实现 Y 组合器,特别是惰性求值和附加参数?我的理解是 Scheme (promise?) (delay) 和 (force) 提供惰性求值支持。

据我了解,带有应用程序的 Y 组合器如下所示,但由于默认情况下应用顺序评估,因此无法在 Scheme 中使用。

((lambda (f)
((lambda (x) (f (x x)))
(lambda (x) (f (x x)))))
(lambda (r) (r)))

这是一个建议的解决方案(Z 组合器),但是它使用另一个带参数的 lambda 函数作为解决方案:

;; Z-combinator
(define Z
(lambda (f)
((lambda (g) (f (g g)))
(lambda (g) (f (lambda args (apply (g g)
args)))))))
;Value: z

((Z (lambda (r)
(lambda (x)
(if (< x 2)
1
(* x (r (- x 1))))))) 5)
;Value: 120

;; end Z-combinator

根据解决方案更新

Y-combinator如下:

;; Y-combinator
(define Y
(lambda (f)
((lambda (x) (f (delay (x x))))
(lambda (x) (f (delay (x x)))))))
;Value: y

;; end Y-combinator

;; Non tail recursive
((Y (lambda (r)
(lambda (x)
(if (< x 2)
1
(* x ((force r) (- x 1)))))))
5)
;Value: 120

;; Tail - recursive
((Y (lambda (r)
(lambda (x acc)
(if (< x 2)
acc
((force r) (- x 1) (* x acc))))))
5 1)

;Value: 120

感谢您的指导!

最佳答案

是的,通过严格评估, self 应用程序 (x x) 会导致无限循环发生。如果你延迟这个,你可以使用 y 组合器,只要你也在它的使用位置“强制”那个延迟的对象:

(define (test)
(((lambda (f)
((lambda (x) (f (delay (x x))))
(lambda (x) (f (delay (x x))))))
(lambda (r)
(lambda (x)
(if (< x 2)
1
(* x ((force r) (- x 1)))))))
5))

对在严格设置下工作的 y 组合器进行变体的正常方法是 eta 扩展自应用程序,这是另一种延迟它但不需要明确应用力的方法。相反,强制是由函数应用程序完成的。

关于lambda - Scheme 中的 Y 组合器,使用惰性求值?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55979015/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com