3

特に遅延評価と追加の引数を使用して、SchemeでYコンビネーターを実装する方法を知っている人はいますか? 私の理解では、Scheme (promise?) (delay) と (force) は遅延評価のサポートを提供します。

アプリケーションを使用した Y コンビネータは次のように理解していますが、デフォルトでは適用可能な順序評価のため、Scheme では機能しません。

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

これは推奨される解決策 (Z コンビネーター) ですが、解決策として引数を持つ別のラムダ関数を使用します。

;; 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

ご指導よろしくお願いします!

4

2 に答える 2