継続渡しスタイルの再帰関数の読み解き方、あるいは多値で済む場合
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)を参照してください。