FC2ブログ
--.--
--
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

11.28
Wed
Yコンビネータ難しいですね

最近ずっと考えてたんですがなかなか理解できなかったんですが、

すこーしわかったような気がするので忘れないようにメモしてみます

Yコンビネータを使うと、無名関数で再帰できるようになります。

関数名与えてやらなくても再帰できるんです!

今回はそのちょっと手前辺りまでをメモしときます

再帰の例としてお馴染みfactでやってみます

まず普通に定義してみる


(define fact 
    (lambda (n) (if (zero? n) 1 (* n (fact (- n 1))))))



Pythonでも書いていく


def fact(n):
    if n == 0 : return 1
    return n * fact(n - 1)



さて、無名再帰したいのでそれぞれ「defineやdefしてるfactって名前使えない。

でも再帰なんで自分自身を呼ばなきゃいけないのでしょうがないので、

自分自身を引数でもらってそれを呼ぶことにする

つまりこうする.


(define fact
	(lambda (func)
		(lambda (n)
			(if (zero? n)
				1
				(* n  ((func func) (- n 1)))))))
((fact fact) 5)



ここでのfuncってのは自分自身(つまりfact)が与えられてる。

つまりこのfuncを呼んでやればfactって書いて再帰するのと同じ感じになります。

だけど、ちょっとややこしくなってる部分があります

(* n ((func func) (- n 1)))

これはfuncという関数(fact)にfuncという関数を与えている

なぜなら、factは自分自身を示す関数をと、数nの2つをとるので。

これでギリギリfactという定義された関数名を呼んでないですね!!(funcがfactに同じなので)


def fact(f , n):
    if n == 0 :
        return 1
    else:
        return n * f(f , n -1)

fact(fact , 5)


あとはこれをlambdaで書いてやれば、無名再帰は出来るんですが、

Yコンビネータにはあと一歩ある.でも今回はそこまでしか書かないです.まだ理解があれなのでw

で、lambdaでかいてく


(lambda (func)
    (lambda (n)
        (if (zero? n) 1 (* n ((func func) (- n 1))))))

;;上はdefineの中身みたいなかんじで、funcには自分自身を与えなきゃいけないのでこうする

((lambda (func)
        (lambda (n)
            (if (zero? n) 1 (* n ((func func) (- n 1))))))
    (lambda (func)
        (lambda (n)
            (if (zero? n) 1 (* n ((func func) (- n 1))))))
)

;;もう一回おんなじやつを書いただけでこれを呼んでやると...

(((lambda (func)
        (lambda (n)
            (if (zero? n) 1 (* n ((func func) (- n 1))))))
    (lambda (func)
        (lambda (n)
            (if (zero? n) 1 (* n ((func func) (- n 1))))))
)5)




Pythonでもおんなじことしてみる


print \
((lambda f:
    (lambda n:
        1 if n == 0 else n * f(f)(n - 1)))
 (lambda f:
    (lambda n:
        1 if n == 0 else n * f(f)(n - 1))))(5)



ということでした。

Yコンビネータってのはこの二回自分自身を書くことを省略できて

f(f)とか(func func)とかやんなくて済むようになる感じかな...?
スポンサーサイト

comment 0 trackback 1
トラックバックURL
http://telracsmoratori.blog.fc2.com/tb.php/150-380b8360
トラックバック
Yコンビネータ難しいですね 最近ずっと考えてたんですがなかなか理解できなかったんですが、 すこーしわ
まとめ【Yコンビネータぁああ】 | まっとめBLOG速報 | 2012.12.03 15:41
コメント
管理者にだけ表示を許可する
 
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。