Bug in Data.Map implementation?
Asked Answered
T

1

16

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?

Tradein answered 24/6, 2012 at 19:28 Comment(3)
@RomanCheplyaka this takes the place of my previous horrible post, which I've deleted. You asked to see the code in full, so here you go :)Tradein
Also, I just discovered (to my surprise) that Data.HashMap.Strict also works fine.Tradein
and now you see exactly why I asked to see the code ;)Roxannroxanna
G
23

Your Ord instance doesn't work:

instance Ord Node where -- for use in Data.Map
  Node a _ < Node b _ = a < b

For a working Ord instance, you must define compare or (<=). If you only define (<), any call to compare or (<=) will loop infinitely since both have default implementations in terms of each other. Also the other members of Ord are defined in terms of compare, so nothing except (<) will work.

Godless answered 24/6, 2012 at 19:48 Comment(4)
Damn it, I'm an idiot. I just realized that myself. Good thing I have no problem making an ass of myself on the internet.Tradein
@Tradein There is no shame in that! If you are not embarrassing yourself you are not learning!Lathan
@GabrielGonzalez Amen to that. I teach for a living, and I often tell my students the same thing :)Tradein
@Tradein it's so hard to apply the word one teaches to oneself - I teach too.Dispose

© 2022 - 2024 — McMap. All rights reserved.