Scheme手習い(19) Yコンビネータ(4)

Yコンビネータでいろいろな関数を動かしてみます

(define Y
  (lambda (le)
    ((lambda (f) (f f))
     (lambda (f)
       (le (lambda (x) ((f f) x)))))))

再帰しない関数を渡しても動くかな

((Y (lambda (add2) (lambda (n) (add1 (add1 n))))) 1)
⇛ 3

動いた！

じゃあ、2引数の関数は？

((Y
  (lambda (member?) 
    (lambda (a lat)
      (cond ((null? lat) #f)
            ((eq? (car lat) a) #t)
            (else (member? a (cdr lat)))))))
 'c '(a b c))
⇛ エラー

(f f)は引数をひとつしか取らないもんなあ
頭使わずに解決してみます

(define Y2
  (lambda (le)
    ((lambda (f) (f f))
     (lambda (f)
       (le (lambda (x y) ((f f) x y)))))))

((Y2
  (lambda (member?) 
    (lambda (a lat)
      (cond ((null? lat) #f)
            ((eq? (car lat) a) #t)
            (else (member? a (cdr lat)))))))
 'c '(a b c))
⇛ #t     

動きました
でも引数の数ごとにY作んなきゃいけないとか頭使わなさすぎです

じゃあ、カリー化したら？

(((Y
   (lambda (member?) 
     (lambda (a)
       (lambda (lat)
         (cond ((null? lat) #f)
               ((eq? (car lat) a) #t)
               (else ((member? a) (cdr lat))))))))
  'c) '(a b c))
⇛ #t

動きました
リストの中にcを含むかどうかを判定する関数を作り、その関数を(a b c)に適用しています
細かく考えだすと頭がパンク気味です

カリー化って、引数の順番どうなんですかね
並んだ引数のなかで特別扱いがひとつだけ

(((Y
   (lambda (member?) 
     (lambda (lat)
       (lambda (a)
         (cond ((null? lat) #f)
               ((eq? (car lat) a) #t)
               (else ((member? (cdr lat)) a)))))))
  '(a b c)) 'c)
⇛ #t

当然ながらこれでも動きます
引数の順番は考えて決めましょう

3引数は？
2回カリー化するのかな？
いや1回だけでよさそうです

(((Y
   (lambda (insertR)
     (lambda (lat)
       (lambda (old new)
         (cond ((null? lat) (quote ()))
               ((eq? (car lat) old) (cons old (cons new (cdr lat))))
               (else (cons (car lat) ((insertR (cdr lat)) old new))))))))
  '(a b c)) 'b 'd)
⇛ (a b d c)

oldとnew・latの組に分けるのはブサイクな気がしたのでlatを外に出しました

*関数も動きました

(((Y
   (lambda (rember*)
     (lambda (a)
       (lambda (l)
         (cond ((null? l) (quote ()))
               ((atom? (car l))
                (cond ((eq? (car l) a) ((rember* a) (cdr l)))
                      (else (cons (car l) ((rember* a) (cdr l))))))
               (else (cons ((rember* a) (car l)) ((rember* a) (cdr l)))))))))
  'b) '((a b c) a b c))
⇛ ((a c) a c)

入れ子になった再帰はどうでしょうか？

(((Y
   (lambda (o*)
     (lambda (n)
       (lambda (m)
         (cond ((zero? m) 0)
               (else (((Y
                        (lambda (o+)
                          (lambda (m)
                            (lambda (n)
                              (cond ((zero? n) m)
                                    (else ((o+ (add1 m)) (sub1 n)))))))) 
                       n) ((o* n) (sub1 m)))))))))
  2) 3)
⇛ 6

動きました

o+に名前をつけてやれば見やすいかな？

((((lambda (o+)
     (Y
      (lambda (o*)
        (lambda (n)
          (lambda (m)
            (cond ((zero? m) 0)
                  (else ((o+ n) ((o* n) (sub1 m))))))))))
   (Y
    (lambda (o+)
      (lambda (n)
        (lambda (m)
          (cond ((zero? m) n)
                (else (add1 ((o+ n) (sub1 m))))))))))
  2) 3)

o*にも名前をつけてやってもいいですね

((lambda (o+)
   ((lambda (o*)
      ((o* 2) 3))
    (Y
     (lambda (o*)
       (lambda (n)
         (lambda (m)
           (cond ((zero? m) 0)
                 (else ((o+ n) ((o* n) (sub1 m)))))))))))
 (Y
  (lambda (o+)
    (lambda (n)
      (lambda (m)
        (cond ((zero? m) n)
              (else (add1 ((o+ n) (sub1 m))))))))))

じー

じー

名前をつけて呼び出す・・・だと・・・？

(define ...)は何ですか。

もしかして、これがdefineってこと？

(define ... )は正しく動作するといえますか。

defineは実はlambdaだから正しく動作する？

確かに。いまや再帰とは何かを知っています。

再帰だけちょっと心配だったけど、Yがあれば書けるし？

そういうことなんでしょうか？

defineにしちゃちょっとスコープ的にうるさい感じがしますが
というのは、こういう書き方ではうまくいかなかったので

((lambda (o* o+)
   ((o* 2) 3))
 (Y
  (lambda (o*)
    (lambda (n)
      (lambda (m)
        (cond ((zero? m) 0)
              (else ((o+ n) ((o* n) (sub1 m)))))))))
 (Y
  (lambda (o+)
    (lambda (n)
      (lambda (m)
        (cond ((zero? m) n)
              (else (add1 ((o+ n) (sub1 m))))))))))

o*からo+が見えてないんです
見た目はきれいなだけに残念
入れ子にして書けばいいんですが
ちょっと書き方変えるぐらいでうまくいかないかなあ

入れ子にして書かなきゃいけないとすると相互に呼び合う関数は大丈夫かと気になります
こういうのとか

(define ev?
  (lambda (n)
    (cond ((zero? n) #t)
          (else (od? (sub1 n))))))

(define od?
  (lambda (n)
    (cond ((zero? n) #f)
          (else (ev? (sub1 n))))))

どうやって書きましょう
od?を埋め込んじゃいましょうか

((Y
  (lambda (ev?)
    (lambda (n)
      (cond ((zero? n) #t)
            (else ((lambda (n)
                     (cond ((zero? n) #f)
                           (else (ev? (sub1 n)))))
                   (sub1 n)))))))
 3)

これはこれで動きますが、od?を作ろうと思ったらほとんど同じコードをもう一度書かないといけません
かなり癪に障ります

こんなふうに書いて動かないかなーと思いましたが無理でした
やっぱりev?からはod?が、od?からはev?が見えません

((lambda (ev? od?)
   (od? 3))
 (lambda (n)
   (cond ((zero? n) #t)
         (else (od? (sub1 n)))))
 (lambda (n)
   (cond ((zero? n) #f)
         (else (ev? (sub1 n))))))

さて。

ev?からod?が呼べる必要があり、od?からev?が呼べる必要がある、というのは
lengthからlengthを呼び出す必要がある、というのと似ています
Yコンビネータを作るときのやり方で1から作ってみます

まずは呼びたい関数を引数に取るようにします
ev?に当たる関数からはod?を呼び出しますのでev?ではなくod?を引数に取るというのが
今までと違います

;ev?に似た関数
(lambda (od?)
  (lambda (n)
    (cond ((zero? n) #t)
          (else (od? (sub1 n))))))
;od?に似た関数
(lambda (ev?)
  (lambda (n)
    (cond ((zero? n) #f)
          (else (ev? (sub1 n))))))

次に、今作った関数に名前をつけます。

((lambda (e? o?)
   'ここはあとで考える)
 ;ev?に似た関数
 (lambda (od?)
   (lambda (n)
     (cond ((zero? n) #t)
           (else (od? (sub1 n))))))
 ;od?に似た関数
 (lambda (ev?)
   (lambda (n)
     (cond ((zero? n) #f)
           (else (ev? (sub1 n)))))))

ev?に似た関数、od?に似た関数から、mk-ev?、mk-ed?を作ります
mk-ev?はmk-ev?もmk-od?も使いますので、2引数を取る関数になります
ちょっとめんどくさい

((lambda (e? o?)
   ((lambda (mk-ev? mk-od?)
      'ここはあとで考える)
    ;mk-ev?
    (lambda (mk-od? mk-ev?)
      (e? (mk-od? mk-ev? mk-od?)))
    ;mk-od?
    (lambda (mk-ev? mk-od?)
      (o? (mk-ev? mk-od? mk-ev?)))))
 ;ev?に似た関数
 (lambda (od?)
   (lambda (n)
     (cond ((zero? n) #t)
           (else (od? (sub1 n))))))
 ;od?に似た関数
 (lambda (ev?)
   (lambda (n)
     (cond ((zero? n) #f)
           (else (ev? (sub1 n)))))))

このままだとやっぱり止まらないのでlambdaで囲みます

((lambda (e? o?)
   ((lambda (mk-ev? mk-od?)
      'ここはあとで考える)
    (lambda (mk-od? mk-ev?)
      (e? (lambda (n) ((mk-od? mk-ev? mk-od?) n))))
    (lambda (mk-ev? mk-od?)
      (o? (lambda (n) ((mk-ev? mk-od? mk-ev?) n))))))
 (lambda (od?)
   (lambda (n)
     (cond ((zero? n) #t)
           (else (od? (sub1 n))))))
 (lambda (ev?)
   (lambda (n)
     (cond ((zero? n) #f)
           (else (ev? (sub1 n)))))))

関数を返してできあがり・・・なんですが関数を2つ返すことができません
(mk-ev? mk-od? mk-ev?)を返せばev?に
(mk-od? mk-ev? mk-od?)を返せばod?になります

((lambda (e? o?)
   ((lambda (mk-ev? mk-od?)
      (mk-od? mk-ev? mk-od?))
    (lambda (mk-od? mk-ev?)
      (e? (lambda (n) ((mk-od? mk-ev? mk-od?) n))))
    (lambda (mk-ev? mk-od?)
      (o? (lambda (n) ((mk-ev? mk-od? mk-ev?) n))))))
 (lambda (od?)
   (lambda (n)
     (cond ((zero? n) #t)
           (else (od? (sub1 n))))))
 (lambda (ev?)
   (lambda (n)
     (cond ((zero? n) #f)
           (else (ev? (sub1 n)))))))

ev?、od?に名前を付けて両方使えるようにするにはどうするといいでしょう？
関数をふたつ返すことはできませんから中で使う？

((lambda (e? o?)
   ((lambda (mk-ev? mk-od?)
      ((lambda (ev? od?)
         (display (ev? 2)) (newline)
         (display (ev? 3)) (newline)
         (display (od? 2)) (newline)
         (display (od? 3)) (newline))
       (mk-ev? mk-od? mk-ev?)
       (mk-od? mk-ev? mk-od?)))
    (lambda (mk-od? mk-ev?)
      (e? (lambda (n) ((mk-od? mk-ev? mk-od?) n))))
    (lambda (mk-ev? mk-od?)
      (o? (lambda (n) ((mk-ev? mk-od? mk-ev?) n))))))
 (lambda (od?)
   (lambda (n)
     (cond ((zero? n) #t)
           (else (od? (sub1 n))))))
 (lambda (ev?)
   (lambda (n)
     (cond ((zero? n) #f)
           (else (ev? (sub1 n)))))))
⇛ #t
  #f
  #f
  #t

動きました
動いたんですけどここまでしないといけないかとちょっと疑問
ちょっと変えるだけとか、せめてYを2回使うくらいでできないもんですかね