haskell - Haskellでポインタをエミュレートするにはどうすればよいですか?

Question

Haskell で Dijkstra のアルゴリズムを実装しようとしています。ツリーを使用してバイナリ ヒープを既に実装しています。アルゴリズムでは、現在の頂点の隣接キーをヒープで更新する必要があります。Haskellのヒープ内の値へのポインタをエミュレートするにはどうすればよいですか? 各操作の後にヒープが変更されているときに、ヒープ内の要素にすばやくアクセスするにはどうすればよいですか?

Answer 1

変更可能な参照へのアクセスを提供するパッケージData.IORefおよびData.STRefを確認してください。IO も実行する必要がある場合は IORefs を使用し、そうでない場合は STRefs を使用します。

しかし、私の疑いは、おそらくあなたが間違ったことをしているということです。可変状態なしでダイクストラのアルゴリズムを実装することは完全に可能です (ただし、キャッシュできる関数評価を継続的に再計算している場合、漸近的な実行時間が簡単に爆発する可能性があるため、少し注意する必要があります)。

Answer 2

おそらくvectorパッケージからData.Vector.Mutableを探しており、これをSTまたは IO モナドと組み合わせたいと思うかもしれません。

Answer 3

調整操作をサポートするData.FingerTree.PSQueueを使用して、ヒープを更新できます。この場合、キーを介して値を更新するため、ヒープ内の値へのポインターは必要ありません。