数据结构中的自引用–检查是否相等 [英] Self-reference in data structure – Checking for equality

问题描述

在最初尝试创建不连续的集合数据结构时，我创建了 Point 数据类型，并使用了 parent 指针到另一个点：

 数据点a =点
 {_value :: a 
，_parent ::指向a 
，_rank :: Int 
} 
  

要创建单例集，将创建一个以自身为父元素的 Point （我相信这称为打结）：

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

现在，当我想写一个 findSet （即跟随父指针，直到找到一个父元素本身的 Point ），我遇到了一个问题：是否可以检查这种情况？天真的 Eq 实例当然会无限循环-但是从概念上讲，这种检查是否可以写？

（我结束了使用也许点作为父字段的方法，请参见我的其他问题。）

解决方案

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

例如，您可以问自己是否会考虑以下两个值相同：

  pl1 ::点整数
 pl1 =点0（点0 pl1 1）1 
 
 pl2 ::点整数
 pl2 =点0 pl2 1 
  

Haskell认为两个值完全相等。即Haskell 不不支持引用身份。原因之一是它会违反Haskell支持的其他功能。举例来说，在Haskell中，我们始终可以通过该函数的实现来替换对该函数的引用，而无需更改其含义（等式推理）。例如，如果我们采用 pl2 的实现： Point 0 pl2 1 并替换 pl2 的定义，我们得到 Point 0（Point 0 pl2 1）1 ，使 pl2 的定义等同于 pl1 的定义。这表明Haskell不允许您观察 pl1 和 pl2 之间的差异，而不会违反等式推理所隐含的属性。 / p>

您可以使用 unsafePerformIO 之类的不安全功能（如上所述）来解决Haskell中缺少引用身份的问题，但是您应该知道自己当时正在打破Haskell的核心原理，并且当GHC开始优化（例如，内联）代码时，您可能会发现奇怪的错误。最好使用不同的数据表示形式，例如您提到的那个使用也许点值。

In my initial attempt at creating a disjoint set data structure I created a Point data type with a parent pointer to another Point:

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

To create a singleton set, a Point is created that has itself as its parent (I believe this is called tying the knot):

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

Now, when I wanted to write findSet (i.e. follow parent pointers until you find a Point whose parent is itself) I hit a problem: Is it possible to check if this is the case? A naïve Eq instance would of course loop infinitely – but is this check conceptually possible to write?

(I ended up using a Maybe Point for the parent field, see my other question.)

解决方案

No, what you are asking for is known in the Haskell world as referential identity: the idea that for two values of a certain type, you can check whether they are the same value in memory or two separate values that happen to have exactly the same properties.

For your example, you can ask yourself whether you would consider the following two values the same or not:

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

pl2 :: Point Int
pl2 = Point 0 pl2 1

Haskell considers both values completely equal. I.e. Haskell does not support referential identity. One of the reasons for this is that it would violate other features that Haskell does support. It is for example the case in Haskell that we can always replace a reference to a function by that function's implementation without changing the meaning (equational reasoning). For example if we take the implementation of pl2: Point 0 pl2 1 and replace pl2 by its definition, we get Point 0 (Point 0 pl2 1) 1, making pl2's definition equivalent to pl1's. This shows that Haskell cannot allow you to observe the difference between pl1 and pl2 without violating properties implied by equational reasoning.

You could use unsafe features like unsafePerformIO (as suggested above) to work around the lack of referential identity in Haskell, but you should know that you are then breaking core principles of Haskell and you may observe weird bugs when GHC starts optimizing (e.g. inlining) your code. It is better to use a different representation of your data, e.g. the one you mentioned using a Maybe Point value.

这篇关于数据结构中的自引用–检查是否相等的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！