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

Question

在我最初尝试创建不相交的集合数据结构时，我创建了一个 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 作为父字段，请参阅 my other question 。)

Answer 1

不，你所要求的在 Haskell 世界中被称为引用身份:对于某种类型的两个值，你可以检查它们在内存中是否是相同的值或两个不同的值恰好具有完全相同的属性。

对于您的示例，您可以问问自己是否认为以下两个值相同:

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

pl2 :: Point Int
pl2 = Point 0 pl2 1

Haskell 认为这两个值完全相等。 IE。 Haskell 不支持引用身份。原因之一是它会违反 Haskell 支持的其他功能。例如，在 Haskell 中，我们总是可以用函数的实现替换对函数的引用，而不改变含义(等式推理)。例如，如果我们采用 pl2 的实现:Point 0 pl2 1 并用其定义替换 pl2，我们得到 Point 0 (点 0 pl2 1) 1，使得 pl2 的定义等同于 pl1 的定义。这表明 Haskell 无法让您在不违反等式推理所隐含的属性的情况下观察 pl1 和 pl2 之间的差异。

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