Lỗi trong triển khai Data.Map?

Question

Tôi đã tình cờ gặp một điều gì đó mà tôi đang đoán là lỗi trong số Data.Map, nhưng cũng có thể là một lỗi trong kiến ​​thức Haskell của tôi. Hy vọng ai đó có thể làm rõ nó là gì :)

Vui lòng tham khảo this gist. Tôi đang sắp xếp tuần tự một cấu trúc danh sách được liên kết vòng tròn tới một luồng. Đối với bất kỳ nút nào đó, có dạng:

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

Tôi hy vọng nó sẽ được tuần tự như một cặp byte: byte đầu tiên đại diện cho val, và byte thứ hai đại diện cho bù đắp trong bytestream nơi next có thể được đặt. Ví dụ: tôi mong đợi:

let n0 = Node 0 n1 
    n1 = Node 1 n0 

để được tuần tự hóa là [0, 1, 1, 0]. Không phải vấn đề lớn.

Phần hơi khó hiểu ở đây là tôi đang khai thác dụ MonadFix cho RWST để "kết hôn" của offsets bytestream: Tôi duy trì một bản đồ từ các nút để bù đắp, Populating bản đồ trong serialization, mà còn tham khảo các mục trong bản đồ không nhất thiết tồn tại cho đến khi quá trình serialization hoàn tất.

Điều này hoạt động tốt khi triển khai bản đồ là Data.HashMap.Lazy (từ). Tuy nhiên, khi triển khai là thông thường Data.Map (từ containers), ngăn xếp chương trình tràn - không có ý định chơi chữ - với Map cố gắng vô hạn để so sánh hai nút bằng cách sử dụng (==).

Vì vậy, câu hỏi của tôi là: đây là một lỗi trong Data.Map, hoặc là giả định của tôi về cách cấu trúc này nên cư xử trong sự hiện diện của mfix thiếu sót?

Answer 1

dụ Ord của bạn không hoạt động:

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

Đối với một Ord dụ làm việc, bạn phải xác định compare hoặc (<=). Nếu bạn chỉ xác định (<), mọi cuộc gọi đến compare hoặc (<=) sẽ lặp lại vô hạn vì cả hai đều có triển khai mặc định về mặt nhau. Ngoài ra các thành viên khác của Ord được xác định theo điều khoản của compare, vì vậy không có gì ngoại trừ (<) sẽ hoạt động.