algorithm - 純粋関数型セット

Question

純粋に機能的なセットを実装するアルゴリズムはありますか？

期待される操作は、和集合、共通部分、差、要素ですか？、空？と隣接します。

ただし、これらは難しい要件ではありません。それらのサブセットのみを実装するアルゴリズムを学習できれば幸いです。

score 5 · Accepted Answer

値を無視するだけの純粋関数型マップの実装を使用できます。

（補足：機能データ構造の詳細については、http：//www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504を参照してください）

score 3 · Accepted Answer

ほぼすべてのデータ構造に対して、純粋に機能的な実装が存在します。セットまたはマップの場合、通常、赤/黒ツリーや AVL ツリーなど、何らかの形式の検索ツリーを使用します。関数型データ構造の標準的なリファレンスは、岡崎の本です。

その重要な部分は、彼の論文から無料で入手できます。

score 1 · Accepted Answer

純粋に機能的なセットを実装するアルゴリズムはありますか?

さまざまな純粋関数データ構造を使用して集合演算を実装できます。いくつかは他のものよりも複雑です。

例は次のとおりです。

私たちが持っている場所：

List Difference:

(\\) :: Eq a => [a] -> [a] -> [a]

\\関数は list difference ((non-associative) です。の結果では、xs \\ ysys の各要素の最初の出現 (存在する場合) が xs から削除されています。したがって、

union :: Eq a => [a] -> [a] -> [a]

union 関数は、2 つのリストの和集合を返します。例えば、

"dog" `union` "cow" == "dogcw"

重複、および最初のリストの要素は 2 番目のリストから削除されますが、最初のリストに重複が含まれている場合は結果も削除されます。これは、unionBy の特殊なケースであり、プログラマが独自の等価性テストを提供できるようにします。

intersect :: Eq a => [a] -> [a] -> [a]

intersect 関数は、2 つのリストのリスト共通部分を取ります。例えば、

[1,2,3,4] `intersect` [2,4,6,8] == [2,4]

最初のリストに重複が含まれている場合、結果も重複します。

不変セット

集合演算の複雑さを改善するために、より効率的なデータ構造を設計できます。たとえば、Data.SetHaskell の標準ライブラリは、セットをサイズバランスの取れたバイナリツリーとして実装します。

Stephen Adams 著、「Efficient sets: a balancer act」、Journal of Functional Programming 3(4):553-562、1993 年 10 月、http ://www.swiss.ai.mit.edu/~adams/BB/ 。

このデータ構造はどれですか:

data Set a    = Bin !Size !a !(Set a) !(Set a)
              | Tip

type Size     = Int

生成する複雑さ:

score 1 · Accepted Answer

@ninjagecko による回答からのリンクは良好です。私が最近注目しているのは、Clojure で使用される永続データ構造です。これは、機能的で、不変で、永続的です。

永続的なハッシュマップの実装の説明は、次の 2 部構成のブログ投稿にあります。

これらは、このリファレンスリクエストの質問にあるいくつかのアイデア (最初の回答、最初のエントリを参照) の実装です。

これらの構造から生じるセットは、必要な機能をサポートします。

score 1 · Accepted Answer

これは、 OCamlでの純粋な関数セットの実装です (OCaml の標準ライブラリです)。

5 に答える 5