継続渡しスタイルの再帰関数の読み解き方、あるいは多値で済む場合

Scheme手習い(The Little Schemer) 8章に、multirember&coという関数が出てくるのですが、何だか急に難しさが跳ね上がったようで、正直わけがわからなかったので、自分用に解説をメモしておきます。 動作環境はGauche 0.9.4です。

継続渡しスタイルでのgrouping関数

題材はmultirember&co関数なのですが、関数や変数の命名が余りにわかりづらいため、適宜形式と命名を変更していきます。 *1

;; grouping
;; latの各要素にpred?関数を適用し、
;; 成功した要素のリストと失敗した要素のリストをhandler関数に渡す。
(define (grouping pred? handler lat)
  (cond
   ((null? lat)
    (print "!empty!"); debug出力
    (handler '() '())); 再帰終了
   ((pred? (car lat))
    ;; チェック成功時
    (grouping
     pred?
     (lambda (successes failures)
       (print " !success!: " (car lat) successes failures); debug出力
       (handler (cons (car lat) successes) failures))
     (cdr lat)))
   (else
    ;; チェック失敗時
    (grouping
     pred?
     (lambda (successes failures)
       (print " !failure!: " (car lat) successes failures); debug出力
       (handler successes (cons (car lat) failures)))
     (cdr lat)))))
;; 動かしてみる
;; リスト`(1 2 3 2 4 2 5)の要素うち、(= x 2)となるようなxなら成功とする。
;; successesに'(2 2 2)、failuresに`(1 3 4 5)が入っていることを確認する。
(grouping
 (lambda (x) (= x 2))
 (lambda (successes failures)
   (print "!finish!: " successes failures); debug出力
   (and
    (equal? successes '(2 2 2))
    (equal? failures '(1 3 4 5))))
 '(1 2 3 2 4 2 5))

後半のgrouping関数呼び出しの実行結果は以下です。

!empty!
 !failure!: 5()()
 !success!: 2()(5)
 !failure!: 4(2)(5)
 !success!: 2(2)(4 5)
 !failure!: 3(2 2)(4 5)
 !success!: 2(2 2)(3 4 5)
 !failure!: 1(2 2 2)(3 4 5)
!finish!: (2 2 2)(1 3 4 5)
#t

• ここで定義したgrouping関数では、再帰のたびに新たなlambdaをhandlerの外側に被せています。
• 再帰の終了時に、これまで構築した入れ子lambdaの実際の呼び出しが起きていることがわかります。
• 入れ子になったlambdaの一番内側が、外部から渡されたhandler関数となっています。
• 関数全体の評価結果は、再帰終了時に呼び出された入れ子lambdaの結果であり、つまり最終的には一番内側の、初めに渡したhandler関数の結果となっています。
  • 現状ではsuccessesとfailuresの中身を確認した結果の#tが評価結果となっています。

多値を利用するgrouping関数の実装

ここまで書いて、二つの値を使用するだけのために、継続渡しスタイルにしてhandler関数をわざわざ外部から渡すのも可笑しいように思われたので、多値*2を用いて実装してみました。

;; grouping2
;; grouping関数の多値による実装
;; latの各要素にpred?関数を適用し、
;; 成功した要素のリストと失敗した要素のリストを多値で返す。
(define (grouping2 pred? lat)
  (cond
   ((null? lat)
    (print "!empty!"); debug出力
    (values '() '())); 再帰終了
   ((pred? (car lat))
    ;; チェック成功時
    (receive (successes failures) (grouping2 pred? (cdr lat))
             (print " !success!: " (car lat) successes failures); debug出力
             (values (cons (car lat) successes) failures)))
   (else
    ;; チェック失敗時
    (receive (successes failures) (grouping2 pred? (cdr lat))
             (print " !failure!: " (car lat) successes failures); debug出力
             (values successes (cons (car lat) failures))))))
;; 動かしてみる
(call-with-values
    (lambda ()
      (grouping2
       (lambda (x) (= x 2))
       '(1 2 3 2 4 2 5)))
  (lambda (successes failures)
    (print "!finish!: " successes failures); debug出力
    (and
     (equal? successes '(2 2 2))
     (equal? failures '(1 3 4 5)))))

実行結果は上記とまったく同一になるため省略します。

関数が2つのリスト(successes, failures)を同時に返していること、そのためにvalues(多値の生成)とreceive(多値が作られる式の評価と、結果の束縛)を使っていることに注意すれば、こちらは只の再帰関数となんら変わりありません。

といったところで、今回は以上です。

*1:オリジナルのmultirember&co関数とその解説はこのあたり(GPソフト Wiki - The Little Schemerを読み解く ～ multirember&co)を参照してください。

*2:多値についてはこちら(Scheme:多値)が詳しいです。