4

Haskell で使用する二重接続エッジ リスト データ構造を実装したいと思います。このデータ構造は、平面内の線の配置のトポロジを管理するために使用され、面、エッジ、および頂点の構造が含まれています。

このデータ構造への優れたインターフェースは、次のArrangementような関数を備えた type としてのように思えます

overlay :: Arrangement -> Arrangement -> Arrangement

ただし、通常の実装は参照に大きく依存しています (たとえば、各面には隣接するエッジへの参照があります)。

これが機能する理想的な方法は、可変および不変の配列が行う方法に似ているように思えます。データ構造の内部はArrangement機能的なデータ構造として実装されますが、配置を変更する操作はそれらを「解凍」して新しいものを作成しますモナド内の変更可能なインスタンス (理想的には COW マジックを使用して物事を効率化します)。

だから私の質問は：

(1) 配列の場合のように、小さなヒープをフリーズおよびアンフリーズする方法はありますか? （2）そうでない場合、より良いアプローチはありますか？

4

2 に答える 2

0

安全なバージョンのfreezeとthawが配列の完全なコピーを作成するわけではないため、必ずしも効率的ではありません。もちろん、ref の配列の完全なコピーを作成することは、間違いなく、構造体の完全なコピーを作成することよりも最適化であり、構造体をウォークし、再帰的にものをMVars から取り出します。

Repa取るべき別のアプローチは、構造に対する操作を代数的に表現し、run最適化、融合、およびすべてを 1 つのパスで実行する関数を作成するのと似たものです。より機能的なデザインと言えるでしょう。(具体化を明示的ではなくオンデマンドで行うために、安全でない操作を内部で使用することもできます)。

于 2013-02-05T16:20:34.330 に答える