Error en la implementación de Data.Map?

Question

Me he topado con algo que estoy adivinando es un error en Data.Map, pero que también es muy posiblemente un error en mi conocimiento de Haskell. Esperando que alguien pueda aclarar cuál es :)

Consulte this gist. Estoy serializando una estructura circular de lista enlazada a una copia de prueba. Para cualquier nodo dado, de la forma:

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

espero que puede serializar como un par de bytes: el primer byte que representa val, y el segundo byte representa el desplazamiento en el bytestream donde next puede ser localizado. Por ejemplo, espero:

let n0 = Node 0 n1 
    n1 = Node 1 n0 

que ser serializado como [0, 1, 1, 0]. No es gran cosa.

La parte poco difícil aquí es que estoy explotando la instancia MonadFix para RWST a "atar el nudo" de las compensaciones de chorro de bytes: Mantengo un mapa de nodos a las compensaciones, poblando el mapa durante la serialización, sino que también hace referencia a las entradas de el mapa que no existe necesariamente hasta que la serialización esté completa.

Esto funciona muy bien cuando la implementación del mapa es Data.HashMap.Lazy (desde). Sin embargo, cuando la implementación es la habitual Data.Map (desde containers), la pila de programas se desborda, sin juego de palabras, con Map intentando infinitamente comparar los dos nodos usando (==).

Así que mi pregunta es: es esto un error en Data.Map, o son mis suposiciones acerca de cómo estas estructuras deben comportarse en presencia de mfix defectuoso?

Answer 1

Su Ord ejemplo no funciona:

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

Para una Ord instancia de trabajo, debe definir compare o (<=). Si solo define (<), cualquier llamada al compare o (<=) se repetirá infinitamente, ya que ambas tienen implementaciones predeterminadas en términos de la otra. También los otros miembros de Ord se definen en términos de compare, por lo que nada excepto (<) funcionará.