16

我偶然发现了一些我猜是 中的错误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（来自unordered-containers）时，这很有效。但是，当实现是通常的Data.Map（来自容器）时，程序堆栈溢出 - 没有双关语 -Map无限尝试使用(==).

所以我的问题是：这是一个错误Data.Map，还是我对这些结构在存在mfix缺陷的情况下应该如何表现的假设？

4

1 回答 1

23

您的Ord实例不起作用：

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

对于工作Ord实例，您必须定义compareor (<=)。如果您只定义，则对或(<)的任何调用都将无限循环，因为两者都具有彼此的默认实现。的其他成员也是根据 定义的，因此除此之外没有任何作用。compare(<=)Ordcompare(<)

于 2012-06-24T19:48:23.500 回答