有人知道如何在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组合子的表达式如下:
;; 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
感谢您的指导!