数据结构中的自引用 - 检查相等性

Question

在我最初尝试创建一个不相交的set数据结构时,我创建了一个Point带有parent另一个指针的数据类型Point:

data Point a = Point
  { _value  :: a
  , _parent :: Point a
  , _rank   :: Int
  }

要创建一个单例集,创建一个将Point其自身作为其父级的东西(我相信这称为绑结):

makeSet' :: a -> Point a
makeSet' x = let p = Point x p 0 in p

现在,当我想写findSet(即跟随父指针,直到找到Point其父亲本身)我遇到了一个问题:是否有可能检查是否是这种情况？一个天真的Eq实例当然会无限循环 - 但是这个检查在概念上是否可以编写？

(我最终使用了一个Maybe Point用于父字段,请参阅我的另一个问题.)

Answer 1

不,你所要求的是在Haskell世界中被称为参照身份:对于某种类型的两个值,你可以检查它们在内存中是否是相同的值,或者两个单独的值碰巧具有完全相同的想法属性.

对于您的示例,您可以问自己是否会考虑以下两个值相同或不同:

pl1 :: Point Int
pl1 = Point 0 (Point 0 pl1 1) 1

pl2 :: Point Int
pl2 = Point 0 pl2 1

Haskell认为两个值完全相同.即哈斯克尔并没有支持参考身份.其中一个原因是它会违反Haskell支持的其他功能.例如,在Haskell中,我们总是可以通过该函数的实现替换对函数的引用而不改变含义(等式推理).例如,如果我们执行pl2:Point 0 pl2 1并且pl2通过其定义替换,我们得到Point 0 (Point 0 pl2 1) 1,使得pl2定义等同于pl1's.这表明Haskell不允许您观察pl1与pl2违反等式推理所暗示的属性之间的差异.

您可以使用不安全的功能unsafePerformIO(如上所述)来解决Haskell中缺少引用标识的问题,但是您应该知道您正在破坏Haskell的核心原则,并且当GHC开始优化(例如内联)时您可能会发现奇怪的错误码.最好使用不同的数据表示形式,例如您使用Maybe Point值提到的数据.