Clojureにおけるデータ構造の抽象化を理解して独自のデータ構造を実装する Part 2: Sequenceとは何か
前回に引き続き、次はsequenceについて見ていこう。 （編集：athosさんに間違いを指摘していただいたので、内容を大幅に修正しました 2015/08/14）
Clojureを始めたばかりの時、
user=> (seq? []) false
となることに驚いて 「アイエエエ! false!? falseナンデ!?」 となった人は多いはずだ。 Sequenceってのは、リストっぽいものの抽象化じゃなかったのか？ vectorは一番リストっぽいものじゃないか。 なんでこれがfalseになるんだ？
今回は、Sequenceとは何かを説明することで、この辺りの紛らわしい点を明らかにしたい。
目標は、
- sequenceとは何で、何のために存在するのか？
- Sequenceとcollectionの違いは何か？
- 何を満たせばsequenceなのか？
といった点を理解することだ。
おことわり：
Sequenceとは何で、何のために存在するのか？
Sequenceとは、一言で言えば「Collectionの特殊な形態であり、Collectionを表現する方法の1つで、Lispの伝統的リストや関数型言語風味のもの」だ。Sequenceの 目的は2つある。1つは、Collection間の統一的なインターフェースを提供すること、2つめは普通のCollectionでは表現できない 特殊な集合を表現することだ。
インターフェースとしてのSequence
C++やJavaのイテレータに類似したものだということもできるだろう。C++のSTLでは、std::vectorやstd::listといった コンテナ型に対して、その要素に逐次的にアクセスするためのイテレータという概念が提供されている。ClojureのSequenceも、 これに近いものだと考えると理解しやすいかも知れない。
なぜ、そんなものが必要なのだろうか？それは、複数種類存在するClojureのCollection同士や、Collectionとその他のコードの間に 統一的なインターフェースがあると便利だからだ。例えば、次のコードを考えてみよう。
user=> (set [1 2 3]) #{1 3 2}
ここでは、vectorのデータを元にsetを作成している。当たり前のように思えるが、これが可能なのはvectorをSequenceに変換する事が可能だからだ。変換するというよりはvectorを表すsequenceを作ると言うべきか。Sequenceという共通インターフェースを介してsetとvectorの橋渡しがされている。再びC++で例えると、コンテナのコンストラクタにbeginイテレータとendイテレータを渡せば、ほぼ任意のコンテナ間の変換ができることと似ている （C++をご存じない人はすいません。）
ちなみに、上記の操作の逆（set → vector）は一発では変換できず、applyとseqの呼び出しを介す必要がある。このあたりは
やや実装依存の些末事項といってよいところだと思うので深入りしない。
ちなみに、set→vectorの逆方向はvec関数で行える。
user=> (vec #{1 2 3}) [1 3 2]
特殊な集合の表現としてのSequence
Sequenceのもう1つの役割は、遅延評価を用いることにより、Collectionでは直接表現できない（したくない）データの集合を表現することだ。 「アクセスは先頭要素から1個ずつ」という制約がこれを可能にする。 厳密に言うと、遅延評価の目的は単純に処理を遅延したい場合と無限集合を扱いたい場合の2通りあるが、ここでは区別しない。
以下は、遅延評価Sequence（LazySeq）の例として稀によく使われる「正の偶数全体を表し、それへの逐次アクセスを提供するLazySeq」だ。
user=> (defn positive-evens ([] (positive-evens 2)) ([n] (cons n (lazy-seq (positive-evens (+ n 2)))))) user=> (take 10 (positive-evens)) ; => (2 4 6 8 10 12 14 16 18 20)
positive-evensの定義で cons を用いているのは、実はconsもSequenceに他ならないからだ。 Sequenceが伝統的リストの一般化だと考えれば当たり前かも知れない。なお、Clojureのconsには制約があって、2つめの要素（cdr）もSequenceでなければならない。Common LispやSchemeでは特にその制限は無い。
;; Common Lisp or Scheme > (cons 1 1) (1 . 1) ;; Clojure > (cons 1 1) IllegalArgumentException Don't know how to create ISeq from: java.lang.Long clojure.lang.RT.seqFrom (RT.java:505) > (cons 1 nil) (1) > (cons 1 '()) (1)
Sequenceとcollectionの違いは何か？
一言で言えば、Sequenceとは「Collectionの一種（特殊な場合）で、他のCollection間のインターフェースとなり、ついでに 他のCollectionでは表せない特殊な集合を表すのにも使われる。
この「SequenceはCollectionの一種である」という事実が話を全体的にややこしくしている。 それぞれのCollectionは、それぞれの内部構造に応じた方法でSequenceへの変換方法とSequenceからの変換方法を 提供する。伝統的リストの役割を分解・整理したものがSequenceであるから、当然と言えば当然なのだが。
だから、Sequenceを「Collectionの表現方法」と見たとき、CollectionとSequenceの対応は一意とは限らない。 一番身近な例としては、標準関数のseqとrseqがあるだろう。
user=> (seq [1 2 3 4 5]) ; => (1 2 3 4 5) user=> (rseq [1 2 3 4 5]) ; => (5 4 3 2 1)
もっと意味のありそうな例としては、木構造データを考えるとよいだろう。木構造というのは、用途にもよるが 一種の集合と考えることができるから、Collectionだ。 そして、この木構造を逐次的に走査する方法というのはいくつか考えられる。 例えば、幅優先探索と深さ優先探索。それぞれ逆を考えれば、これだけで4通りのSequenceが考えられる。
Part1で示したベン図に、Sequenceを加えたものが下の図だ。
何を満たせばsequenceなのか？
だいぶ前半が長くなったが、具体的にどのような条件を満たせばSequenceとして扱えるのかということを見ていこう。 基本としては、ISeq interfaceを実装することが基本となる。ISeqインターフェースは4つのメソッドを持つ。
| メソッド名 | 意味 |
|---|---|
| first | 現在の先頭要素を返す。伝統的Lispでいうcar。 |
| next | 残りの要素を返す。Sequenceの終わりならnilを返す。伝統的Lispでいうcdr。 |
| more | 残りの要素を返す。Sequenceの終わりなら空リスト '() を返す。 |
| cons | 先頭に要素を付加した新しいSequenceを返す |
Clojureのコードを調査したところ、実際にClojureのエコシステムの中でSequenceとして機能させるには、 追加で2つのインターフェース（Sequential、Seqable）を実装することが必要なようだ。両者とも簡単なものだ。
以上をまとめて、自前でSequenceを作ってみよう。例題として、コラッツの問題を取り上げてみる。 （コラッツの問題 - Wikipedia）
コラッツの問題とは、任意の正整数Nからスタートして、「もし偶数なら2で割り、奇数なら3N+1を計算する」という手順を繰り返して数列を作ったときに、すべてのNで「1」に到達するかどうか？という問題だ。ある正整数Nからスタートするコラッツの数列を、Sequenceとして表してみよう。 以下のコードでは、lazy-seq を用いる普通の方法と、自前でdeftypeを用いて定義する方法の2通りを実装してみる。
;; lazy-seqを使う方法 (defn collatz [n] (cons n (if (= n 1) nil (lazy-seq (collatz (if (even? n) (/ n 2) (+ (* 3 n) 1))))))) ;; deftypeを使った自前のCollatz列 (deftype MyCollatz [n] clojure.lang.Sequential clojure.lang.ISeq (first [_] n) (next [_] (if (= n 1) nil (MyCollatz. (if (even? n) (/ n 2) (+ (* 3 n) 1))))) (more [_] (or (next _) '())) (cons [_ o] (cons o _)) clojure.lang.Seqable (seq [_] _)) (defn collatz2 [n] (MyCollatz. n)) (type (collatz 100)) ; => clojure.lang.Cons (type (collatz2 100)) ; => samples.core.MyCollatz (collatz 100) ;=> (100 50 25 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1) (collatz2 100) ; => (100 50 25 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1)
できた。次回は、Part1とPar2の結果を統合し、完全な独自のCollectionを作成し、さらにそれをマクロ化してみよう。
