haskell - 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 的实例为字节流偏移“打结”:我维护一个从节点到偏移的映射，在序列化期间填充映射，但还引用映射中在序列化完成之前不一定存在的条目。

这在 map 实现为 Data.HashMap.Lazy 时非常有用(来自 unordered-containers)。但是，当实现是通常的 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 定义, 所以除了 (<)将工作。