16

のバグだと思われるものに出くわしましたが、これは私のHaskellData.Mapの知識のバグである可能性も十分にあります。誰かがそれが何であるかを明確にできることを願っています:)

この要点を参照してください。循環リンク リスト構造をバイトストリームにシリアル化しています。任意のノードに対して、次の形式をとります。

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

バイトのペアとしてシリアル化されることを期待しています。最初のバイトは を表し、2 番目のバイトはを配置できるvalバイトストリーム内のオフセットを表します。nextたとえば、次のことを期待しています。

let n0 = Node 0 n1
    n1 = Node 1 n0

として連載予定[0, 1, 1, 0]。大きな問題ではない。

ここで少しトリッキーな部分は、バイトストリーム オフセットの「結び目を結ぶ」MonadFixためにインスタンスを利用していることです。ノードからオフセットへのマップを維持し、シリアル化中にマップにデータを入力しますが、そうでないマップ内のエントリも参照します。RWSTシリアル化が完了するまで、まだ存在する必要があります。

これは、マップの実装がData.HashMap.Lazy( unordered-containersから) である場合にうまく機能します。ただし、実装が通常の場合Data.Map(コンテナーMapから)、プログラム スタックがオーバーフローします (しゃれは意図されていません) (==)。

私の質問は次のとおりです。これは のバグですか、それとも欠陥があるData.Map場合にこれらの構造がどのように動作するかについての私の仮定ですか?mfix

4

1 に答える 1

23

インスタンスが機能しませOrdん:

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

作業Ordインスタンスの場合、compareまたはを定義する必要があります(<=)。のみを定義すると、 or(<)の呼び出しは無限にループします。これは、両方が相互にデフォルトの実装を持っているためです。また、 の他のメンバーは の観点から定義されているため、 以外は機能しません。compare(<=)Ordcompare(<)

于 2012-06-24T19:48:23.500 に答える