「レコード (record)」は、ユーザーが既存のデータ型を組み合わせて、新しいデータ型を定義する機能です。たとえば、Ｃ言語ではデータ型の組み合わせを「構造体 (structure)」で行い、型名を typedef で定義します。Common Lisp にも構造体がありますが、データ型の定義だけではなく、データを生成する関数 (コンストラクタ) やアクセス関数を自動的に生成します。オブジェクト指向言語であれば「クラス (class)」を使うと簡単です。
Clojure のレコードは immutable なデータ構造で、基本的にはマップにデータ型を付けたイメージになります。Common Lisp と同様に、コンストラクタやアクセス関数が自動的に生成されます。述語 instance? を使ってデータ型をチェックすることもできます。
さらに、defprotocol を使って「プロトコル」を定義すると、レコードの中でプロトコル (仕様) を満たす関数を定義することができます。これらの機能を使うと、オブジェクト指向言語の「クラス (class)」みたいな使い方も可能です。今回はレコードについて簡単に説明します。
レコードは defrecord を使って定義します。
(defrecord name [field1 filed2 ...])
「フィールド (field)」とは、レコードで定義した変数のことです。他の言語、たとえばＣ言語では「メンバ変数」といいます。レコード名とフィールド名はシンボルで指定します。フィールド名で指定したシンボルはキーワードに変換され、マップのキーとして扱われます。
defrecord はレコードの定義のほかに、次の関数を生成します。
defrecord はデータ型を定義して必要な関数を生成するだけで、実際のデータを作り出すわけではないことに注意してください。
簡単な例を示しましょう。
user=> (defrecord Foo [a b])
user.Foo
user=> (def x (map->Foo{:a 1, :b 2}))
#'user/x
user=> x
#user.Foo{:a 1, :b 2}
user=> (->Foo 10 20)
#user.Foo{:a 10, :b 20}
user=> (Foo. 100 200)
#user.Foo{:a 100, :b 200}
user=> #user.Foo[-1 -2]
#user.Foo{:a -1, :b -2}
user=> #user.Foo{:a -10, :b -20}
#user.Foo{:a -10, :b -20}
user=> x
#user.Foo{:a 1, :b 2}
user=> (:a x)
1
user=> (:b x)
2
user=> (instance? Foo x)
true
user=> (instance? Foo 1)
false
ところで、わざわざレコードを使わなくてもリストで十分ではないか、と思われる方もいるでしょう。実際、リストを使って新しいデータ型を表すことも可能です。たとえば、リストの第 1 要素をデータ型名 Foo とし、第 2 要素をフィールド a、第 3 要素をフィールド b としましょう。コンストラクタやアクセス関数だって、わざわざ定義することもありません。
user=> (def z (list 'Foo 10 20)) #'user/z user=> z (Foo 10 20) user=> (second z) 10 user=> (nth z 2) 20
簡単にプログラムできるように思えますが、この方法には大きな弱点があるのです。ひとつは、データにアクセスするときに、要素の位置とデータの対応をプログラマが把握していないといけません。フィールド b はリストの何番目だったかな、a の次の 2 番目か、いや先頭にデータ型のシンボルが入るから 3 番目か、などと考えながらプログラムするのではストレスがたまってしまいますね。
もうひとつは、データ構造を変更するときです。たとえば、フィールド a が不用になったので、リストから削除することにしました。すると、スロット b の位置がひとつずつ前へずれるので、アクセスしている個所をすべて修正しなければいけません。データへのアクセスは単なるリスト操作関数にすぎないので、その関数が目的のデータを操作しているのか、それとも、それ以外のデータを操作しているのかを区別しながら、すべてのプログラムを修正しなければいけません。この修正作業は、プログラムの規模が大きくなればなるほど困難なものになります。
ようするに、データに直接アクセスするから、このような問題を引き起こすのです。そこで、次のようなアクセス関数を定義してみましょう。
リスト : アクセス関数 (defn get-a [data] (second data)) (defn get-b [data] (nth data 3))
アクセス関数の仕様さえわかっていれば、フィールド a がリストの 2 番目の要素に対応するといった、データ構造の詳細を把握する必要はありませんね。それから、関数名によってスロットの値をリードしていることが明確になります。また、フィールド a を削除する場合、関数 get-a を検索すれば、修正個所を簡単に見つけることができます。フィールド b にしても、関数 get-b を (second data) に修正するだけで、ほかのプログラムを見直す必要はまったくありません。
このように、データ構造に直接アクセスせず、アクセス関数を経由してデータの読み書きを行うことを、「データ抽象」とか「カプセル化」といいます。わざわざアクセス関数を用意するのは面倒なようですが、そのことによりデータ構造の細かいところを気にしなくてもいいわけです。それだけプログラムも読みやすくなり、修正にも強いプログラムを作ることができます。
このデータ抽象を進めていくと「オブジェクト指向」へとつながります。Common Lisp には Common Lisp Object System (CLOS) というオブジェクト指向システムがあります。興味のある方は拙作のページ「お気楽 CLOS プログラミング入門」をお読みください。
それでは簡単な例題として、「キュー (queue)」という基本的なデータ構造を作ってみましょう。Clojure には標準で Queue が用意されていますが、私達でも簡単にプログラムすることができます。
キューは「待ち行列」といわれるデータ構造です。たとえばチケットを買う場合、窓口に長い列ができますが、それと同じだと考えてください。チケットを買うときは、列の途中に割り込むことはできませんね。いちばん後ろに並んで順番を待たなければいけません。列の先頭まで進むと、チケットを購入することができます。
このように、要素を取り出す場合は列の先頭から行い、要素を追加する場合は列の後ろに行うデータ構造がキューなのです。キューは「先入れ先出し (FIFO : first-in, first-out)」とも呼ばれます。
先頭 最後尾
---------------------------
<= 1 2 3 4 5 . . . n <=
---------------------------
先頭 最後尾
変数 ┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
queue ─→│・│・┼─→│・│・┼─→│・│・┼・・・→│・│／│
└┼┴─┘ └┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓ ↓
１ ２ ３ ｎ
図 : キューの構造
キューにデータを入れることを enqueue といい、キューからデータを取り出すことを dequeue といいます。リストを使ってキューを実装する場合、上図のようにキューの先頭とリストの先頭を対応させます。すると、キューからデータを取り出すには、リストの先頭からデータを取り出すだけですみます。これはとても簡単ですね。
ただし、キューにデータを入れるには、リストの最後尾にデータを追加することになるため、ちょっとした工夫が必要になります。たとえば、データの追加に関数 concat を使うと、データを追加するたびにリスト (キュー) がコピーされてしまいます。このため、キューに格納されているデータが多くなると時間がかかるようになります。
そこで、今回はちょっと変わった方法ですが、連結リストを 2 つ使ってキューを作ってみましょう。なお、この方法は関数型言語のライブラリ (たとえば SML/NJ など) で用いられています。
次の図を見てください。
先頭
変数 ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
front ─→│０│・┼─→│１│・┼─→│２│／│
└─┴─┘ └─┴─┘ └─┴─┘
最後尾
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
rear ─→│５│・┼─→│４│・┼─→│３│／│
└─┴─┘ └─┴─┘ └─┴─┘
図 : キューの構造 (改良版)
上図は 2 つのリストでキューを表しています。データを取り出すときは front のリストを、データを追加するときは rear のリストを使います。front と rear で一つのキューを構成し、rear のリストはデータを逆順で格納することになります。ようするに、front が先頭で rear が最後尾になるわけです。上図のキューを一つのリストで表すと (0 1 2 3 4 5) になります。
したがって、front が空リストでも rear にデータがあれば、キューは空ではありません。rear のリストを逆順にして front にセットし、rear を空リストにします。これで front からデータを取り出すことができます。キューが空の状態は front と rear が両方とも空リストの場合です。
それではプログラムを作りましょう。次のリストを見てください。
リスト : キュー (myqueue.clj)
;; immutable なキュー
(defrecord ImQueue [front rear])
;; 空のキュー
(def empty-queue (->ImQueue '() '()))
;; キューは空か
(defn empty-queue? [q]
(and (not (seq (:front q))) (not (seq (:rear q)))))
;; 挿入
(defn enqueue [q x]
(assoc q :rear (cons x (:rear q))))
;; 取得 (キューが空の場合は nil を返す)
(defn top [q]
(cond
(seq (:front q)) (first (:front q))
(seq (:rear q)) (top (->ImQueue (reverse (:rear q)) '()))
:else nil))
;; 削除
(defn dequeue [q]
(cond
(seq (:front q)) (assoc q :front (rest (:front q)))
(seq (:rear q)) (dequeue (->ImQueue (reverse (:rear q)) '()))
:else nil))
レコード名は ImQueue (Immutable Queue) としました。フィールドは :front と :rear の 2 つを用意します。大域変数 empty-queue には空のキューをセットします。これは :front, :rear に空リストをセットするだけです。述語 empty-queue? はキューが空ならば真を返します。
関数 enqueue はキューにデータ x を挿入します。これは x を :rear の先頭に追加するだけです。関数 top はキューの先頭要素を返します。キューが空の場合は nil を返します。:front にデータがある場合は先頭要素を返します。:front が空リストの場合、:rear を反転したリストを :front にセットしたキューを作って、top をを再帰呼び出しします。
関数 dequeue はキューから先頭要素を取り除きます。キューが空の場合は nil を返します。処理は top とほとんど同じで、違いは :front の先頭要素を取り除いたキューを返すだけです。
それでは簡単な実行例を示します。
user=> empty-queue
#user.ImQueue{:front (), :rear ()}
user=> (empty-queue? empty-queue)
true
user=> (top empty-queue)
nil
user=> (dequeue empty-queue)
nil
user=> (def a1 (enqueue empty-queue 1))
#'user/a1
user=> a1
#user.ImQueue{:front (), :rear (1)}
user=> (def a2 (enqueue a1 2))
#'user/a2
user=> a2
#user.ImQueue{:front (), :rear (2 1)}
user=> (def a3 (enqueue a2 3))
#'user/a3
user=> a3
#user.ImQueue{:front (), :rear (3 2 1)}
user=> (top a3)
1
user=> (def a4 (dequeue a3))
#'user/a4
user=> a4
#user.ImQueue{:front (2 3), :rear ()}
user=> (top a4)
2
user=> (def a5 (dequeue a4))
#'user/a5
user=> a5
#user.ImQueue{:front (3), :rear ()}
user=> (top a5)
3
user=> (def a6 (dequeue a5))
#'user/a6
user=> a6
#user.ImQueue{:front (), :rear ()}
user=> (empty-queue? a6)
true
きちんと動作していますね。
次は「プロトコル (protocol)」について説明します。Clojure のプロトコルは関数の仕様を記述したもので、Java のインターフェースと似ています。プロトコルを使用すると、レコードの中で関数を定義することができ、レコードとその関数をオブジェクト指向言語のクラスとメソッドのように扱うことができます。
プロトコルは defprotocol を使って定義します。
(defprotocol p-name
(func-name1 [this a1 b1 ...]
(func-name2 [this a2 b2 ...]
・・・
(func-nameZ [this az bz ...]))
プロトコル名 p-name はシンボルで指定します。あとは関数名 func-name と引数 this, a, b, ... を指定します。マルチアリティ関数の場合、たとえば引数 [this a b] の後ろに引数 [this a b c] を指定します。なお、関数の宣言に defn は必要ありません。Clojure の場合、関数の第 1 引数 this にはプロトコルを実装したレコードを渡します。
レコードでは使用するプロトコル名を記述して、関数本体を定義します。
(defrecord r-name [f1 f2 ...]
p-name
(func-name1 [this a1 b1 ...] body ...)
(func-name2 [this a2 b2 ...] body ...)
・・・
(func-nameZ [this az bz ...] body ...))
レコードの中で関数を定義する場合、defn は必要ありません。関数の本体 body では、レコードのフィールド変数 f1, f2, ... をアクセス関数を使わずに直接参照することができます。もちろん、複数のプロトコルを使用することができます。
簡単な例を示しましょう。myqueue.clj をプロトコルを使って書き直すと、次のようになります。
リスト : キュー (myqueue1.clj)
;; プロトコル
(defprotocol MyQueue
(empty-queue? [this])
(enqueue [this x])
(dequeue [this])
(top [this]))
;; immutable なキュー
(defrecord ImQueue [front rear]
MyQueue
;; キューは空か
(empty-queue? [_]
(and (not (seq front)) (not (seq rear))))
;; 挿入
(enqueue [q x]
(assoc q :rear (cons x rear)))
;; 取得 (キューが空の場合は nil を返す)
(top [_]
(cond
(seq front) (first front)
(seq rear) (top (->ImQueue (reverse rear) '()))
:else nil))
;; 削除
(dequeue [q]
(cond
(seq front) (assoc q :front (rest front))
(seq rear) (dequeue (->ImQueue (reverse rear) '()))
:else nil)))
;; 空のキュー
(def empty-queue (->ImQueue '() '()))
プロトコル名は MyQueue としました。defrecord の中で MyQueue を宣言し、その後にプロトコルで宣言されている関数の実体を定義します。引数名はプロトコルと異なっていてもかまいません。Java のインターフェースと違ってデフォルトの定義はありません。メソッドの第 1 引数を使用しないのであれば、引数名を指定せずに匿名変数 ( _ ) で済ますことができます。あとは特に難しいところはないと思います。
簡単な実行例を示します。
user=> (def a (reduce (fn [q x] (enqueue q x)) empty-queue (range 0 8)))
#'user/a
user=> a
#user.ImQueue{:front (), :rear (7 6 5 4 3 2 1 0)}
user=> (loop [q a] (when-not (empty-queue? q) (println (top q)) (recur (dequeue q))))
0
1
2
3
4
5
6
7
nil
Clojure の場合、異なるレコードであれば同名の関数を定義することができます。たとえば、２次元の点を表すレコード Point と 3 次元の点を表すレコード Point3d で、2 点間の距離を求めるメソッド distance を定義してみましょう。
リスト : 2 次元と 3 次元の点
;; 距離を求めるメソッド
(defprotocol Distance
(distance [p1 p2]))
;; 2 次元の点
(defrecord Point [x y]
Distance
(distance [_ p2]
(let [{x2 :x, y2 :y} p2
dx (- x x2)
dy (- y y2)]
(Math/sqrt (+ (* dx dx) (* dy dy))))))
;; 3 次元の点
(defrecord Point3d [x y z]
Distance
(distance [_ p2]
(let [{x2 :x, y2 :y, z2 :z} p2
dx (- x x2)
dy (- y y2)
dz (- z z2)]
(Math/sqrt (+ (* dx dx) (* dy dy) (* dz dz))))))
x 座標をフィールド x に、y 座標をフィールド y に、z 座標をフィールド z に格納します。プロトコル Distance にはメソッド distance を宣言します。distance は引数を 2 つ受け取り、その距離を計算します。sqrt は平方根を求める関数 (メソッド) で、Java のクラス Math に定義されています。Math/sqrt で Java のスタティックメソッドを呼び出すことができます。
ここで、レコードで定義したメソッドの呼び出しは、第 1 引数に渡されるデータの型 (レコード) によって適切なメソッドが選択されることに注意してください。つまり、distance の第 1 引数が Point 型であれば、Point で定義されている distance が呼び出され、Point3d であれば Point3d の distance が呼び出されます。このように、プログラムの実行時に呼び出すメソッドを選択する機能を「ポリモーフィズム (polymorphism)」といいます。
それでは実際に試してみましょう。
user=> (def p1 (->Point 0 0)) #'user/p1 user=> (def p2 (->Point 10 10)) #'user/p2 user=> (def p3 (->Point3d 0 0 0)) #'user/p3 user=> (def p4 (->Point3d 20 20 20)) #'user/p4 user=> (distance p1 p2) 14.142135623730951 user=> (distance p3 p4) 34.64101615137755
このように、distance の第 1 引数のデータ型により、適切なメソッドが選択されます。引数をひとつ使ってメソッドを選択する方法を「単一ディスパッチ (Single dispatch)」といいいます。多くのオブジェクト指向言語はシングルディスパッチを採用しています。これに対し、複数の引数を使って、適切なメソッドを選択する方法もあります。これを「多重ディスパッチ (Multiple dispatch)」とか「マルチメソッド (Multimethods)」といいます。
多重ディスパッチを採用している言語はそれほど多くありませんが、有名なところでは Common Lisp Object System (CLOS) があります。最近では、Julia が多重ディスパッチです。Clojure の場合、defmulti と defmethod を使うと、メソッドの選択に「マルチメソッド」を使うことができます。これは回を改めて説明することにします。
多重ディスパッチに興味のある方は、拙作のページ「お気楽 CLOS プログラミング入門」や「お気楽 Julia プログラミング超入門」をお読みくださいませ。
もうひとつ簡単な例として、三角形、四角形、円を操作するプロトコルを考えてみましょう。次のリストを見てください。
リスト : 図形のプロトコル (defprotocol Figure (kind-of [this]) (area [this]) (display [this]))
プロトコル名は Figure にしました。kind-of は図形の種別をキーワードで返すメソッドです。area は面積を求めます。display は種別と面積を表示します。Figure を実装したレコードは、図形として共通の操作を行うことができます。 次は、三角形 (Triangle)、四角形 (Rectangle) 、円 (Circle) のレコードとメソッドを定義します。
リスト : 図形を表すレコード ;; 三角形 (defrecord Triangle [altitude base] Figure (kind-of [_] :Triangle) (area [_] (/ (* altitude base) 2.0)) (display [this] (printf "Triangle : area = %g\n" (area this)))) ;; 四角形 (defrecord Rectangle [width height] Figure (kind-of [_] :Rectangle) (area [_] (* width height)) (display [this] (printf "Rectangle : area = %g\n" (area this)))) ;; 円 (defrecord Circle [radius] Figure (kind-of [_] :Circle) (area [_] (* radius radius Math/PI)) (display [this] (printf "Circle : area = %g\n" (area this))))
メソッドの第 1 引数を使用しないのであれば、引数名を指定せずに匿名変数 ( _ ) で済ますことができます。あとは特に難しいところはないでしょう。
簡単な実行例を示します。
user=> (def a (->Triangle 2.0 2.0))
#'user/a
user=> a
#user.Triangle{:altitude 2.0, :base 2.0}
user=> (def b (->Rectangle 2.0 2.0))
#'user/b
user=> b
#user.Rectangle{:width 2.0, :height 2.0}
user=> (def c (->Circle 2.0))
#'user/c
user=> c
#user.Circle{:radius 2.0}
user=> (kind-of a)
:Triangle
user=> (kind-of b)
:Rectangle
user=> (kind-of c)
:Circle
user=> (area a)
2.0
user=> (area b)
4.0
user=> (area c)
12.566370614359172
user=> (display a)
Triangle : area = 2.00000
nil
user=> (display b)
Rectangle : area = 4.00000
nil
user=> (display c)
Circle : area = 12.5664
nil
user=> (reduce (fn [a x] (+ a (area x))) 0.0 [a b c])
18.566370614359172
最後の reduce は無名関数の中でメソッド area を呼び出していますが、ポリモーフィズムの働きにより各レコードのメソッド area が呼び出されるので、図形の面積を正しく求めることができます。
レコードはマップと同様の機能を持っていましたが、それらが必要ない、もしくは mutable なフィールド変数を使用したい場合は deftype を使うと便利です。
(deftype name [field1 field2 ...])
deftype はデータ型の定義のほかに、次の関数を生成します。
deftype はデータ型を定義して必要最低限な関数を生成するだけで、実際のデータを作り出すわけではないことに注意してください。
簡単な例を示しましょう。
user=> (deftype Foo [a b]) user.Foo user=> (def x (->Foo 1 2)) #'user/x user=> x #object[user.Foo 0x425d5d46 "user.Foo@425d5d46"] user=> (.a x) 1 user=> (.b x) 2 user=> (.a (Foo. 10 20)) 10 user=> (.b (Foo. 10 20)) 20 user=> (instance? Foo x) true user=> (record? x)
フィールド変数を mutable にする場合、変数名の前にメタデータ :volatile-mutable または :unsynchronized-mutable を指定します。メタデータの指定は ^ を使うと簡単です。
(deftype name [^:unsynchronized-mutable field ...] ...)
defrecord や deftype で定義したデータ型は Java のクラスにコンパイルされます。フィールド変数を mutable に設定すると、アクセス権限が private になるので、デフォルトのアクセス関数は使用できなくなります。そのため、プロトコルでアクセスメソッドを宣言して、deftype の中でメソッドを定義する必要があります。次のリストを見てください。
リスト : mutable なフィールド変数 (defprotocol AccessorX (get-x [this]) (set-x [this value])) (deftype Foo [^:unsynchronized-mutable x] AccessorX (get-x [_] x) (set-x [this value] (set! x value)))
defprotocol でメソッド get-x, set-x を宣言します。プロトコル名は AccessorX としました。次に deftype で Foo を定義します。フィールド変数 x は mutable に指定します。そして、プロトコル AccessorX を指定して、メソッド get-x, set-x を定義します。get-x は簡単です。メソッドの本体から直接フィールド変数 x にアクセスできるので、x の値を返すだけです。フィールド変数の書き換えは set! を使います。
(set! field value)
set! は mutable な変数 filed の値を value に書き換えます。簡単な実行例を示します。
user=> (def a (Foo. 100)) #'user/a user=> a #object[user.Foo 0x10876a6 "user.Foo@10876a6"] user=> (.x a) Execution error (IllegalArgumentException) at user/eval227 (REPL:1). No matching field found: x for class user.Foo user=> (get-x a) 100 user=> (set-x a 10) 10 user=> (get-x a) 10
このようにフィールド変数 x の値を書き換えることができます。
最後に、簡単な例題として「スタック (stack)」というデータ構造を作ってみましょう。次の図を見てください。
|-----| |[ A ]| |[ B ]| |[ A ]| |-----|
| | | |-----| |[ A ]| |-----| | | |
| | | | | | |-----| | | | | | |
| | | | | | | | | | | | | | |
| | | | | | | | | | | | | | |
+-----+ +-----+ +-----+ +-----+ +-----+
(1) 空の状態 (2) PUSH A (3) PUSH B (4) POP B (5) POP A
図 : スタックの動作例
上図は、バネがついた容器を表していて、上から品物を出し入れすることができます。初めは空の状態です。ここに品物を乗せると、重さによってバネを圧縮し、品物が容器に格納されます。さらにもう一つ品物を上に乗せると、さらにバネを圧縮し、その品物も容器に格納することができます。バネが限界まで圧縮されると、もう品物は追加できなくなります。取り出す場合は、上にある品物から行います。一つ取り出すと、その分バネが伸びて下にある品物が上に押し出されます。
この容器の動作が、スタックの動作なのです。スタックにデータを追加する操作をプッシュ (PUSH) といい、スタックからデータを取り出す操作をポップ (POP) といいます。品物をデータに見立てれば、データ A をスタックにプッシュし (2)、次にデータ B をプッシュします (3)。データを取り出す場合、あとから入れたデータ B が先にポップされ (4)、その次にデータ A がポップされてスタックが空になります (5)。このように、スタックはあとから入れたデータが先に取り出されるので、後入れ先出し (LIFO : Last-In, First-Out) と呼ばれます。
Clojure の場合、スタックはリストを使って簡単に実現することができます。データを追加するときはリストの先頭に追加し、データを取り出すときはリストの先頭から行うように操作を限定すると、スタックの動作と同じになります。今回は immutable と mutable の二種類のスタックを作ることにします。
最初にプロトコルを定義しましょう。次のリストを見てください。
リスト : スタックのプロトコル (defprotocol PStack (top [this]) (empty-stack? [this])) (defprotocol PImStack (push-stack [this x]) (pop-stack [this])) (defprotocol PMuStack (push-stack! [this x]) (pop-stack! [this]))
プロトコル PStack は immutable と mutable で共通なメソッドを宣言します。top は先頭データを求めるメソッドで、empty-stack? はスタックが空ならば真を返す述語です。PImStack は immutable なスタック用のメソッドを宣言します。push-stack はスタックにデータを追加するメソッド、pop-stack はスタックからデータを取り出すメソッドです。immutable なので、新しいスタックを返すことに注意してください。
PMuStack は mutable なスタック用のメソッドを宣言します。push-stack! はスタックにデータを追加するメソッド、pop-stack! はスタックからデータを取り出すメソッドです。mutable なので、スタックを破壊的に修正することに注意してください。
次は immutable なスタック本体を定義しましょう。immutable なので defrecord を使うことにします。次のリストを見てください。
リスト : immutable なスタック
(defrecord ImStack [front]
PStack
(top [_] (first front))
(empty-stack? [_] (not (seq front)))
PImStack
(push-stack [_ x] (->ImStack (cons x front)))
(pop-stack [_]
(when (seq front) (->ImStack (rest front)))))
;; 空のキュー
(def empty-ImStack (->ImStack '()))
レコード名は ImStack としました。フィールド変数 front にスタック本体 (リスト) を格納します。メソッド top は front の先頭要素を first で求めます。empty-stack? は front が空リストならば真を返します。push-stack は front の先頭に x を追加し、それを格納した新しい ImStack を返します。pop-stack は front が空リストでなければ、rest で先頭要素を取り除き、それを新しいスタックに格納して返します。変数 empty-ImStack には空のスタックをセットします。
それでは実行してみましょう。
user=> empty-ImStack
#user.ImStack{:front ()}
user=> (empty-stack? empty-ImStack)
true
user=> (def a1 (push-stack empty-ImStack 1))
#'user/a1
user=> a1
#user.ImStack{:front (1)}
user=> (def a2 (push-stack a1 2))
#'user/a2
user=> a2
#user.ImStack{:front (2 1)}
user=> (top a1)
1
user=> (top a2)
2
user=> (def a3 (pop-stack a2))
#'user/a3
user=> a3
#user.ImStack{:front (1)}
user=> (top a3)
1
user=> (def a (reduce (fn [s x] (push-stack s x)) empty-ImStack (range 0 8)))
#'user/a
user=> a
#user.ImStack{:front (7 6 5 4 3 2 1 0)}
user=> (loop [a a] (when (not (empty-stack? a)) (println (top a)) (recur (pop-stack a))))
7
6
5
4
3
2
1
0
nil
正常に動作していますね。
次は mutable なスタック本体を定義しましょう。mutable なので deftype を使うことにします。次のリストを見てください。
リスト : mutable なスタック
(deftype MuStack [^:unsynchronized-mutable front]
PStack
(top [_] (first front))
(empty-stack? [_] (not (seq front)))
PMuStack
(push-stack! [_ x] (set! front (cons x front)))
(pop-stack! [_]
(when (seq front) (set! front (rest front)))))
;; 空のキュー
(defn make-MuStack [] (->MuStack '()))
名前は MuStack としました。フィールド変数 front を mutable に指定します。top と empty-stack? は ImStack と同じです。push-stack! は front の先頭に x を追加し、その値で front を書き換えます。pop-stack! は rest で front の先頭要素を取り除き、その値で front を書き換えます。関数 make-MuStack は空のスタックを生成して返します。
それでは実行してみましょう。
user=> (def b (make-MuStack)) #'user/b user=> b #object[user.MuStack 0x50a3d0f6 "user.MuStack@50a3d0f6"] user=> (empty-stack? b) true user=> (push-stack! b 1) (1) user=> (empty-stack? b) false user=> (top b) 1 user=> (push-stack! b 2) (2 1) user=> (top b) 2 user=> (push-stack! b 3) (3 2 1) user=> (top b) 3 user=> (pop-stack! b) (2 1) user=> (top b) 2 user=> (pop-stack! b) (1) user=> (top b) 1 user=> (pop-stack! b) () user=> (empty-stack? b) true user=> (dotimes [x 8] (push-stack! b x)) nil user=> (while (not (empty-stack? b)) (println (top b)) (pop-stack! b)) 7 6 5 4 3 2 1 0 nil
正常に動作しているようです。興味のある方はいろいろ試してみてください。