Clojure-シーケンス

ClojureはLispの方言であるため、リストの操作が言語の重要な位置を占めることはまったく驚くことではありません。 確かに、伝統的な方言（CLまたはScheme）とは異なり、Clojureは従来のダブルスロットリストの代わりに、シーケンスの抽象化-「論理リスト」を使用します。 実際、不変、遅延、および場合によっては無限のシーケンスを操作するためのメソッドを提供するインターフェイスです。 この記事では、これらのエンティティの内部構造について説明します。

シーケンスの本質

Javaインターフェースから始めましょう。 Clojureのすべての構造はclojure.lang.Seqableを実装します 。

public interface Seqable { ISeq seq(); } 

次に、 clojure.lang.ISeqは次のように定義されます。

 public interface ISeq extends IPersistentCollection { Object first(); ISeq next(); ISeq more(); ISeq cons(Object o); } 

ここでは、 Iterable 、 ISeq （ Iteratorの一種）との類推を描くことができます。 主な違いは、 ISeqオブジェクトは不変であるということです 。そのメソッドは、オブジェクトの内部状態を変更する代わりに、新しいインスタンス（場合によっては異なるタイプ）を返します。 Clojureのすべてのシーケンスも同時にコレクションです-継承されたインターフェイスclojure.lang.IPersistentCollectionを実装し、それを通じてSeqableを実装します。

 public interface IPersistentCollection extends Seqable { int count(); IPersistentCollection cons(Object o); IPersistentCollection empty(); boolean equiv(Object o); } 

ここではcount-要素の数をカウントしています。 シーケンスの場合、その複雑さは明らかにO（n）です。 emptyメソッドは、同じタイプの空のコレクションを返します。 シーケンスの場合、 （）を返します。 まあ、 consメソッドは新しい要素を追加します。

ISeqオブジェクトを取得するために、言語にはseq関数が用意されています。 コレクションが空の場合、 nilが返されます。Seqableオブジェクトがある場合は、 seq（）メソッドが呼び出されます。そうでない場合は、特別なラッパー（アダプター）が作成されます。 ラッパーは、配列、反復子、javaコレクション（ Mapを含む）、およびCharSequenceオブジェクト（文字列）でサポートされています。 あなたのタイプをこのリストに追加することはできません-それはJavaコードに「縫い付け」られています（プロトコルでさえ助けにはなりません）。 もちろん、配列（またはJavaコレクション）のシーケンスを作成する場合は、配列を変更しないでください。 そのため、 ConcurrentModificationExceptionは単純にスローされます。

Clojureには、シーケンスを操作するための3つの基本機能しかありません。

• first-シーケンスの最初の要素を取得します。空の場合はnil 。
• 休息 -「尾」を取得、すなわち 最初の要素のないシーケンス。
• cons-新しい不変のコンスセルを作成します。

consの代わりに、 consの代わりにconj関数が通常使用されます。 2つの違いは、1つ目は常に単純に接続されたリストに新しいセルを作成しますが、2つ目の結果はコレクションの特定のタイプごとに固有であるということです。アイテムは最適な場所に追加されます。 コンスセルの場合、これはリストの始まりであり、ベクトルの場合は終わりであり、セットの場合、順序はまったく定義されていません。 コレクションにseqを適用すると、そのタイプに関する情報が失われることに注意することが重要です。

 (conj [1 2 3] 4) ;=> [1 2 3 4] (conj (seq [1 2 3]) 4) ;=> '(4 1 2 3) 

残念ながら、Javaインターフェースのメソッドの名前と関数の名前は必ずしも一致しません。conj関数はconsメソッドに対応し、 残りはmoreメソッドに対応します。 一方、メソッドの名前を知る必要があるのは、コレクションを作成するときだけであり、この職業は普通に起因することはほとんどありません。

すべての標準関数は、自動的にseqを呼び出します 。 たとえば、 （cons 1 [2 3]）と書くと、作成されたcons-cellは実際にはベクトル[1 2]自体ではなく、結果（seq [1 2]）を参照します。 同じトリックが他の関数（マップ、フィルターなど）の作業中に実行されます-それらはすべてシーケンスで機能しますが、コレクションはパラメーターとして受け入れます。

実際、リストとコンスセルのみがISeqを直接実装します ：

 (seq? '(1 2)) ;=> true (seq? ()) ;=> true (seq? (cons 1 nil)) ;=> true (seq? (cons 1 [2 3])) ;=> true (seq? [1 2]) ;=> false (seq? {:a :b}) ;=> false (seq? #{1 2}) ;=> false (seq? nil) ;=> false 

したがって、リストの反復中に、一時オブジェクトは作成されません。 しかし、ベクトルを調べると、各要素に対して1つの一時ISeqインスタンスが作成されます。 実際、バージョン1.1からは少し異なりますが、それについては以下で詳しく説明します。

また、「誰も知らない」インターフェースclojure.lang.IndexedSeqがあり 、配列と文字列のシーケンスがそれを実装します。 index（）メソッドを定義して、現在の要素の番号を取得します（つまり、元のコレクションの頭です）。

 (.index (rest (to-array [1 2 3 4]))) ;=> 1 (.index (rest (rest (to-array [1 2 3 4]))) ;=> 2 

実際には、このインターフェイスはどこでも使用されていません（文書化されていない機能）。 しかし、アプリケーションを思い付くのは本当に難しいです。 ちなみに、 clojure.lang.APersistenVector $ Seqオブジェクトも実装しています。 しかし、ここでの問題は、ベクターのseqがclojure.lang.PersistentVector $ ChunkedSeqのインスタンスを返すようになったことです。

遅延シーケンス

Clojureのシーケンスの重要な機能は、潜在的な遅延です。 これは、現時点ではシーケンス全体が構築されておらず、その「テール」がまだ作成されていないことを意味します。 Clojureでは、これはI / Oのストリーミングによく使用されます。

怠azineは非常に簡単に実現されます。 clojure.lang.LazySeqクラスがあります（もちろんISeqを実装しています ）。 このクラスのオブジェクトには、関数（ IFnインスタンス）への参照があります。この関数を呼び出すと、新しいシーケンス自体が返されるはずです（ほとんどの場合、レイジーですが、必要ではありません）。 LazySeqメソッドの呼び出しは、生成関数の同期呼び出しを行い、結果が保存され、関数自体へのリンクがリセットされます（ガベージコレクターが処理できるようにするため）。 明らかに、前のものをすべて計算せずに遅延シーケンスの要素を取得する方法はありません。 この動作だけが必要な場合は、 遅延マクロを使用できます。

 (nth (map #(print % "") (iterate inc 0)) 5) ;=> 1 2 3 4 5 @(nth (map #(delay (print % "")) (iterate inc 0)) 5) ;=> 5 

コードで遅延シーケンスを生成するのはとてつもなく簡単です。 consを呼び出すコードをlazy-seqマクロ内に配置するだけで十分です。 しかし、実際には、これを最も頻繁に行う必要さえありません。ほとんどの標準関数（例外はほとんどありません）が遅延コレクションを返し、すべての「汚い」作業を行います。 ここには真実と微妙なニュアンスがあります。

そのため、その計算では、レイジーシーケンスは実際には単純で単純に接続されたリストに変わります。最初の要素へのリンクを保存すると、メモリの問題が発生する可能性があります。 古典的な例：

 (def all-odds (filter odd? (range))) (println (nth all-odds 20000000)) 

ここでは、20,000,000番目の奇数を見つけようとしています。 そして、それを見つけますが、それはすべての中間ISeqインスタンスがメモリに残っているだけです。 正しい決定：

 (defn make-all-odds [] (filter odd? (range))) (println (nth (make-all-odds) 2000000)) 

rest関数は決してnilを返さず、代わりに空のシーケンスを返すことができます。 nilを取得したい場合は、 nextを使用します。

 (first '(1 2 3)) ;=> 1 (rest '(1 2 3)) ;=> '(2 3) (rest '(1)) ;=> () (rest ()) ;=> () (next '(1)) ;=> nil (next ()) ;=> nil 

これは怠greaterを大きくするために行われます。 実際、シーケンスが遅延している場合、一般的なケースでは、シーケンス内にさらに要素があるかどうかはわかりません。 nextでこの事実を検証するには、少なくとも最初の2つの要素を計算する必要があります。最初の要素を破棄し、2番目の要素が存在することで、 nilを返すかどうかを理解します。 さて、2つの要素の計算-これは明らかに私たちが通常必要とするものではありません。

遅延動作が必要ない場合、 dorunおよびdoall関数を使用してシーケンス全体を完全に計算できます。 最初は元のシーケンス、2番目はnilを返します。

 (dorun (map #(println % "") (range 5)));=> 1 2 3 4 5 

ブロックシーケンス

遅延コレクションは非常に強力なツールですが、実際にはコレクション全体を処理することが多く、 遅延シーケンスは具体的なオーバーヘッドをもたらします。 したがって、バージョン1.1では、重要な最適化が行われました-チャンク化されたシーケンス。 結論は簡単です-遅延シーケンスを処理するとき、個々の要素ではなく、それらのグループを扱います。 同時に、多くの「成長」要素が貪欲に計算されます。

このコードが出力するものを推測しますか？

 (first (map #(print % "") (range 100))) 

そのため、Clojureは特別なインターフェースclojure.lang.IChunkedSeqを定義しています。 このメカニズムのJava部分を説明する意味はあまりないので、ここでは省略します。 ベクターのシーケンスのみがインターフェースを実装します。 さて、そして、私たちが見たように、 範囲関数の結果。

そのようなシーケンスを処理するためのアルゴリズム：

• ソースがIChunkedSeq （ chunked-seq function ？ ） かどうかを確認します。
• そうでない場合は、通常のバージョンのアルゴリズムを実行します（ビット処理）。
• その場合、シーケンスから最初のブロックを取得します（ チャンクファースト関数）。
• そのサイズを見る（ チャンクサイズ関数）;
• 新しいブロックを作成し、生成された要素をそこに配置します（ チャンクバッファ機能）。
• 実際に有用な作業を行い、要素をブロックに追加します （ チャンク付加機能）。
• ChunkedCons（関数chunk-cons ）で新しいブロックをラップします。

例として、実装を記述します＃（奇数フィルター？％）。 簡単なオプション：

 (defn filter-odd-1 [a] (lazy-seq (when-let [s (seq a)] (let [f (first s) r (rest s)] (if (odd? f) (cons f (filter-odd-1 r)) (filter-odd-1 r)))))) 

詳細オプション（ブロックサポート付き）：

 (defn filter-odd-2 [a] (lazy-seq (when-let [s (seq a)] (if (chunked-seq? s) (let [f (chunk-first s) c (count f) b (chunk-buffer c)] (dotimes [ic] (let [x (nth fi)] (when (odd? x) (chunk-append bx)))) (chunk-cons (chunk b) (filter-odd-2 (chunk-rest s)))) (let [f (first s) r (rest s)] (if (odd? f) (cons f (filter-odd-2 r)) (filter-odd-2 r))))))) 

もちろん、もう少しコードがあり、明らかな重複がありました。2つの別個の実装を作成する必要がありました。 しかし、これは速度の代価です。 幸いなことに、ほとんどの標準機能はすでにチャンクを完全にサポートしています。 シーケンスはさまざまな長さのブロックで構成でき（ブロックは互いにくっつかないが、上の例のようにカットされることもある）、通常の要素とブロックの混合でさえあることに注意する。

通常のシーケンスをブロックシーケンスに変換する場合はどうなりますか？ vec関数を使用してベクトルに変換するだけです。 逆はすでにもう少し複雑です：

 (defn seq1 [s] (lazy-seq (when-let [x (seq s)] (cons (first x) (seq1 (rest x)))))) (first (map println (seq1 (range 1000)))) ;=> 1 

また、 reduce関数がブロックシーケンスを利用することも期待されます。 そのため、各ブロックには、一時オブジェクトを作成せずにJavaサイクルで畳み込みを実行する特別なメソッドがあります。 一般的に、 reduceには他の最適化もあり、興味のある人は誰でもclojure.core.protocolsを見ることができます。

結論の代わりに

Clojureシーケンスは強力で便利です。 彼らの疑いのないプラスは、怠suchやブロック処理などの「些細なこと」について考えることさえできないことが多いということです。Clojureはそれを私たちのために試みます。