定義済みのキー順を持つ辞書型

Question

aのキーをbの値にマッピングして、辞書として機能する対の単純なリスト[(a,b)]のような振る舞いをするタイプを使用したいと思います。指定されたキーの順序。 （つまり、通常のリストと同じように、「最後の要素」として認識されるアイテムを「追加」できるようにしたいと思っています）。しかし、線形のパフォーマンスよりも優れたキー、つまり何のためのランダムアクセスルックアップを希望しますか？Data.Map提供します。同期中に二つの重要なコレクションを保つことなど、

data OrderedDict a b = OrderedDict (Map a b) [a] 

、その後append操作を定義：1つのオプションは、ちょうど彼らの順序を定義するキーのリストに加えて、通常のマップを維持するだろう。同じキーの2つの別々のコレクションを維持することは醜いようです。キーによる効率的なランダムアクセスルックアップを備えた順序付けされたキーを既に組み合わせた既製のデータ型はありますか？

Answer 1

あなたの質問を完全に誤解しない限り、Data.MapはキータイプのOrdインスタンスを使用して注文します。これはバイナリツリーなので、実装ではキーの順序も保持されます。

Data.Map.keysは、マップのキーを昇順で表示します。 mapなどの変換は純粋に機能的であり、トラバーサルの順序は無関係であり、キーまたはキー/値のペアのシーケンスをマップから取得するすべての方法で、順序付きリストが得られます。あなただけのOを持っていることのほかに、いくつか固定ため（例えば挿入時間）を保持したい場合は

Answer 2

あなたは、単に複数のマップを使用することができ、検索/挿入（Nを記録）し、それらを同時に更新：

1. 実際のデータを格納するためのMap a bと、順番にi番目のキーを与える
2. Map Int aがあります。 （あなたも、あなたがMap a Intを追加することができ、特定のキーのインデックスを照会する必要がある場合）

Answer 3

はixsetライブラリを見てください - それは（aで、あなたの内Intによって複数の列でインデックス化セットを維持することができます場合）。これは、手作業でマップを一貫性を保つよりもはるかに保守的です。