8

データ型の同じインスタンスを比較すると起動するGHC（および一般的にはHaskell）の派生インスタンスに組み込まれている短絡はありますか？Eq

-- will this fire?
let same = complex == complex

私の計画は、怠惰なデータ構造（たとえばツリー）を読み込み、いくつかの値を変更してから、古いバージョンと新しいバージョンを比較してdiffを作成し、それをファイルに書き戻すことです。

短絡が組み込まれている場合、新しい構造が古い値を参照していることが検出されるとすぐに、比較ステップが中断します。同時に、これはそもそもファイルから必要以上に読み込まれることはありません。

Haskellでの参照について心配する必要はないことは知っていますが、これは怠惰なファイル変更を処理するための優れた方法のようです。短絡が組み込まれていない場合、これを実装する方法はありますか？さまざまなスキームに関する提案を歓迎します。

4

2 に答える 2

8

StableName は、あなたのような問題を解決するために特別に設計されています。

StableName はIOモナドでのみ作成できることに注意してください。つまり、モナドでオブジェクトを作成するか、実装で使用するか(この状況では多かれ少なかれ問題ありません) の 2 つの選択肢があります。IOunsafePerformIO(==)

unsafe*しかし、完全に安全な方法 (関数なし) でこれを行うことが可能であることを強調しておく必要がIOあります。その後、完全に純粋な方法でそれらを比較できます。

例えば

data SNWrapper a = SNW !a !(StableName a)

snwrap :: a -> IO (SNWrapper a)
snwrap a = SNW a <$> makeStableName a

instance Eq a => Eq (SNWrapper a) where
  (SNW a sna) (SNW b snb) = sna == snb || a == b

安定した名前の比較で「いいえ」と表示された場合でも、決定的な答えを得るには完全な値の比較を実行する必要があることに注意してください。

私の経験では、多くの共有があり、何らかの理由で共有を示すために他の方法を使用したくない場合に、かなりうまく機能しました。

(他の方法について言えば、たとえば、IOモナドをモナドに置き換えて、そのモナドでState Integer一意の整数を「安定した名前」に相当するものとして生成することができます。)

別のトリックは、再帰的なデータ構造がある場合、再帰をSNWrapper. たとえば、代わりに

data Tree a = Bin (Tree a) (Tree a) | Leaf a
type WrappedTree a = SNWrapper (Tree a)

使用する

data Tree a = Bin (WrappedTree a) (WrappedTree a) | Leaf a
type WrappedTree a = SNWrapper (Tree a)

このように、短絡が最上層で発火しなくても、中間のどこかで発火する可能性があり、それでもいくらかの作業を節約できます。

于 2012-10-09T12:57:18.490 に答える
4

(==)の両方の引数が同じオブジェクトである場合、ショートサーキットはありません。派生Eqインスタンスは構造比較を行い、等しい場合はもちろん構造全体をトラバースする必要があります。を使用して、可能なショートカットを自分で構築できます

GHC.Prim.reallyUnsafePtrEquality# :: a -> a -> GHC.Prim.Int#

しかし、実際にはめったに発生しません。

Prelude GHC.Base> let x = "foo"
Prelude GHC.Base> I# (reallyUnsafePtrEquality# x x)
1
Prelude GHC.Base> I# (reallyUnsafePtrEquality# True True)
1
Prelude GHC.Base> I# (reallyUnsafePtrEquality# 3 3)
0
Prelude GHC.Base> I# (reallyUnsafePtrEquality# (3 :: Int) 3)
0

また、ファイルから構造体を読み取った場合、既にメモリ内にあるオブジェクトと同じオブジェクトであるとは限りません。

書き換え規則を使用して、字句的に同一のオブジェクトの比較を回避できます

module Equal where

{-# RULES
"==/same"  forall x. x == x = True
  #-}

main :: IO ()
main = let x = [1 :: Int .. 10] in print (x == x)

につながる

$ ghc -O -ddump-rule-firings Equal.hs 
[1 of 1] Compiling Equal            ( Equal.hs, Equal.o )
Rule fired: Class op enumFromTo
Rule fired: ==/same
Rule fired: Class op show

ルールの起動 (注: では起動しませんでしlet x = "foo"たが、ユーザー定義型では起動する必要があります)。

于 2012-10-09T10:57:16.317 に答える