28

Haskell で二重にリンクされたリストを持つことは可能ですか?それらを実装するための理想的なソリューションは何ですか? 私は、すべてのウィジェットに子だけでなく親もあるシーン グラフを実装しています。グラフを上下に調べると便利です。

4

3 に答える 3

43

Haskell で二重にリンクされたリストを作成することは、一度に作成する必要があるため、実際には実用的ではありません。

たとえば、[1, 2, 3, 4, 5]二重リンクにしたいリストがあるとします。さて、リストがどのように表現されるか想像してみましょう:

data DoubleList a
  = LeftEnd  a (DoubleList a)
  | Middle   a (DoubleList a) (DoubleList a)
  | RightEnd a (DoubleList a)

(簡単にするために、両端に 2 つの異なるコンストラクターを使用します)

上記のリストを作成するには、まず最初の要素を作成する必要があります。

let e1 = LeftEnd  1 ...

しかし、最初の要素を構築するには、すでに 2 番目の要素が必要です。

let e1 = LeftEnd  1 e2
    e2 = Middle   2 e1 ...

2 番目の要素には、3 番目の要素が必要です。

let e1 = LeftEnd  1 e2
    e2 = Middle   2 e1 e3
    e3 = Middle   3 e2 e4
    e4 = Middle   4 e3 e5
    e5 = RightEnd 5 e4

これは、遅延評価により Haskell で実行できます。この戦略は「結び目を結ぶ」と呼ばれます (そして、文字通りすべてを 1 つのletブロックに入れる必要はありません。構造を関数に分割することができます)。

しかし、言い換えれば、二重連結リストを作成するには、一度にすべてを作成する必要があり、その一部を変更したい場合は、Zipperを使用するか、完全なコピーを作成する必要があります。毎回。

Data.Sequence代わりに、最適化されたフィンガー ツリー ベースのシーケンシャル ストレージの実装である を使用することをお勧めします。純粋に機能的なデータ構造でありながら、非常に高速な挿入、削除、反復をサポートします。

それ以外の場合は、Zippers のみを使用したい場合がありますが、リストではなくツリーに使用します。Zippers の詳細については、Haskell Wikiを参照してください。Zipper は、まさにあなたが求めている機能を提供するため、この状況に非常に適しています: Zipper を使用してツリーにアクセスすると、アクセスしているツリーの部分の「親」にアクセスできます。ただし、ツリー自体に親参照が含まれている必要はありません。

于 2012-04-30T16:03:03.170 に答える
1

Haskell には (通常) OO スタイルのオブジェクトがないため、データが自己認識していると考えるのは奇妙です。通常、Haskell データ型では集計を使用せず、代わりに合成を優先することに注意することが重要です。

XMonadを調べて、その設計がニーズに合っているかどうかを確認することをお勧めします (コードは驚くほど読みやすいです)。

また、上を見る必要がないように設計を再構築することもできます (たとえば、子に「コールバック」を渡すことによって)。

グラフ全体のジッパーを記述できるかどうかも確認したい場合があります。

于 2012-05-10T03:35:47.043 に答える