Compatability of Haskell heap and deepseq library

I'm currently trying to make some code that uses the heap-1.0.0 package from hackage use deepseq to ensure that a calculation is fully strictly evaluated.

I've found that to use deepseq I need to declare NFData instances for the types involved in the larger expression. All good so far. Then I get to the Data.Heap that I use to hold a priority开发者_StackOverflow社区 queue of some items. Suddenly not so good.

Essentially, as far as I can tell, I can't make deepseq and heap work together because the data constructors for heap are hidden away, and NFData instances are not declared inside the heap library itself.

Is my understanding correct? Are there any known ways of making these libraries work together and interoperate?

Thanks in advance!

There's no need to deepseq a heap. The HeapT type is defined as

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)

If you just use a normal seq, it will evaluate a Heap to weak-head normal form, i.e. either the Empty or Tree constructor. Since the size field is strict, this will fully evaluate the spine of the heap.

If you combine this with deepseqing new items as you enter them, the heap will be fully evaluated.

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

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

That being said, I wouldn't be surprised if this leads to worse performance. Since the heap package uses Okasaki's implementation, it relies on laziness for certain performance guarantees. Try it and see.

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

Not the most efficient, but then rnfing everything willy nilly usually isn't :-)