Ошибка в реализации 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так что ничего кроме (<) буду работать.