Scheme手習い(13) 継続の続き

第8章「究極のlambda」の続きの続きの続き

数のリストから偶数だけを集めるevens-only*を作ります
タップではなく木から集めてくるところがさっきまでとは違います
これは普通の再帰だし問題ありません

次は収集子を使って、できあがりのリストと偶数の積と奇数の和を収集します
「同時に２つ以上の値を集める」にようにしたということなんでしょうけど
なんか取ってつけたような機能ですね
戒律とか読んだ記憶を頼りに書けるところまで書いてみますよと

(define evens-only*&co
  (lambda (l col)
    (cond ((null? l) (col '() 1 0))
          ((atom? (car l))
            (cond ((even? (car l))
                   (evens-only*&co
                     (cdr l)
                     (lambda (newl p s)
                       (col (cons (car l) newl) (* (car l) p) s))))
                  (else
                    (evens-only*&co
                      (cdr l)
                      (lambda (newl p s)
                        (col newl p (+ (car l) s)))))))
          (else
            (evens-only*&co

えーと
carとcdrの両方を再帰的に処理しなければならないので
(car l)と(cdr l)について呼び出す必要があることは間違いないんですけど

    (else
      (evens-only*&co (car l) ...)
      (evens-only*&co (cdr l) ...))

これではcarの結果が捨てられてしまってcdrの結果と別れ別れになってしまいます
関数型プログラミングの形になってません
どうやってくっつけてたんだったかな

いったん引き下がって、書けたところだけで動かしてみながら考えます
収集子はcollectorという関数があることにして

  (evens-only*&co '() collector)
= (collector '() 1 0)

  (evens-only*&co '(1) collector)
= ((lambda (newl p s) (collector newl p (+ 1 s)) '() 1 0)
= (collector '() 1 (+ 1 0))
= (collector '() 1 1)

  (evens-only*&co '(2) collector)
= ((lambda (newl p s) (collector (cons 2 newl) (* 2 p) s)) '() 1 0)
= (collector (cons 2 '()) (* 2 1) 0)
= (collector '(2) 2 0)

ここまでは*関数じゃなくても同じで問題ありません
ここから先はすでにちょっとあやしくなってきますが前回を思い出しながら

  (evens-only*&co '(2 4) collector)
= (evens-only*&co '(4) (lambda (newl p s) (collector (cons 2 newl) (* 2 p) s)))

ここでは(cdr l)つまり(4)を処理した結果をnewl、p、sに入れてもらえることを期待して
そこに(car l)つまり2を結合する関数を作っています
(evens-only*&co '(4) ...)が(4)を処理した値がnewl、p、sに入ってるイメージなんでした
自分の仕事は(car l)つまり2をなんとかすること
あとは「上から」言われたとおりにcolしますが、そのときnewl、p、sに自分の仕事の
結果を入れてます

= (evens-only*&co '()
    (lambda (newl p s)
      ((lambda (newl p s) (collector (cons 2 newl) (* 2 p) s))
       (cons 4 newl) (* 4 p) s)))
= ((lambda (newl p s)
     ((lambda (newl p s) (collector (cons 2 newl) (* 2 p) s))
      (cons 4 newl) (* 4 p) s))
   '() 1 0)
= ((lambda (newl p s) (collector (cons 2 newl) (* 2 p) s))
   (cons 4 '()) (* 4 1) 0)
= (collector (cons 2 (cons 4 '())) (* 2 (* 4 1)) 0)
= (collector '(2 4) 8 0)

lが()になったらリストを最後までたどったということなのでcolに初期値を与えて
継続を評価したら完了です

さて本番
木を対象にして考えてみます
これはどうなってくれるとうれしいかな

  (evens-only*&co '((2 3) 4) collector)

(car l)もリストであるところがさっきまでと違いますけれども
さっきのパターンを再利用してみます

(cdr l)の処理を次のevens-only*&coにまかせて結果をnewl、p、sに入れてもらい
自分は(car l)だけを処理して
もらったnewl、p、sに結合してやります

ただ今回は(car l)もリストなのでこっちもevens-only*&coを使って処理します

(car l)の処理が終わったら続いて(cdr l)の処理を行いますから
(car l)を処理するときのcolに(cdr l)を処理するためのevens-only*&coを指定してやれば
うまくいくんじゃないでしょうか

(define evens-only*&co
  (lambda (l col)
    (cond ((null? l) (col '() 1 0))
          ((atom? (car l))
           (cond ((even? (car l))
                  (evens-only*&co (cdr l)
                    (lambda (newl p s)
                      (col (cons (car l) newl) (* (car l) p) s))))
                 (else
                   (evens-only*&co (cdr l)
                     (lambda (newl p s)
                       (col newl p (+ (car l) s)))))))
          (else
            (evens-only*&co (car l)
              (lambda (newl p s)
                (evens-only*&co (cdr l)
                  (lambda (newl2 p2 s2)
                    (col (cons newl newl2) (* p p2) (+ s s2))))))))))

すごく大ざっぱに読めば
まず(car l)を処理して次に(cdr l)を処理してくっつけたら継続を呼ぶ、と読めますね

実行の様子を追ってみます

  (evens-only*&co '((2 3) 4) collector)
; (car l)がアトムでない場合の展開
= (evens-only*&co '(2 3)
    (lambda (newl p s)
      (evens-only*&co '(4)
        (lambda (newl2 p2 s2)
          (collector (cons newl newl2) (* p p2) (+ s s2))))))
; しばらくcdr側(内側)のevens-only*&coは放置
= (evens-only*&co '(3)
    (lambda (newl p s)
      ((lambda (newl p s)
        (evens-only*&co '(4)
          (lambda (newl2 p2 s2)
            (collector (cons newl newl2) (* p p2) (+ s s2)))))
      (cons 2 newl) (* 2 p) s)))
= (evens-only*&co '()
    (lambda (newl p s)
      ((lambda (newl p s)
        ((lambda (newl p s)
            (evens-only*&co '(4)
              (lambda (newl2 p2 s2)
                (collector (cons newl newl2) (* p p2) (+ s s2)))))
          (cons 2 newl) (* 2 p) s))
      newl p (+ 3 s))))
;car側が末端まで達しlambdaの呼び出しが始まる
= ((lambda (newl p s)
    ((lambda (newl p s)
        ((lambda (newl p s)
          (evens-only*&co '(4)
            (lambda (newl2 p2 s2)
              (collector (cons newl newl2) (* p p2) (+ s s2)))))
        (cons 2 newl) (* 2 p) s))
      newl p (+ 3 s)))
  '() 1 0)
;外側から順番に適用
= ((lambda (newl p s)
    ((lambda (newl p s)
        (evens-only*&co '(4)
          (lambda (newl2 p2 s2)
            (collector (cons newl newl2) (* p p2) (+ s s2)))))
      (cons 2 newl) (* 2 p) s))
  '() 1 3)
= ((lambda (newl p s)
    (evens-only*&co '(4)
      (lambda (newl2 p2 s2)
        (collector (cons newl newl2) (* p p2) (+ s s2)))))
  '(2) 2 3)
= (evens-only*&co '(4)
    (lambda (newl2 p2 s2)
      (collector (cons '(2) newl2) (* 2 p2) (+ 3 s2))))
;car側の処理が完了。cdr側の処理を開始
= (evens-only*&co '()
    (lambda (newl p s)
      ((lambda (newl2 p2 s2)
        (collector (cons '(2) newl2) (* 2 p2) (+ 3 s2)))
      (cons 4 newl) (* 4 p) s)))
;cdr側が末端まで達しlambdaの呼び出しを開始
= ((lambda (newl p s)
    ((lambda (newl2 p2 s2)
        (collector (cons '(2) newl2) (* 2 p2) (+ 3 s2)))
      (cons 4 newl) (* 4 p) s))
  '() 1 0)
;car側の結果とcdr側の結果を結合する
= ((lambda (newl2 p2 s2)
    (collector (cons '(2) newl2) (* 2 p2) (+ 3 s2)))
  '(4) 4 0)
= (collector '((2) 4) 8 3)

できたー
けどそろそろ限界

ソースを読んできっとこれで動きそう、というところまではわかる気がしてきましたが
ここまで来ると実行の様子を思い浮かべて確信を持つのは容易ではないですね

さてこれでこの章も終わりですがいったい「究極のlambda」ってなんだったんでしょう
高階関数のこと？
継続のこと？

原文だと「Lambda the Ultimate」となってますね
いろんなlambdaがあってその中で特にすごいlambdaがあるように読んでたんですが
これだとlambda様自体が究極であるって感じですね
「究極のlambda」というより「究極なるlambda」の方が雰囲気が出るかなあ