haskell - Error en la implementación de Data.Map?

containers monadfix

Question

Me he topado con algo que supongo que es un error en Data.Map , pero que posiblemente también sea un error en mi conocimiento de Haskell. Esperando que alguien pueda aclarar cual es :)

Por favor haga referencia a esta esencia . Estoy serializando una estructura de lista enlazada circular a un bytestream. Para cualquier nodo dado, de la forma:

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

Espero que se serialice como un par de bytes: el primer byte que representa a val , y el segundo byte que representa el desplazamiento en el bytestream donde se puede ubicar el siguiente. Por ejemplo, espero:

let n0 = Node 0 n1
    n1 = Node 1 n0

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

La parte un poco complicada aquí es que estoy explotando la instancia de RWST para RWST para "atar el nudo" de las compensaciones de bytestream: mantengo un mapa desde los nodos a las compensaciones, poblando el mapa durante la serialización, pero también haciendo referencia a las entradas en el mapa que no No existe necesariamente hasta que se complete la serialización.

Esto funciona muy bien cuando la implementación del mapa es Data.HashMap.Lazy (de unordered-containers ). Sin embargo, cuando la implementación es el Data.Map habitual (de los containers ), la pila del programa se desborda, no se pretende hacer un juego de palabras, con Map tratando infinitamente de comparar los dos nodos utilizando (==) .

Entonces, mi pregunta es: ¿ es esto un error en Data.Map , o mis suposiciones sobre cómo deben comportarse estas estructuras en presencia de mfix erróneas?

Answer 1

Tu instancia de Ord no funciona:

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

Para una instancia Ord trabajo, debe definir compare o (<=) . Si solo define (<) , cualquier llamada para compare o (<=) 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á.