Clojureにおけるデータ構造の抽象化を理解して独自のデータ構造を実装する Part 1: Collectionとは何か

この記事シリーズでは、プログラマもしくはライブラリ作者が独自のデータ構造を作成する際、それをClojureの組み込みデータ構造と同等に振る舞わせる方法について説明する。このPart 1では、Clojureの組み込みデータ構造がどのような抽象化とデザインの上に構築されているかを見てみよう。最後に、vector型と同じように振る舞うデータ型を定義してみる。

• Part 0: 導入
• Part 1: Collectionとは何か（ここ）
• Part 2: Sequenceとは何か
• Part 3: 独自Vector作成をマクロ化してみる

おことわり：

• この記事は入門では無く、ClojureとJavaの知識をある程度仮定している。
• 末尾に示した参考文献を大いに参考にさせていただいた。

伝統的なLispにおけるデータ構造

伝統的なLispでは、基本となるデータ構造はListである。そもそもLispという名前からしてLISt Processingから来ている。Listというのは、計算機科学の用語で言うと連結リストだ。リストを構成するノードはConsセルと呼ばれていて、本質的にはポインタのタプルである。Lispにおいては、最も頻繁に使われるデータ構造はリストだし、プログラム自体もリストだ。

しかし、現代的なプログラミング言語の立場から見ると、この伝統的リストは問題が多い。一言で言えば、具体的すぎるということだ。もっと細かく言うと、

• 構造が具体的に決められてしまっている
• 従って、動作も具体的に決められてしまっている

ということになる。別の言い方をすると抽象度が低いのだ。抽象度が低いと、下のレイヤでの最適化の余地が少なくなってしまう。特に並列化については問題だ。通常のリストだと、並列化のしようがない。だから、データ構造については、「構造と動作を具体的に決める」のではなく、「満たすべき性質を定め、実装の詳細は隠蔽する」べきなのだ。

Clojureにおけるデータ構造の抽象化

Clojureではより抽象化したcollectionとsequenceというものを用いている。非常に簡単に述べると、

• collection = データの集まりを抽象化した物
• sequence = データの集まりについて、順次アクセスによってデータへアクセスできるようなデータの表現方法（View）

となる。いきなりこれだけを説明されても何が何だかわからないと思うが、順次説明していきたいと思う。このPart 1では、Collectionについてどのような抽象化が行われているのかを見てみよう。Sequenceについては次回に送る。

Collectionとは何か。何を満たせばcollectionなのか

Clojureにおいては、「collectionである」とは 「coll? 関数で真が返る」ということだ。

user=> (coll? [])
true
user=> (coll? {})
true
user=> (coll? #{})
true

もっと具体的に言うと、coll?の定義は 「IPersistentCollectionを実装しているかどうか」だ。しかし、これでは説明になっているとは言いがたいので、もう少し「意味」を考えてみよう。IPersistentCollectionには、5つのメソッド（count, cons, empty, equiv, seq）が定義されている（interfaceの継承による間接的なものも含む）。これらの意味はというと

メソッド名	意味
count	様子の個数を返す
cons	要素を１つ追加する（Clojureレベルではconjのこと）
empty	このcollectionにおける空集合を表す定数を返す
equiv	collection同士が等しいかどうかを判定する
seq	Sequenceを返す

となる。これが「collectionである」ということの定義だ。これらの5つの操作をサポートすれば、それはcollectionであると言える。なお、Sequenceを返すseq()については後に述べるのでここでは触れない。

collectionは、サポートする操作や属性によってさらに分類されている。大きな分類が次の3つだ。

分類	意味
Associative	連想配列のように、キーから値を取得できる
Counted	要素の個数がO(1)時間で求まる
Sequential	決まった順番で要素について繰り返しができることを保証する

これらの3つの部分集合と、Clojureの組み込み型との対応関係を示したのが下の図だ。

ここで1つ注意して欲しいのは、SequentialとSequenceは別物であるということだ。名前が似ているが、別物だ。SequentialというのはCollectionの部分集合であるが、SequenceはCollectionとは異なる別の概念だ。

具体的なcollection：vectorを例に

具体的なcollectionとしてvectorを見てみる。他のデータ型については、本質的には同じで個別の違いだけなので省略する。vectorは、上の図を見ればわかるように、Associative・Counted・Sequential の3つを全て満たすものだ。実装上必要な細かいものも含めて、IPersistentVectorが実装しているインターフェースをClojureのソースコードから抜き出してみると次のようになる。

インターフェース	実装メソッド
IPersistentCollection	count,cons,empty,equiv,seq
Associative	containsKey, entryAt, assoc
Counted	count
Sequential	（具体的なメソッドは無し）
IPersistentStack	peek, pop
Reversible	rseq
Indexed(Counted)	count, nth

独自vectorを実装してみる（不完全版）

以上のinterfaceによって定義されるメソッドを全て実装すれば、独自のvectorが定義できるはずだ。やってみよう。

例題とするのは、一部の要素がfutureによって遅延・並列評価されているが、それが隠蔽されているvectorのようなデータ構造だ。

(deftype MyVec [contents]
  clojure.lang.Associative
  (entryAt [_ key]
    (let [v (.entryAt contents key)]
      (if (future? v)
        @v
        v)))
  (assoc [_ key, val]
    (MyVec. (.assoc contents key val)))

  clojure.lang.IPersistentStack
  (peek [_] (.peek contents))
  (pop [_] (MyVec. (.pop contents)))

  clojure.lang.Indexed
  (nth [_ i]
    (let [v (.nth contents i)]
      (if (future? v) @v v)))
  (nth [_ i not-found]
    (let [v (.nth contents i not-found)]
      (if (future? v) @v v)))

  clojure.lang.IPersistentCollection
  (count [_]
    (.count contents))
  (empty [_]
    (.empty contents))
  (equiv [_ o]
    (and (isa? (class o) MyVec)
         (.equiv contents (:contents o))))

  clojure.lang.ILookup
  (valAt [_ k]
    (let [v (.valAt contents k)]
      (if (future? v)
        @v
        v)))
  (valAt [_ k not-found]
    (let [v (.valAt contents k not-found)]
      (if (future? v)
        @v
        v)))

  clojure.lang.IPersistentVector
  (assocN [_ i val]
    (MyVec. (.assocN contents i val)))
  (cons [_ o]
    (MyVec. (.cons contents o)))

  clojure.lang.Sequential)

(defn heavy-computation [a]
  (Thread/sleep 10000)
  a)

(defn myfunc []
  (MyVec. [:a
           (future :b)
           (future (heavy-computation :c))
           :d]))

(defn foo [& args]
  (time
   (let [v (myfunc)]
     (println (get v 0))
     (println (get v 1))
     (println (get v 2))
     (println (get v 3)))))

(foo) 
=> :a
   :b
   :c
   :d
   "Elapsed time: 10004.761063 msec"

(println (myfunc))
=> AbstractMethodError    clojure.lang.RT.seqFrom (RT.java)

一部のフィールドがfutureになっているが、外から見ると普通のvectorと全く同じように要素にアクセスできていることに注目して欲しい。また、defrecordでなくてdeftypeを使っていることに注意しよう。defrecordは、map型のインターフェースをサポートするように自動的にinterfaceの実装をおこなってしまうのでいろいろと都合が悪いからだ。

このコードでは、ISeq interfaceのseq()、Reversible interfaceのrseq()の実装は省略した。だから実際、printしようとするとエラーが起こる。printlnは内部でcollectionをISeqに変換しているためだ。collectionをきちんと実装するためには、ISeqについても正しく実装することが求められる。次回は、ISeqについて理解を深めたい。続く。

参考文献

• Clojure - sequences
• Collections and Sequences in Clojure | Clojure Documentation | Clojure Docs
• Seqs and Colls in Clojure

P.S.

関係ないけどClojure Cookbook書籍版買いました

Clojure Cookbook: Recipes for Functional Programming