3

在我最初尝试创建一个不相交的集合数据结构时，我创建了一个Point带有parent指向另一个指针的数据类型Point：

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

为了创建一个单例集，创建了一个以Point自身为父集的 a （我相信这被称为打结）：

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

现在，当我想写findSet（即跟随父指针，直到找到Point它的父对象本身）时，我遇到了一个问题：是否可以检查是否是这种情况？一个幼稚Eq的实例当然会无限循环——但这个检查在概念上是否可以编写？

（我最终使用 aMaybe Point作为父字段，请参阅我的另一个问题。）

4

4 回答 4

5

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

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

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

pl2 :: Point Int
pl2 = Point 0 pl2 1

Haskell 认为这两个值完全相等。即 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值的表示。

于 2013-08-06T12:30:24.410 回答
4

您可以尝试使用StableName(或StablePtr) 和来执行此操作unsafePerformIO，但这似乎比Maybe Point这种情况更糟糕。

于 2013-08-06T11:34:01.000 回答
3

为了观察到您最可能感兴趣的效果——指针相等而不是值相等——您很可能希望在STmonad 中编写算法。monad 可以被认为有点像“ST本地不纯 IO，全局纯 API”，但根据 Union Find 的性质，您可能不得不将整个查找过程浸入代码的不纯部分。

幸运的是，单子仍然很好地包含了这种杂质。

Haskell 中已经有一个 Union Find 的实现，它使用三种方法来实现您正在寻找的身份类型：使用IOmonad、使用IntSets 和使用STmonad。

于 2013-08-06T14:22:27.710 回答
0

在 Haskell 中，数据是不可变的（除了IO a, IORef a, ST a, STRef a, ..）并且数据是函数。所以，任何数据都是“单一的”

当您键入

data C = C {a, b :: Int}
changeCa :: C -> Int -> C
changeCa c newa = c {a = newa}

您不会更改变量，而是销毁旧数据并创建新数据。您可以尝试使用链接和指针，但它无用且复杂

最后，

data Point a = Point {p :: Point a}

是一个无限的类似列表的数据 =Point { p=Point { p=Point { p=Point { ....

于 2013-08-06T18:40:16.363 回答