Fehler in der Implementierung von Data.Map?

Question

Ich bin auf etwas gestolpert, das ich bin Raten ist ein Fehler in Data.Map, aber das ist auch möglicherweise ein Fehler in meinem Haskell Wissen. Hoffe, jemand kann klären, was es ist :)

Bitte Referenz this gist. Ich bin eine zirkuläre verkettete Listenstruktur zu einem Bytestrom serialisieren. Für jeden gegebenen Knoten, der Form:

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

I erwarten, dass es als ein Paar von Bytes serialisiert werden: das erste Byte repräsentiert val, und das zweite Byte repräsentiert, die in der Bytestrom-Offset in dem next angeordnet werden kann. Zum Beispiel erwarte ich:

let n0 = Node 0 n1 
    n1 = Node 1 n0 

als [0, 1, 1, 0] serialisiert werden. Keine große Sache.

Der etwas schwierige Teil hier ist, dass ich die MonadFix Instanz für RWST bin Ausnutzung von Bytestrom Offsets „den Bund fürs Leben“: Ich habe eine Karte von Knoten zu Offsets, bevölkern die Karte während der Serialisierung halten, sondern auch Referenzierung Einträge in die Karte, die noch nicht existiert, bis die Serialisierung abgeschlossen ist.

Dies funktioniert hervorragend, wenn die Kartenimplementierung Data.HashMap.Lazy (von) ist. Wenn jedoch die Implementierung der üblichen (von containers) ist, überläuft der Programmstapel - kein Wortspiel beabsichtigt - mit Map versucht unendlich die beiden Knoten mit (==) zu vergleichen.

Also meine Frage ist: ist dies ein Fehler in Data.Map, oder sind meine Annahmen darüber, wie diese Strukturen in Gegenwart von mfix fehlerhaft verhalten sollen?

Answer 1

Ihre Ord Instanz nicht funktioniert:

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

Ein funktionstüchtiges Ord Beispiel Sie compare oder (<=) definieren. Wenn Sie nur (<) definieren, wird jeder Aufruf an compare oder (<=) unendlich wiederholt, da beide Standardimplementierungen in Bezug aufeinander haben. Auch die anderen Mitglieder von Ord sind in Bezug auf compare definiert, so dass nichts außer (<) funktioniert.