Cofreeは私たちを引き裂きます

みなさんこんにちは。

最近、私は分散システムで作業しており、データの処理で問題に遭遇することがよくあります。データの一部は異なる場所に配置できます。 さて、私はHaskellで長い間書いているので、問題の説明と強力な型システムは、このアイデアをさらに発展させるのに大いに役立ちました。 代数的構築をサポートするたった1つが、一般的な方法でデータのリサイクルの問題を解決することを可能にした方法についてです。

紹介と動機

ストーリーの過程で、望ましい結果のアイデアを与える3つの主要なポイントに会います。

ある種のデータを扱うプログラムを書く必要があると想像してください。 データが多すぎる場合は、整理と保存について考える必要があります-RAMに保存するのは信頼性が低いため、十分なスペースがないか、プログラムのクラッシュ中に完全に失われます。

データベースを使用しますか？ どれ？ リレーショナル、ドキュメント指向、キーバリューストレージ、またはもっとシンプルなもの-ファイルに書き込むだけですか？ さて、これらのオプションにはそれぞれ長所と短所があります。

それらを保存する場所はどこでも、選択したメソッドの機能を超えてこのデータで何かをするために、いずれにしても、それらをRAMにロードする必要があります。 もちろん、上記の理由により、すべてが連続しているわけではなく、一部のみです。

論文1.すべてのデータをメモリに保存する必要はなく、一部のみを保存する必要があります。

実際、データベースを操作するとき、クエリを作成して、このデータをメモリで受信できます。 データベース内のレコードは、情報の配列全体の一部にすぎません。 リレーショナルのものの場合、これらはテーブル内のレコードです。 キーと値のストレージの場合、キーと値のペア。

現実世界のアプリケーションを作成する場合、選択した方法の制限に合わせて、サブジェクト領域のデータの編成を調整する必要があります。 これは、接続の程度、パフォーマンスの側面、および他の多くの要因に依存します。

論文2.情報が保存され処理される方法を無視したい。

前述の2つのプロパティに基づいて、現在作業中のデータと、実際にメインメモリにあるデータと、ハードドライブのどこかに格納されているデータを分離する方法が必要です。 それらを分離する方法が必要です。

それらをどのように分離しますか？ データをシームレスに共有および結合できる構造が必要です。 このトピックを振り返りましょうか？

• リスト？ 可能ですが、問題があります。 任意の要素にアクセスするコストはO（n）です。 2つのリストを結合するコストは同じです。
• 木はありますか？ バイナリの場合、適切な場合のアクセスのコストはO（log n）に削減されます。 ただし、ソートされたデータを常に保存する必要はありません。 あまりにも特別な場合、私たちには合いません。
• 配列？ アクセスコスト-O（1）。 しかし、特別な場合でも、他の問題に直面するだけです-この構造は一般に代数的ではありません。

論文3.私たちは、その説明で他の多くのデータ構造をカバーできるサポート構造が必要です。

そして、そのような構造があります！

コフリー耐荷重構造

多くのHaskellプログラマーはFree型に精通しています。 しかし、何らかの理由で、彼の二重性Cofreeはあまり注目されていません。 そして、それらの違いは1つの詳細です。 Freeタイプはとt (Free ta)の合計であり Cofreeは製品です。

 Free ta = a + t (Free ta) Cofree ta = a × t (Cofree ta) 

つまり、サポート構造としてCofreeを選択した場合、後者を介して定義されたデータ構造にはいくつかの機能があります。

• この構造は常に空ではなく、常に少なくとも1つの要素があります。
• CofreeにはComonad型クラスのインスタンスもあるため、すでに多くの便利なメソッドが無料で用意されています。
  
  • extractフォーカスされている値を取得します。
  • extendコンテキストに応じて構造全体の値を更新します。
  • unwrap -製品の乗数、情報セグメントを取得します。
  • coiter初期値から構造を生成します。

それでは、Cofreeを使用してさまざまなデータ構造をどのように収集するのでしょうか？ 必要なのは、 Functor型クラスのインスタンスを持つCofree ta型tをインスタンス化することだけです。

スタックまたは空でないリスト、つまり単純なデータ構造が必要だと想像してください。 Maybe私たちに適しているMaybeん。この場合、後者の設計者はジェネレータとして機能します-構造を記述し続けることができますが、終了する不変式はありません：

 data Maybe a = Just a | Nothing type Stack = Cofree Maybe example :: Stack Int example = 1 :< Just (2 :< Just (3 :< Nothing)) 

補助形状設計

さて、 Cofreeデータ構造を記述する方法をCofree 。 この会話は、さまざまな場所にある型の観点からデータを分離する方法を見つけるために始まりました。 これを行うために、 Cofreeに別のデザインを提供します。

 data Shape t raw value = Ready (t value) -- ^      | Converted raw -- ^ C  -    data Apart t raw value = Apart (Cofree (Shape t raw) value) 

そして、データの量を制御する素晴らしいApartタイプを取得します。

別の例

さて、図解された例を作りましょう。 バイナリツリーを使用したいと想像してください。 Cofreeどのように説明できますか？ 「分岐ファンクター」を通じて。 ツリーノードには、子孫がない、左子孫、右子孫、またはその両方がある場合があります。 このようにコーディングしましょう：

 data Crotch a = End | Less a | Greater a | Crotch aa type Binary = Cofree Crotch 

さて、これでこの型の値を書くことができます。同じ名前のウィキペディアの記事からバイナリ検索ツリーの例を見てみましょう。

 example :: Binary Int example = 8 :< Crotch (3:< Crotch (1 :< End) (6 :< Crotch (4 :< End) (7 :< End))) (10 :< Greater (14 :< Less (13 :< End))) 

最初のコンビネータ-limitをテストします。これにより、ツリーの高さをトリミングできます。

 limit 3 do_something_with_the_rest example 

これに焦点を当てないように、保存方法を意図的に無視しました-ファイル内の範囲にないセグメントを保存でき、 do_something_with_rest関数はファイル名と行番号を返すことができます。 または、 Redis / Memcashed / Tarantool入れて、保存されたセグメントの接続パラメーターとキーを返します。 一般的に、それほど重要ではありません。

 scattered :: Scattered Binary Int _ scattered = 8 :< Crotch (3 :< Crotch (1 :< {RESTORE_INFO}) (6 :< {RESTORE_INFO})) (10 :< Greater (14 :< {RESTORE_INFO})) 

そして、ここに私たちの木の残りがあります-それは高さがトリミングされました。 しかし、回復のための情報は、消失した3つのセグメントの代わりに残りました。 上記のビューは実際にReadyコンストラクターを非表示にし、 Converted中括弧に置き換えられます（ Showクラスのトリッキーなインスタンスのおかげです）。

recoverコンビネータを使用して、データ構造全体をメモリに戻すことができます。

 recover back_to_RAM scattered 

または、散在するデータ構造に沿ってエフェクトを歩いて、途中でメモリ内のセグメントを復元し、メモリ内の値と同じ機能をそれらに適用します。

 fluent do_something_whereever_they_are scattered 

結論として

これが、カテゴリー理論の代数的データ構造と概念により、最も一般的な形式でリサイクルされたデータの問題を最初に記述し、解決することを可能にした方法です。

上記のアイデアは、まだHackage上にないライブラリに実装されましたが、積極的な開発の段階にあります。

現時点では、有向非巡回グラフ、バイナリ、プレフィックス、ピンク、AVLツリー、およびそれらを操作するためのいくつかの個別の関数を説明できました。

他のデータ構造のサポート構造としてCofreeを使用するというまさにその考えは、Edward KmettによるfreeパッケージのControl.Comonad.Cofreeモジュールの説明から得られました。

グラフの代数的記述のアイデアは、 Andrei Mokhovの研究からここで使用されました。

計画も残っています。

• フィンガータイプ、スプレイツリー、およびその他の構造の実装はより複雑です。
• それらを操作するための関数をさらに作成します（挿入、削除、バランスなど）。
• それらの間の自然な変換（ファンクターは別個の構造の特徴を決定するだけなので）。
• 内部構造を操作するための光インターフェース。
• コンビネータがストリーミングライブラリ（ pipes 、 conduit 、 io-streams 、 machines ）とどのように互換性があるかを学びます。
• 個々のデータ構造のプロパティの完全なテストを記述します。
• ベンチマーク、主に人気のあるcontainers 。

この方法でどのデータ構造を使用し、どのコンビネータが日常業務に役立つかをコメントに記入してください。 コメントや批判を歓迎します。

ご清聴ありがとうございました。