GHC中派生的Eq实例的效率如何？

Question

是否存在内置于GHC(以及一般Haskell)派生实例的短路Eq,当我比较数据类型的同一实例时会触发该实例？

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

我的计划是读取一个惰性数据结构(比如一棵树),更改一些值,然后比较旧版本和新版本以创建一个差异,然后将其写回文件.

如果内置短路,那么一旦发现新结构引用旧值,比较步骤就会中断.同时,这首先不会从文件中读取.

我知道我不应该担心Haskell中的引用,但这似乎是处理惰性文件更改的好方法.如果内置没有短路,是否有办法实现这一点？对不同方案的建议表示欢迎.

Answer 1

StableNames专门用于解决像您这样的问题.

请注意,StableNames只能在IOmonad中创建.所以你有两个选择:在monad中创建你的对象IO,或者unsafePerformIO在你的(==)实现中使用(在这种情况下或多或少都可以).

但我应该强调,有可能以一种完全安全的方式(没有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 替换monad,State Integer并在该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)

这样,即使短路不会在最顶层发射,它也可能会在中间的某处发生,但仍可以节省一些工作.