I've stumbled upon something that I'm guessing is a bug in Data.Map
, but which is also quite possibly a bug in my Haskell knowledge. Hoping somebody can clarify which it is :)
Please reference this gist. I'm serializing a circular linked list structure to a bytestream. For any given node, of the form:
data Node = Node
{ val :: Word8
, next :: Node
}
I expect it to be serialized as a pair of bytes: the first byte representing val
, and the second byte representing the offset in the bytestream where next
can be located. For example, I expect:
let n0 = Node 0 n1
n1 = Node 1 n0
to be serialized as [0, 1, 1, 0]
. No big deal.
The slightly tricky part here is that I'm exploiting the MonadFix
instance for RWST
to "tie the knot" of bytestream offsets: I maintain a map from nodes to offsets, populating the map during serialization, but also referencing entries in the map that don't necessarily exist yet until serialization is complete.
This works great when the map implementation is Data.HashMap.Lazy
(from unordered-containers). However, when the implementation is the usual Data.Map
(from containers), the program stack overflows -- no pun intended -- with Map
trying infinitely to compare the two nodes using (==)
.
So my question is: is this a bug in Data.Map
, or are my assumptions about how these structures should behave in the presence of mfix
flawed?
Data.HashMap.Strict
also works fine. – Tradein