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

Question

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

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

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

脱节的集合森林是一个具有 Int → Point 映射的 IntMap:

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。此操作将通过将另一个点设置为其父点来修改一个点(并且在某些情况下更改其排名)。在Point的等级不同的情况下，Point只需“更新”(创建一个新的Point)以使其父点指向另一个点。如果它们相等，则会创建一个新的 Point，其等级增加 1:

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'

即首先插入一个新的Point x，其等级增加，然后让y'的父级成为一个新的Point x 随着其排名的提高，这是否意味着它们不再指向内存中的同一个点？(这还重要吗？应该我在使用/创建持久数据结构时担心这些事情？)

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

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

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

Answer 1

would this mean that they no longer point to the same Point in memory?

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

就其他建议而言，我建议让函数 findSet 返回 Point 本身而不是键，因为这会消除 中的查找联盟。

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

在 union 函数中进行适当的更改。