8

当我比较数据类型的相同实例时，GHC（以及一般的 Haskell）派生实例中是否存在短路？Eq

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

我的计划是读入一个惰性数据结构（比如说一棵树），更改一些值，然后比较旧版本和新版本以创建一个差异，然后将其写回文件。

如果内置短路，那么一旦发现新结构引用旧值，比较步骤就会中断。同时，这不会首先从文件中读取超过必要的内容。

我知道我不应该担心 Haskell 中的引用，但这似乎是处理延迟文件更改的好方法。如果没有内置短路，有没有办法实现这个？欢迎对不同方案提出建议。

4

2 回答 2

8

StableNames 是专门为解决像您这样的问题而设计的。

请注意，StableNames 只能在IOmonad 中创建。所以你有两个选择：要么在monad中创建你的对象，要么在你的实现中使用（在这种情况下或多或少很好）。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

请注意，如果稳定名称比较说“否”，您仍然需要执行全值比较以获得明确的答案。

根据我的经验，当你有很多共享并且由于某种原因不愿意使用其他方法来表示共享时，效果很好。

（说到其他方法，例如，您可以将IOmonad替换为State Integermonad 并在该 monad 中生成唯一整数作为“稳定名称”的等价物。）

另一个技巧是，如果你有一个递归数据结构，让递归通过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 回答