要素を交換するのに有効なHaskellのデータ構造ですか？

私は、要素の順序付きリストを格納するHaskellデータ構造を探しています。これは、リスト内の任意の場所にある要素のペアをスワップする際に時間効率が良いことです。明らかに、[a]ではありません。スワップは新しいベクトルを作成するので、Vectorではありません。どのデータ構造が効率的ですか？要素を交換するのに有効なHaskellのデータ構造ですか？

出典

2015-10-04 Ana

を[A]要素操作で非常に効率的であるリンクリストです。問題が効率的なインデックス作成である場合、ソリューションは実際のユースケースに依存します。おそらく[ジッパー]（https://wiki.haskell.org/Zipper）が役立ちますか？ –

['Data.Vector.Mutable']（https://hackage.haskell.org/package/vector-0.11.0.0/docs/Data-Vector-Mutable.html）について質問していますか？ – Bakuriu

また、[Ropes]（https://en.wikipedia.org/wiki/Rope_%28data_structure%29） –

ハスケルは（ほとんど）純粋な関数型言語なので、更新するデータ構造は構造体の新しいコピーを作る必要があり、データ要素を再利用することはできる限り最善の方法です。また、新しいリストは遅れて評価され、データが必要になるまで通常は背骨だけを作成する必要があります。要素数に比べて更新回数が少ない場合は、最初に疎な一連の更新を確認し、元のベクトルのみを調べる差分リストを作成することができます。

出典

2015-10-04 06:03:07 Davislor

Data.Sequencecontainersパッケージは、このユースケースではじまる恐ろしいデータ構造ではないでしょう。

出典

2015-10-04 06:56:44 lpsmith

O（1）アップデート（追加、プリペア、カウント、スライシング）を示す永続データ構造の最も効率的な実装は、Array Mapped Trieアルゴリズムに基づいています。 ClojureとScalaのVectorデータ構造は、例えばそれに基づいています。私が知っているそのデータ構造の唯一のHaskellの実装は、the "persistent-vector" packageです。

このアルゴリズムは非常に若く、2000年に初めて発表されたばかりであり、多くの人がそれを聞いたことがない理由です。しかし、このことはまもなくハッシュテーブルに適応された普遍的な解決策であることが判明しました。このアルゴリズムの適合バージョンは、ハッシュ・アレイ・マッピング・トライと呼ばれる。これは、ClojureとScalaでSetとMapのデータ構造を実装するためにも使用されています。また、Haskellでは、"unordered-containers"と"stm-containers"のようなパッケージを使って、より遍在しています。

私は、以下のリンクをお勧めアルゴリズムについて詳しく知ることができます。

出典

2015-10-04 08:00:01

私は木の高さに関する但し書きであっても、更新はO（1）しかかかりません。それはかなり良いです。あなたの答えにいくつかの複雑さの範囲を言及したいかもしれません。 – chi

Edward Kmettは、いくつかの同様の構造に取り組んでいます。彼がリリースにどれほど近づいているかわからない。 – dfeuer

要素を交換するのに有効なHaskellのデータ構造ですか？

答えて

関連する問題