haskell - 永続的なデータ構造との共有を容易にするために明示的なアクションを実行する必要がありますか?

Question

私は必須のバックグラウンドを持っており、Haskell で (永続的な) データ構造を作成および変更する練習をするために、単純な素集合 (「共用体検索」) データ構造を実装しようとしています。目標はシンプルな実装ですが、効率性も気になります。私の質問はこれに関連しています。

まず、ランクごとの結合を使用して互いに素な集合のフォレストの実装を作成し、「ポイント」のデータ型を定義することから始めました。

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

切り離されたセット フォレストは、次のようIntMapにInt → Pointマッピングされます。

type DSForest = IntMap Point

empty :: DSForest
empty = I.empty

シングルトン セットは、その値xから値xを持つ Point への単純なマッピングであり、親はなく、ランクは 1 です。

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

さて、興味深い部分 – union. この操作は、他のポイントをその親として設定することによってポイントを変更します (場合によってはそのランクを変更します)。Points のランクが異なる場合、は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 xy'を挿入し、次にの親をランクを上げた新しいPoint xにすると、それらはメモリ内で同じものを指さなくなりますか? Point(これは問題ですか?永続的なデータ構造を使用/作成するときにこれらのことを心配する必要がありますか?)

完全を期すために、次のfindSetとおりです。

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

(このコードの効率と設計に関する一般的なコメントも歓迎します。)