Yコンビネータ

前置き

本文

xからyへの関数f
y = f x
fによって変わらない(不動の)点aのことを、関数fの不動点と呼ぶ
f a = a
fの不動点を返すような関数Yを不動点コンビネータと呼ぶ
Y f = a

(fが複数の不動点を持つ場合でも、fの不動点コンビネータは存在するのか??)

nの階乗を求める関数fact(再帰を使った関数定義の例として)
(define fact
  (lambda (n)
    (cond
     ((zero? n) 1)
     (else (* n (fact (- n 1)))))))
factをパラメータ化したλ
(lambda (fac)          ;;λ
  (lambda (n)
    (cond
     ((zero? n) 1)
     (else (* n (fac (- n 1)))))))
Yをλに適用すると、なんと、factができる
(Y λ)
λの不動点をaとすると
(Y λ) = a = (λ a)
3の階乗で試す
((Y λ) 3) = ((λ a) 3)
                                       ;;↓λの定義の、facがaで、nが3なので…
           = (* 3 (a (- 3 1)))
                                       ;;↓aをλ aに置き換えて…
           = (* 3 ((λ a) 2))
                                       ;;↓facがaで、nが2
           = (* 3 (* 2 (a (- 2 1))))
                                       ;;以下、同様
           = (* 3 (* 2 ((λ a) 1)))
           = (* 3 (* 2 (* 1 (a (- 1 1)))))
           = (* 3 (* 2 (* 1 ((λ a) 0))))
           = (* 3 (* 2 (* 1 1)))
           = 6
The Little SchemerのYコンビネータは、不動点コンビネータの一種
(define Y
  (lambda (le)
    ((lambda (f) (f f))
     (lambda (f)
       (le (lambda (x) ((f f) x)))))))
λに適用してみる
gosh> ((Y
(lambda (fac)
  (lambda (n)
    (cond
     ((zero? n) 1)
     (else (* n (fac (- n 1)))))))) 3)
6
gosh> ((Y
(lambda (fac)
  (lambda (n)
    (cond
     ((zero? n) 1)
     (else (* n (fac (- n 1)))))))) 5)
120
Last modified:2013/04/16 22:16:59
Keyword(s):
References:[FP: 関数型プログラミング]
This page is frozen.