Bug nell'implementazione Data.Map?

Question

Mi sono imbattuto in qualcosa che io sono indovinando è un bug in Data.Map, ma che è anche molto probabilmente un bug nella mia conoscenza Haskell. Sperando che qualcuno possa chiarire di cosa si tratta :)

Si prega di riferimento this gist. Sto serializzando una struttura circolare di elenchi collegati a un puntatore. Per ogni dato nodo, di forma:

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

mi aspetto da serializzare come una coppia di byte: il primo byte rappresenta val, e il secondo byte che rappresenta l'offset nella bytestream dove può essere situato next. Per esempio, mi aspetto:

let n0 = Node 0 n1 
    n1 = Node 1 n0 

essere serializzato come [0, 1, 1, 0]. Nessun grosso problema.

La parte un po 'difficile qui è che sto sfruttando l'istanza MonadFix per RWST a "legare il nodo" delle compensazioni Bytestream: Io sostengo una mappa da nodi a offset, popolando la mappa durante la serializzazione, ma anche riferimento a voci in la mappa che non esiste necessariamente fino a quando la serializzazione non è completa.

Questo funziona perfettamente quando l'implementazione della mappa è Data.HashMap.Lazy (da). Tuttavia, quando l'implementazione è la solita Data.Map (da containers), lo stack del programma trabocca - no pun intended - con Map che tenta infinitamente di confrontare i due nodi usando (==).

Quindi la mia domanda è: è questo un bug in Data.Map, o sono i miei ipotesi su come queste strutture dovrebbero comportarsi in presenza di mfix viziata?

Answer 1

tuo esempio Ord non funziona:

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

Per un lavoro Ord esempio, è necessario definire compare o (<=). Se si definisce solo (<), qualsiasi chiamata a compare o (<=) verrà interrotta a ciclo continuo poiché entrambe hanno implementazioni predefinite in termini l'una dell'altra. Anche gli altri membri di Ord sono definiti in termini di compare, quindi non funziona nulla tranne (<).