プログラマーと山/Queueの答え合わせ

プログラマーが山を登りたくなるのは、
山が土地の局所最適解だからだとしておいてください。

道中、出会ったお二人のお爺さんに、
カメラスポットと帰り道を教えて頂きました。
(カメラは 持ってないので撮らなかったですが)

帰り道を教えてもらったお爺さんとは
60°くらいの斜面の途中で休憩しながらお話していたので、
シュールな状況で個人的にツボってました。

f:id:bis83gb:20141103170040p:plain

低山で道なりも分かりやすかったので下山も早かったです。
今度は温泉が場所にしたいと思います。

Queueの回答

SICP 3.3.2 にQueueの実装があったので、
先日の投稿内容と答え合わせします。

空キューの表現

空キューは先頭リストがNILであるかどうかで十分です。
pop処理で末尾セルへの不正な参照が残っていても、
隠蔽されたキューのインタフェースではアクセスできないからです。

(define (qnull? q)
  (null? (car q)))

こうすれば、キューのpop処理をよりシンプルに記述できます。

(define (qpop! q)
  (assert (not (qnull? q)) "pop from null-queue")
  (set-car! q (cdar q)))

要素のあるキューからpopして空キューになった際に、
末尾セルをさすCDR部の参照が残ります。

しかし、次回pushする時に正しい末尾セルが代入されるため、
問題が起きることがないわけです。

こちらのほうが判定処理が短い分、qnull?とqpop!の実行効率が良いです。
pushのほうは特に変更は必要ありません。

空のキューを作成する際に、CAR,CDRともにNILを指すセルを生成するため、
そのイメージに引っ張られたため冗長な定義になってしまいました。

本来のCDR部の制約条件は、
「キューが空でないならCDR部はCAR部のLISTの末尾セルでなければならない」
なので、空キューのCDR部は「不定値」で十分です。*1

誤解には気をつけなければなりませんね。

*1:制約条件は、前回わざわざ定義したqueue?に自ら記載いたのですが・・・