きっかけはGaucheで「iotaって(use srfi-1)しないと使えないんだ」と気づいたこと。手元のSCMでは使えなさそうなので、Gauche Users’ Reference: Topに載っているiotaの説明を参考にそれっぽいものを実装してみた。
Schemeの初心者*1としては無謀な試みだったかもしれないけど、それっぽいものができた。
制限事項はこんな感じ。
最初に思いついたのは末尾再帰っぽいイメージで、再帰の一番深い呼び出しの時にリストが完成する感じだったのだが、よく分からない所で躓いたので、先に普通の再帰で書いてみた。
; 再帰版 (define (iota count start step) (if (<= count 0) '() (cons start (iota (- count 1) (+ start step) step))))
SCMでtrace付きで実行するとこんな感じ。
> (trace iota) #<unspecified> > (iota 3 0 1) call iota 3 0 1 call iota 2 1 1 call iota 1 2 1 call iota 0 3 1 retn iota () retn iota (2) retn iota (1 2) retn iota (0 1 2) (0 1 2)
ようやく納得できたのだけど、よく言われる「再帰は、完成の一歩手前に実行する処理を書くだけ」というのは正しいと思う。
; 末尾再帰（反復）版 (define (iota count start step) (define (iota-iter count num lst) (if (<= count 0) (reverse lst) (iota-iter (- count 1) (+ num step) (cons num lst)))) (iota-iter count start '()))
ついでにtraceに対応した末尾再帰版も晒しておく。
; 末尾再帰（反復）版の trace対応バージョン ; (trace iota-iter) してからiotaを呼べばOK (define (iota-iter count start step lst) (if (<= count 0) (reverse lst) (iota-iter (- count 1) (+ start step) step (cons start lst)))) (define (iota count start step) (iota-iter count start step '()))
traceするとこんな感じ。
> (trace iota)
#<unspecified>
> (trace iota-iter)
#<unspecified>
> (iota 3 0 1)
call iota 3 0 1
call iota-iter 3 0 1 ()
call iota-iter 2 1 1 (0)
call iota-iter 1 2 1 (1 0)
call iota-iter 0 3 1 (2 1 0)
retn iota-iter (0 1 2)
retn iota-iter (0 1 2)
retn iota-iter (0 1 2)
retn iota-iter (0 1 2)
retn iota (0 1 2)
(0 1 2)再帰や末尾再帰については、階乗やハノイの塔ではうまくイメージできない部分があったのだけど、今回はハッキリとしたイメージが持てた。多分リストという具体的なデータ構造を操作する処理だったからだと思う。
ということで、再帰の勉強にiotaっぽいものを実装するのもありかもしれない、なんて思った午後のひとときだった。
*1:Schemeプログラマのレベル10のレベル0と1を4:6の比率で混ぜ合わせた感じだと思う
