2010/01/25

さっきの5の階乗

lambda, cond, zero?, +, -, 0, 1 だけで、というルールで階乗してね、ということで。

; 5の階乗
(((lambda (f)
    (f f))
  (lambda (f)
    (lambda (n)
      (cond ((zero? n) 1)
            (else (((lambda (f)
                      (f f))
                    (lambda (f)
                      (lambda (n m)
                        (cond ((zero? m) 0)
                              (else ((
(lambda (f)
                                        (f f))
                                      (lambda (f)
                                        (lambda (n m)
                                          (cond ((zero? m) n)
                                                (else ((lambda (n)(+ n 1)) ((f f) n ((lambda (n)(- n 1)) m))))))))

                                     n ((f f) n ((lambda (n)(- n 1)) m))))))))
                   n ((f f) ((lambda (n)(- n 1)) n)))))))) 5)

 

一応どうなっているかというと・・・。

こんなの書けてもお得なことは何もありません(と思います)。暇つぶしとか頭の体操(罰ゲーム?)としてどうぞ・・・。

 

インクリメントとデクリメントで加算を行なう無名関数を作る(無名関数での再帰ということで再帰はYコンビネータ的な)

;加算

((lambda (f)
    (f f))
  (lambda (f)
    (lambda (n m)
      (cond ((zero? m) n)
            (else ((lambda (n)(+ n 1)) ((f f) n ((lambda (n)(- n 1)) m))))))))

 

;実行してみる

(((lambda (f)
    (f f))
  (lambda (f)
    (lambda (n m)
      (cond ((zero? m) n)
            (else ((lambda (n)(+ n 1)) ((f f) n ((lambda (n)(- n 1)) m))))))))
3 4)

; -> 7

 

↑の加算で乗算を作る。再帰はY(ry

;乗算

((lambda (f)
    (f f))
  (lambda (f)
    (lambda (n m)
      (cond ((zero? m) 0)
            (else (
((lambda (f)
                      (f f))
                    (lambda (f)
                      (lambda (n m)
                        (cond ((zero? m) n)
                              (else ((lambda (n)(+ n 1)) ((f f) n ((lambda (n)(- n 1)) m))))))))
                   n ((f f) n ((lambda (n)(- n 1)) m))))))))

;実行してみる

(((lambda (f)
    (f f))
  (lambda (f)
    (lambda (n m)
      (cond ((zero? m) 0)
            (else (
((lambda (f)
                      (f f))
                    (lambda (f)
                      (lambda (n m)
                        (cond ((zero? m) n)
                              (else ((lambda (n)(+ n 1)) ((f f) n ((lambda (n)(- n 1)) m))))))))
                   n ((f f) n ((lambda (n)(- n 1)) m)))))))) 4 5)

; -> 20

 

で最終的に階乗の手続きを作って5を渡してみる・・・

(((lambda (f)
    (f f))
  (lambda (f)
    (lambda (n)
      (cond ((zero? n) 1)
            (else (((lambda (f)
                      (f f))
                    (lambda (f)
                      (lambda (n m)
                        (cond ((zero? m) 0)
                              (else ((
(lambda (f)
                                        (f f))
                                      (lambda (f)
                                        (lambda (n m)
                                          (cond ((zero? m) n)
                                                (else ((lambda (n)(+ n 1)) ((f f) n ((lambda (n)(- n 1)) m))))))))

                                     n ((f f) n ((lambda (n)(- n 1)) m))))))))
                   n ((f f) ((lambda (n)(- n 1)) n)))))))) 5)

; -> 120

 

参考

The Little Schemer, 4th Edition 計算論 計算可能性とラムダ計算 (コンピュータサイエンス大学講座)

 

 

0 件のコメント:

コメントを投稿