ハスケープヒープとdeepseqライブラリの互換性

Question

現在、ハックの使用deepseqからヒープ1.0.0パッケージを使用して計算を完全に厳密に評価するいくつかのコードを作成しようとしています。

deepseqを使用するには、より大きな式に関連する型のNFDataインスタンスを宣言する必要があることがわかりました。これまでのすべての良い。それから、私はData.Heapに行き、いくつかの項目の優先順位キューを保持するために使用します。突然良くない。

本質的に、私が知る限り、ヒープのデータコンストラクタは隠されており、NFDataインスタンスはヒープライブラリ自体の内部で宣言されていないため、deepseqとヒープを一緒に使用することはできません。

私の理解は正しいですか？これらのライブラリを連携させて相互運用させる方法はありますか？

ありがとうございます！

Answer 1

instance NFData Heap where 
     rnf x = rnf (toUnsortedList x) `seq`() 

は、最も効率的な、しかし、その後、ウィリーnillyすべてをrnfingは、通常、ヒープをdeepseqする必要はありません:-)

Answer 2

ではありません。あなただけの通常のseqを使用する場合はHeapTタイプは

data HeapT prio val 
    = Empty --^An empty 'HeapT'. 
    | Tree { _rank  :: {-# UNPACK #-} !Int --^Rank of the leftist heap. 
      , _size  :: {-# UNPACK #-} !Int --^Number of elements in the heap. 
      , _priority :: !prio    --^Priority of the entry. 
      , _value :: val     --^Value of the entry. 
      , _left  :: !(HeapT prio val) --^Left subtree. 
      , _right :: !(HeapT prio val) --^Right subtree. 
      } --^A tree node of a non-empty 'HeapT'. 
    deriving (Typeable) 

として定義され、それが弱いヘッド正規形、すなわちいずれかEmptyまたはTreeコンストラクタにヒープを評価します。サイズフィールドは厳密なので、ヒープの背骨を完全に評価します。

これを入力するときに新しい項目をdeepseqと組み合わせると、ヒープが完全に評価されます。

let insert' item heap = item `deepseq` Data.Heap.insert item heap 

let newheap = insert' item heap 
in newheap `seq` do_something_else 

これは、パフォーマンスが悪化する場合は驚くことではありません。ヒープパッケージは岡崎の実装を使用しているため、特定のパフォーマンス保証のために怠惰に依存しています。それを試してみてください。