TSS scramble は末尾再帰可能

valvallowさんのブログ見てたんですけど、The Seasoned Schemerのscrambleって全然意味不明ですな～～。困ったもんだ。
valvallowさんが抜粋したscrambleのコードですが、ちょっと見てみますか。

(define sub1
  (lambda (n)
    (- n 1)))

(define pick
  (lambda (n lat)
    (list-ref lat (sub1 n))))

(define scramble
  (lambda (tup)
    (letrec ((iter (lambda (t rev-pre)
                     (if (null? t)
                         '()
                         (let* ((n (car t))
                                (rev (cons n rev-pre)))
                           (cons (pick n rev)
                                 (iter (cdr t) rev)))))))
      (iter tup '()))))

ふ～む。何やってんだかサッパリです(苦笑)。
基本的にletrecがいけねえんだな(苦笑)。見づらい。
と言うわけでnamed-letに書き換えてみます。そして個人的にはあまりlet*が好きじゃないんで(何故、って訊かないで・笑)、そこも直して、pickも敢えて解体して書き直してみます。

(define (scramble tup)
  (let iter ((t tup) (rev-pre '()))
    (if (null? t)
 '()
 (let ((n (car t)))
   (let ((rev (cons n rev-pre)))
     (cons (list-ref rev (- n 1))
    (iter (cdr t) rev)))))))

ふ～～～む。まだ何やってるか分かり辛いですよね。しかも、このスタイルは末尾再帰じゃない。何か末尾再帰出来そうな気がするんですよね～～。
コードの意味が分からん、かつ末尾再帰になりそう、と思った時どうすっか。一番簡単なのは継続渡し方式に取りあえず書き直してみる事です。ひょっとしたら、これで何か見えてくるかもしれません。やってみます。

(define (scramble tup)
  (let iter ((t tup) (rev-pre '()) (k values))
    (if (null? t)
 (k '())
 (let ((n (car t)))
   (let ((rev (cons n rev-pre)))
     (iter (cdr t) rev
    (lambda (u)
      (k (cons (list-ref rev (- n 1)) u)))))))))

んで、詳しい論理の流れはこのページを参考にして欲しいんですけど、上のコードは次のように書き換えられて、

(define (scramble tup)
  (let iter ((t tup) (rev-pre '()) (acc '()) (k values))
    (if (null? t)
 (k (reverse acc))
 (let ((n (car t)))
   (let ((rev (cons n rev-pre)))
     (iter (cdr t) rev (cons (list-ref rev (- n 1)) acc)
    (lambda (u) (k u))))))))

ついでに次のように書き換えられます。

(define (scramble tup)
  (let iter ((t tup) (rev-pre '()) (acc '()) (k values))
    (if (null? t)
 (k (reverse acc))
 (let ((n (car t)))
   (let ((rev (cons n rev-pre)))
     (iter (cdr t) rev (cons (list-ref rev (- n 1)) acc) k))))))

ここまで来ると、もはやローカル手続きのkが要らなくなります。事実上、全く仕事をしてないから、です。
従って、題意のコードは、

(define (scramble tup)
  (let iter ((t tup) (rev-pre '()) (acc '()))
    (if (null? t)
 (reverse acc)
 (let ((n (car t)))
   (let ((rev (cons n rev-pre)))
     (iter (cdr t) rev (cons (list-ref rev (- n 1)) acc)))))))

となりますね。末尾再帰になりました。
末尾再帰の方が若干何やってるか分かりやすいかもしれません。

1. n番目の指定はリストtの先頭の数字によって決定される。


2. リストrevは(cons n rev)で生成される。また、このリストは常にリストtに対しては部分的に逆順となっている。


3. リストaccはリストrevのn番目の要素をconsしていって生成される。


4. tは(cdr t)となり(null? t) => #tとなるまで1番から作業を繰り返す。


5. 返り値はaccを逆順にしたものである。

まだ、ちょっと分かり辛いかもしれませんね。例えば、

1. tは(1 1 1 3 4 2 1 1 9 2)、revは空リスト、accも空リストとする。


2. nは1となり、revは(1)となる。


3. revのn = 1番目の要素は1なので、accは(1)となる。


4. tは(1 1 3 4 2 1 1 9 2)となり、以下繰り返し。

つまり、キーポイントとしては「常にtに対して部分的には逆順のリストであるrevのn番目の要素を問題にしている」と言う事なんです。
まだ分かり辛いかもしれないんで、valvallowさんの真似をして出力部分を組み合わせてみます。

(define (scramble tup)
  (let iter ((t tup) (rev-pre '()) (acc '()))
    (if (null? t)
 (reverse acc)
 (let ((n (car t)))
   (let ((rev (cons n rev-pre)))
     (for-each (lambda (x) ; ここは出力
   (display x))
        (list "t = " t ", n = " n ", rev = " rev ", acc = " acc))
     (newline)   ; 改行
     (iter (cdr t) rev (cons (list-ref rev (- n 1)) acc)))))))

出力結果は以下の通りです。

> (scramble '(1 1 1 3 4 2 1 1 9 2))
t = (1 1 1 3 4 2 1 1 9 2), n = 1, rev = (1), acc = ()
t = (1 1 3 4 2 1 1 9 2), n = 1, rev = (1 1), acc = (1)
t = (1 3 4 2 1 1 9 2), n = 1, rev = (1 1 1), acc = (1 1)
t = (3 4 2 1 1 9 2), n = 3, rev = (3 1 1 1), acc = (1 1 1)
t = (4 2 1 1 9 2), n = 4, rev = (4 3 1 1 1), acc = (1 1 1 1)
t = (2 1 1 9 2), n = 2, rev = (2 4 3 1 1 1), acc = (1 1 1 1 1)
t = (1 1 9 2), n = 1, rev = (1 2 4 3 1 1 1), acc = (4 1 1 1 1 1)
t = (1 9 2), n = 1, rev = (1 1 2 4 3 1 1 1), acc = (1 4 1 1 1 1 1)
t = (9 2), n = 9, rev = (9 1 1 2 4 3 1 1 1), acc = (1 1 4 1 1 1 1 1)
t = (2), n = 2, rev = (2 9 1 1 2 4 3 1 1 1), acc = (1 1 1 4 1 1 1 1 1)
(1 1 1 1 1 4 1 1 1 9)
> (scramble '(1 2 3 4 5 6 7 8 9))
t = (1 2 3 4 5 6 7 8 9), n = 1, rev = (1), acc = ()
t = (2 3 4 5 6 7 8 9), n = 2, rev = (2 1), acc = (1)
t = (3 4 5 6 7 8 9), n = 3, rev = (3 2 1), acc = (1 1)
t = (4 5 6 7 8 9), n = 4, rev = (4 3 2 1), acc = (1 1 1)
t = (5 6 7 8 9), n = 5, rev = (5 4 3 2 1), acc = (1 1 1 1)
t = (6 7 8 9), n = 6, rev = (6 5 4 3 2 1), acc = (1 1 1 1 1)
t = (7 8 9), n = 7, rev = (7 6 5 4 3 2 1), acc = (1 1 1 1 1 1)
t = (8 9), n = 8, rev = (8 7 6 5 4 3 2 1), acc = (1 1 1 1 1 1 1)
t = (9), n = 9, rev = (9 8 7 6 5 4 3 2 1), acc = (1 1 1 1 1 1 1 1)
(1 1 1 1 1 1 1 1 1)
> (scramble '(1 2 3 1 2 3 4 1 8 2 10))
t = (1 2 3 1 2 3 4 1 8 2 10), n = 1, rev = (1), acc = ()
t = (2 3 1 2 3 4 1 8 2 10), n = 2, rev = (2 1), acc = (1)
t = (3 1 2 3 4 1 8 2 10), n = 3, rev = (3 2 1), acc = (1 1)
t = (1 2 3 4 1 8 2 10), n = 1, rev = (1 3 2 1), acc = (1 1 1)
t = (2 3 4 1 8 2 10), n = 2, rev = (2 1 3 2 1), acc = (1 1 1 1)
t = (3 4 1 8 2 10), n = 3, rev = (3 2 1 3 2 1), acc = (1 1 1 1 1)
t = (4 1 8 2 10), n = 4, rev = (4 3 2 1 3 2 1), acc = (1 1 1 1 1 1)
t = (1 8 2 10), n = 1, rev = (1 4 3 2 1 3 2 1), acc = (1 1 1 1 1 1 1)
t = (8 2 10), n = 8, rev = (8 1 4 3 2 1 3 2 1), acc = (1 1 1 1 1 1 1 1)
t = (2 10), n = 2, rev = (2 8 1 4 3 2 1 3 2 1), acc = (2 1 1 1 1 1 1 1 1)
t = (10), n = 10, rev = (10 2 8 1 4 3 2 1 3 2 1), acc = (8 2 1 1 1 1 1 1 1 1)
(1 1 1 1 1 1 1 1 2 8 2)
>