末尾に追加する

Scheme ではリストを作るときにリストの頭に要素を追加していき、最後に reverse で逆転するというイディオムが定着している。 諸々を考慮するとおおよその場合は最良の戦略だと思う。 しかし、リストの末尾に要素を追加できないわけではない。

例えばリストの内容を指定回数繰返したリストを返すような手続きはこう書くことも出来る。

(define (cycle lst n)
  (let* ((r (cons #t '()))
         (lp r))
    (do ((i 0 (+ i 1)))
        ((= i n) (cdr r))
      (for-each
       (lambda(x) (let ((n (cons x '()))) (set-cdr! lp n) (set! lp n)))
       lst))))

(cycle '(1 2 3) 3) ;; => (1 2 3 1 2 3 1 2 3)

要するにリストの最後のペアへの参照を常に持っておけばよいということだ。

この例ではあえて末尾に追加していく利点はあまりない (少なくとも速度的には劣る) が、追加する途中でリストを参照しなければならないような場合にはこういう方式が役に立つこともあるだろう。 私が思い付く例で言えば、遅延評価を用いずにエラトステネスの篩を書くような場合などがある。 そういったときはキューのような形に抽象化しておくと更にやり易いかもしれない。

Document ID: 9d4475d396b6d84a651b59eab03a3222