我是否需要采取明确的操作来促进与持久数据结构的共享？

我来自命令式背景，正在尝试实现一个简单的不相交集（“并集查找”）数据结构，以获得在 Haskell 中创建和修改（持久）数据结构的一些练习。目标是有一个简单的实现，但我也关心效率，我的问题与此相关。

首先，我创建了一个按等级并集的不相交集森林实现，并首先为“点”定义数据类型：

data Point = Point
  { _value  :: Int
  , _parent :: Maybe Point
  , _rank   :: Int
  } deriving Show

不相交的集合森林是IntMap with Int → Point映射：

type DSForest = IntMap Point

empty :: DSForest
empty = I.empty

单例集只是其值的映射x到一个有价值的点x，没有父级且等级为 1：

makeSet :: DSForest -> Int -> DSForest
makeSet dsf x = I.insert x (Point x Nothing 0) dsf

现在，有趣的部分——union。此操作将通过将另一个点设置为其父点来修改一个点（并且在某些情况下更改其排名）。在这种情况下Points的等级不同，Point只是“更新”（创建一个新点）以使其父点指向另一个点。在它们相等的情况下，一个新的Point创建后其等级增加一：

union :: DSForest -> Int -> Int -> DSForest
union dsf x y | x == y = dsf 
union dsf x y = 
   if _value x' == _value y'
      then dsf 
      else case compare (_rank x') (_rank y') of
                  GT -> I.insert (_value y') y'{ _parent = Just x' } dsf 
                  LT -> I.insert (_value x') x'{ _parent = Just y' } dsf 
                            -- 1) increase x's rank by one:
                  EQ -> let x''  = x'{ _rank = _rank x' + 1 } 
                            -- 2) update the value for x's rank to point to the new x:
                            dsf' = I.insert (_value x'') x'' dsf 
                            -- 3) then update y to have the new x as its parent:
                         in I.insert (_value y') y'{ _parent = Just x'' } dsf'
  where x' = dsf ! findSet dsf x
        y' = dsf ! findSet dsf y

现在，回答我真正的问题，如果EQ在这种情况下，我改为执行以下操作：

EQ -> let dsf' = I.insert (_value x') x'{ _rank = _rank x' + 1} dsf 
       in I.insert (_value y') y'{ _parent = Just x'{ _rank = _rank x' + 1 }} dsf'

IE。首先插入一个新的Point x随着等级的提高，然后有y'的父母是新的Point x随着等级的提升，这是否意味着它们不再指向同一个Point在记忆中？（这还重要吗？在使用/创建持久数据结构时我应该担心这些事情吗？）

为了完整起见，这里是findSet:

findSet :: DSForest -> Int -> Int
findSet dsf' x' = case _parent (dsf' ! x') of
                     Just (Point v _ _)  -> findSet dsf' v
                     Nothing             -> x'

（也欢迎对此代码的效率和设计提出一般性评论。）

这是否意味着它们不再指向内存中的同一个点？

我认为您不应该关心这一点，因为这只是不可变值的运行时系统（又名 Haskell 的 RTS）的实现细节。

至于其他建议，我想说的是让这个功能findSet返回Point本身而不是键，因为这会消除在union.

findSet :: DSForest -> Int -> Point
findSet dsf' x' = case _parent pt of
                     Just (Point v _ _)  -> findSet dsf' v
                     Nothing             -> pt
                  where
                      pt = (dsf' ! x')

进行适当的更改union功能。