翻訳:"Inside Clojure's Collection Model"
The original article is written by Alex Miller (@puredanger). Translated by Keisuke Fukuda (@keisukefukuda)
この記事は,”Inside Clojure’s Collection Model”の日本語訳です.原著者のAlex Millerさんの許可を得て公開しています.翻訳に関する指摘は翻訳者まで.(athosさんありがとうございました)
Alex Millerさんは,Clojureの主要な開発者の一人であり,リリースマネージャの役割もされ,メーリングリストにおける活動量も非常に多い方です.また,Clojure Applied: From Practice to Practitionerの著者でもあります.
Clojureのコレクションについて,私(翻訳者)の記事「Clojureにおけるデータ構造の抽象化を理解して独自のデータ構造を実装する」も参照してください
Inside Clojure’s Collection Model
Clojureのコレクション型には何があるでしょうか?ほとんどのClojurianは,list, vector, map, setで十分だと言うと思います.seq
を加えてもいいかもしれません.Seq
は,コレクションの抽象化(View)で,コレクションを使って実装することもできるし,別の何かを使って実現することもできるものです.(この点についてはSequencesを見てください.)
しかし,Clojureにはsorted map, sorted set, queue, 組み込み型の配列,Javaの配列,Javaのコレクションなどなど,そしてもちろん deftype
によるユーザー定義の型があります.ここまでくると,だいぶ話が込み入ってくるでしょう.そして,判定関数(sequential?
, seq?
, coll?
)がこれらのコレクション型に対して返す値は,わけがわからないように見えるかもしれません.
少し調べるとわかりますが,コレクションには,一見してわかるよりも,込み入った事情があります.Clojureは,日々使われる基本機能を提供するために,いくつかの異なる層を提供しています.最も優れた点は,Clojureの機能(コンパイラ,ランタイム,標準ライブラリ)はコレクションの実装には全く依存せず,拡張可能な抽象化層の上に 構築されているという点です.Clojure初心者のうちはこれらの拡張機能に触ることはほとんどないでしょうが,より洗練されたプログラムを書くためにこれらの機能が有用だということが徐々にわかってくることでしょう.
Traitと判定関数
Clojureのコレクション・ライブラリの中で最も重要な層は,おそらくTraitでしょう(Traitというのは私独自の用語です).TraitはClojureのProtocolの機能を用いて実装されているのが理想ですが,これらの機能はProtocolの導入よりも前に遡るので,Javaのインターフェースとして定義されています.
重要なtraitクラスをいくつか紹介しましょう(すべてclojure.lang
パッケージにあります):
Counted
- 数え上げ可能(加算*1)なコレクションcount()
Indexed
-Counted
をextendしていて,インデックスによる参照が可能nth(int i)
nth(int i, Object notFound)
Sequential
- シーケンシャルなコレクションのためのマーカーインターフェース
Associative
(ILookup
をextend)containsKey(Object key)
entryAt(Object key)
assoc(Object key, Object val)
ILookup
経由:valAt(Object key)
valAt(Object key, Object notFound)
Sorted
- 並べ替え済みコレクションのためのマーカーSeqable
*2 - sequenceを生成することができるコレクションseq()
Reversible
- 逆向きsequenceを生成できるコレクションrseq()
それぞれのインターフェースは,コレクションが持ちうる特性・属性の一部を示しています.そして,ほとんどの判定関数は,それぞれのインターフェースをimplementしているかどうかをチェックしているに過ぎないということがわかります.
counted?
-Counted
をimplementしているかindexed?
-Indexed
をimplementしているかsequential?
-Sequential
をimplementしているかassociative?
-Associative
をimplementしているかsorted?
-Sorted
をimplementしているか?reversible?
-Reversible
をimplementしているか
上の表で欠けているのはILookup
とSeqable
です.ILookup
は,Associative
の非常に小さなサブセットで,Associative
の方が汎用です.Seqable
は少し厄介で,文字列や配列をseqableと判定するために,Clojureはちょっといろいろなことをやっています.もし当時Protocolが存在していれば,このような「閉じた型」についてもSeqableが直接的に実装されていたでしょう*3.これについては「Sequences」という記事を読んでください.
重要な事は,clojure.core
やclojure.lang.RT
にある集合関数のほとんどは,これらのtraitを操作するのであって,具体的なコレクションの型や,コレクションのインターフェースを操作するわけではないということです.
これを追いかけるのは少々大変です.ほとんどの標準のコレクション関数(count
,nth
, get
, assoc
, seq
)は上記のインターフェースと明示的に対応しています.Clojureのcore関数のソースコードを見ると,それらのメソッドの殆どがRT
クラスへ転送されていることがわかります.そしてRT.count()
をみると,まず第一の実装として上記のインターフェースの関数が起動されています(そして,いくつかの特殊ケースについては特別な実装がされています).もう一度書きますが,もしProtocolを使えばこれらの実装はより綺麗になるはずです.
この実装の利点は,これらのtraitをいくつか実装した型を作れば,既存のClojureの実装に手を加えることなく,協調して動作することができるということなのです
Collections
Clojureのコレクションも,Javaインターフェースの実装が最初に行われています.大半のインターフェースは,コレクションがどのようなtraitsを持つかどうかを定義するものです.
(実は,詳細については少し誤魔化しています.これらの実装が行われている実際のクラス階層は少々ややこしいからです).わかりやすい例は,IPersistentVector
で,これはAssociative
,Sequential
,Reversible
,Indexed
をextendしています.似たようなインターフェースとして,IPersistentSet
,IPersistentMap
,IPersistentList
と,より上位レベルのIPersistentCollection
があります.ここで説明はしませんが,それ以外にもclojure.core
のpeek
とpop
を通して使用できるIPersistentStack
があります
最後に,多くの具体型があります(実際には,型ごとに複数存在しています)
IPersistentList
PersistentList
- 普通のリストPersistentList$EmptyList
- 特別な場合(空リスト)-
PersistentQueue
- キューの実装
IPersistentVector
IPersistentSet
PersistentHashSet
- 普通のsetPersistentTreeSet
- 並べ替え済みset
IPersistentMap
PersistentArrayMap
- 0〜8要素の時に使われる配列ベースのmapPersistentHashMap
- 普通のhash mapPersistentTreeMap
- 並べ替え済みmapPersistentStructMap
defstruct
から生成される(現在は実質的に廃止)defrecord
は,すべてIPersistentMap
のインスタンスを実装する
しかし,シーケンスについてはどうなのでしょう?ここでどのような役割を果たしているのでしょうか?ここから,話が少しややこしくなってくるのです
シーケンス
シーケンスは,論理的なイミュータブルコレクションを表します.シーケンスがコレクションから生成された時は,コレクションの上に構築されたシーケンスということになりますが(私はこれらのシーケンスを「コレクションのView」だと考えています),一方で関数から必要に応じて生成することもできますし,それ以外のデータから生成することもできます(文字列,配列,イテレータなど)
ここで重要なのは,シーケンスもまたJavaのインターフェースによって実装されているということです
ISeq
- シーケンスの抽象化で,seq?
判定関数でチェックできるSeqable
- (前述)シーケンスを生成することができるもの
ここでややこしいのが,ISeq
はIPersistentCollection
を実装しているということです.よって,シーケンスは実質的にコレクションとして扱うこともできますが,IPersistentList
ではありません.紛らわしいのは,シーケンスとリストはどちらも括弧を用いて表示されるということです.
コレクションの時の同じように,シーケンスの実装はたくさんあります
LazySeq
遅延シーケンスCons
cons
呼び出しの結果ChunkedCons
map
やfilter
などのチャンクされた遅延シーケンスの結果ArraySeq
- 配列上のシーケンスStringSeq
- 文字列上のシーケンス- 他にもたくさん!
等価性
Clojureのコレクションは,等価性における種別(Equalily Partition*4)(sequential, map, set)に基づいて定義されています.等価性は,常に値の比較によっています:コレクション同士が等価性における同じ種別かどうか,そして同じ値を含むかどうか?ということです.
ここが,Clojureが他の言語と大きく異なる点です.Clojureのコレクションは 1) immutableであり 2) 値によって等価性が判定されます.この結果,Clojureのコレクションを値の合成として扱うことができ,イミュータブルで単純な値を使うことの利点を享受できるのです.
シーケンシャルなコレクション(list, vector, シーケンス,そしてsequentialであるとマークされたものであれば何でも)では,比較は先頭から末尾へ要素ごとに行われます.シーケンシャルなコレクションは,比較の際にコレクションの種類をチェックしません.
これは,場合によっては欲しい挙動ではないでしょう(例えば戻り値のテストをするときなど).しかし,比較においてシーケンシャルなコレクションを同一視することは,Clojureにおける利便性のための実用的で優れた選択で,特にシーケンスとコレクションの境界線を曖昧にすることに効果を発揮します.
Setは,完全に同一の集合で,互いに余計な要素を持たない時に等しいと判定されます(ここで「同一」といっているのは 「=
演算子がtrue
を返す」という意味で,オブジェクトの同一性を指しているわけではありません).
Mapは,互いに同一のキーを持っていて,それぞれのキーが互いに同一の要素を返すときに等しいと判定されます.
まとめ
Clojureのコレクションが水面下でどのように実装され,抽象化を用いてどのように統合されているかということの概要を理解するのに,この記事が役立てば幸いです.これらの抽象化は,追加のコンポーネントを組み込むために使うことができますので,これは次の記事のテーマで扱うかもしれません.
2016年3月16日
Originally post written by Alex Miller Translated by Keisuke Fukuda