algorithm - 関数型言語 (Haskell) の高速要素検索

Question

グラフをトラバースしていて、ノードが以前に見られたかどうかをすばやく判断したいとします。いくつかの前提条件が設定されています。

1. ノードは整数値 1..N でマークされています
2. グラフは、隣接リストを持つノードで実装されます
3. 1..N のすべての整数値がグラフに出現し、サイズは N です。

純粋に機能的な方法でこれを行うためのアイデアはありますか?(ハッシュテーブルまたは配列は許可されていません)。

2 つの関数が動作するデータ構造が必要です。add (遭遇した整数を追加) および lookup (整数が追加されたかどうかをチェック)。どちらも、N回の繰り返しで償却されるO(n)時間かかることが望ましいです。

これは可能ですか？

Answer 1

Data.Setを使用できます。古いセットから新しいセットを作成して要素を追加し、新しいセットinsertを渡します。要素がセットのメンバーであるかどうかを調べるには、 を使用しmemberます。どちらの演算も O(log n) です。

おそらく、状態モナドを使用してセットの受け渡しをスレッド化することを検討できます。

Answer 2

関数型言語での効率的な要素検索は非常に困難です。Data.Set(上記のように) は、O(log n) でルックアップ操作を提供する純粋に機能的な方法で構築できるバイナリ ツリーを使用して実装されます。HashTables (純粋に機能的ではない) には O(1) があります。

Answer 3

Data.BitSet は O(n) かもしれないと思います。

Answer 4

コードを IO モナドにラップすることを気にしない場合は、judy hashtablesを見てください。