haskell - 重複のないリストまたは順序付けられたセット

Question

アイテムの順序を保持し、重複を含まないデータ構造を提供するライブラリはありますか? そして、そのようなデータ構造の適切な名前は存在しますか?

nub各操作の後に適用されるリストのように動作することを期待しています。もちろん、それが効果のないものとして実装されるとは思っていません。

Answer 1

ここに1つの解決策があります：

モノイドを尺度としてフィンガーツリーを使用します。Set次に、挿入時にmeasure、完全なフィンガーツリーの を使用して、最初にメンバーシップを確認します。これにより、O(log(n))cons と snoc、deleteが得られますO(1)。

別の解決策は次のとおりです。

法線リストと法線をペアにするSetと、基本的に同じ効果が得られます。より良い定数係数が得られますが、O(log(n))削除されます。

ここに質問があります: 複製の挿入で何が起こりたいですか? 既存の位置を保持する必要がありますか? 新しいポジション？プライオリティ キューは、希望するものに近い場合があります。

Answer 2

OSetfromordered-containersはあなたが望むことをするようです。