SICP読書会(Exercise 3.22 – Exercise 3.23)

これまでのあらすじ

弊社では新入社員の技術的な基礎体力向上を目的としてSICPの読書会を一年半程前から毎週行っています。

毎回のまとめは参加者用のMLに流していたのですが、
よくよく考えると後から一覧したり検索したりし辛いので、
今後はこちらにポストしようと思います。

かなりスローペースで進めているため、
一年半経ってようやく3章に突入したところです。

前回は3.3.2 Representing Queuesを読んでExercise 3.21を解き、Exercise 3.22とExercise 3.23は宿題ということにしました。
という訳で宿題の答え合わせをしましょう。

Instead of representing a queue as a pair of pointers, we can
build a queue as a procedure with local state. The local state will consist
of pointers to the beginning and the end of an ordinary list. Thus, the
make-queue procedure will have the form

(define (make-queue)
  (let ((front-ptr ...)
        (rear-ptr ...))
    <definitions of internal procedures>
    (define (dispatch m) ...)
    dispatch))

Complete the definition of make-queue and provide implementations of the
queue operations using this representation.

これはExercise 3.20の前座の「Mutation is just assignment」に出てきた手続き版 cons と同じ要領で作れば良いだけの話です。
テキスト中の実装と比較した場合、 front-ptr と rear-ptr の読み書き方法が異なるくらいで、残りの実装はほぼ同じです。
という訳でテキスト中の実装を切り貼りしてちょちょいと直せば完成ですね。

Exercise 3.23

A deque (“double-ended queue”) is a sequence in which items
can be inserted and deleted at either the front or the rear. Operations on
deques are the constructor make-deque, the predicate empty-deque?,
selectors front-deque and rear-deque, and mutators front-insert-deque!,
rear-insert-deque!, front-delete-deque!, and rear-delete-deque!. Show
how to represent deques using pairs, and give implementations of the
operations. [23] All operations should be accomplished in Θ(1) steps.

dequeはqueueと違って先頭からも末尾からも要素の追加/削除が可能です。
一つづつ検討しましょう:

• front-insert-deque! … queueには無い操作ですが、リストの先頭に新しく追加するのは散々やってきたパターンなので楽勝ですね。
• front-delete-deque! … queueと一緒ですから楽勝ですね。
• rear-insert-deque! … queueと一緒ですから楽勝ですね。
• rear-delete-deque! … queueには無い操作で、 rear-ptr はリストの最後から二番目の要素を指すよう変更する必要があります。

問題は rear-delete-deque! です。
「最後から二番目の要素」はつまり rear-ptr の指す要素の直前の要素なのですが、
今まで散々扱ってきたリストでは直後の要素はO(1)で辿れても直前の要素はO(1)で辿れません。
という事はqueueと同じ要領でやろうとしても rear-delete-deque! をO(1)で実装できないことになります。

という訳で今までのリストを使うのは止めて、
各要素が直前の要素へのポインターも持つ双方向リストをベースにしてdequeを実装しましょう。
双方向リストの各要素は値、直後の要素へのポインター、直前の要素へのポインターの3個のデータで構成されるので、
もはやconsセル1個では賄えません。つまり

1. 双方向リストの要素のconstructor/selectors/mutatorsを作って、
2. それらを利用してdequeを実装する

形になります。
queueに比べると若干複雑ですが、
このデータ構造の分離ができているなら実装するのはそう難しくはないですね。

次回予告

3.3.3 Representing Tables
を読んで問題をバンバン解いていきます。
dequeよりさらに複雑なデータ構造を相手にすることになるので、しっかり復習しておきましょう。