Data.Map实现中的错误？

Question

我一直在说我的东西绊倒猜测是一个错误Data.Map,但也很可能在我的Haskell知识的错误.希望有人能澄清它是什么:)

请参考这个要点.我正在将循环链表结构序列化为字节流.对于任何给定节点,形式如下:

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(从容器)时,程序堆栈溢出 - 没有双关语意图 - 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除了(<)可行之外什么都没有.