schemeを使っていてリストを終りの側から処理したい場面があった。それっぽい関数が標準で有りそうだと思って調べたらやはり有ったfold-right。見慣れないものがあったら試しに自分で書いてみるのがschemeの修練というもの。
(define (fold-right kons knil e) (let loop ((e e)) (if (null? e) knil (kons (car e) (loop (cdr e))))))
単純な実装。リストをひとつしかとれなかったりするけどそれはとりあえず置いて、末尾再帰に出来ないものかと変形してみた。
(define (fold-right kons knil e) (let loop ((e e) (return identity)) (if (null? e) (return knil) (loop (cdr e) (lambda(x)(return (kons (car e) x)))))))
えらい遅い。そりゃそうだよなぁ。スタックフレームを作るよりもクロージャを生成する方がコストは大きいだろ。常識的に考えて。しかも生成したクロージャを評価していかなきゃならないという二度手間。
条件次第ではあるけれど、どうせどこかに一旦蓄積する必要があるデータなら慣れない内は素直にスタックに積んでおくのが無難だと思った。
Document ID: 2d64afb340a3ef1d4a88effa55a1db6d