Data.Map實現中的錯誤？

Question

我在說我猜測是Data.Map錯誤的東西絆倒了，但也很可能在我的Haskell知識的錯誤。希望有人能澄清這是:)

請參考this gist。我將一個循環鏈表結構序列化爲一個字節流。對於任何給定節點，該形式爲：

data Node = Node 
    { val :: Word8 
    , next :: Node 
    } 

我希望它被序列化爲一對字節：表示val第一字節，並且表示在next可以位於字節流的偏移的第二個字節。例如，我期望：

let n0 = Node 0 n1 
    n1 = Node 1 n0 

被序列化爲[0, 1, 1, 0]。沒什麼大不了。

這裏稍微棘手的部分是我在剝削MonadFix實例RWST爲「永結同心」的字節流偏移：我保持與節點偏移量的圖，序列化過程中填充的地圖，但還引用條目在序列化完成之前不一定存在的映射。

這個偉大的工程圖時實現Data.HashMap.Lazy（從）。然而，當執行是通常的Data.Map（從containers），程序堆棧溢出 - 沒有雙關語意 - 與Map試圖無限使用(==)兩個節點進行比較。

所以我的問題是：這是Data.Map一個錯誤，或者是我對這些結構應該如何表現在mfix存在缺陷的假設？

Answer 1

你Ord情況下不工作：

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

有關工作Ord實例，你必須定義compare或(<=)。如果只定義(<)，任何調用compare或(<=)將無限循環，因爲兩者在彼此而言的默認實現。另外Ord的其他成員是根據compare定義的，所以除了(<)之外沒有其他成員可以使用。