1import qualified Data.IntMap.Strict as M
2
3data UF = UF
4  { parent :: M.IntMap Int
5  , ranks  :: M.IntMap Int
6  } deriving Show
7
8makeUF :: [Int] -> UF
9makeUF xs = UF
10  { parent = M.fromList [(x, x) | x <- xs]
11  , ranks  = M.fromList [(x, 0) | x <- xs]
12  }
13
14findUF :: Int -> UF -> (Int, UF)
15findUF x uf =
16  case M.lookup x (parent uf) of
17    Nothing -> error "unknown element"
18    Just p
19| p == x -> (x, uf) | otherwise -> let (root, uf1) = findUF p uf newParent = M.insert x root (parent uf1) in (root, uf1 { parent = newParent }) unionUF :: Int -> Int -> UF -> UF unionUF x y uf = let (rx, uf1) = findUF x uf (ry, uf2) = findUF y uf1 in if rx == ry then uf2 else let rankX = M.findWithDefault 0 rx (ranks uf2) rankY = M.findWithDefault 0 ry (ranks uf2) in case compare rankX rankY of LT -> uf2 { parent = M.insert rx ry (parent uf2) } GT -> uf2 { parent = M.insert ry rx (parent uf2) } EQ -> uf2 { parent = M.insert ry rx (parent uf2) , ranks  = M.insert rx (rankX + 1) (ranks uf2) } equivalent :: Int -> Int -> UF -> (Bool, UF) equivalent x y uf = let (rx, uf1) = findUF x uf (ry, uf2) = findUF y uf1 in (rx == ry, uf2) main :: IO () main = do let uf0 = makeUF [1 .. 6] uf1 = unionUF 1 2 uf0 uf2 = unionUF 2 3 uf1 uf3 = unionUF 4 5 uf2 (same13, uf4) = equivalent 1 3 uf3 (same16, uf5) = equivalent 1 6 uf4 print same13 print same16 print uf5 ``` This version keeps the same asymptotic ideas as the mutable form. Path compression is still happening, but it is represented as a returned value instead of an in-place side effect. ## Practical Tradeoffs in Functional Code The persistent design has a clear advantage: older versions of the structure remain valid. That can be useful in backtracking algorithms, theorem provers, or any system where you want to keep snapshots. The tradeoff is allocation. Mutable union-find is hard to beat for raw speed. Functional union-find is still useful, but you should be honest about the use case. If your algorithm is intensely update-heavy and does not benefit from persistence, a local mutable array inside a controlled functional wrapper can be a better engineering choice. Even so, the conceptual model stays the same. Equivalence classes are still represented by representatives, `union` still merges trees, and compression still matters if you want repeated queries to stay fast. ## Common Pitfalls - Throwing away the updated structure returned from `find`. In a functional implementation, that also throws away path compression. - Using plain lists for parent lookup. That turns core operations into linear scans and defeats the purpose of union-find. - Skipping union by rank or size. Without it, trees can become much deeper than they need to be. - Forgetting to initialize every element as its own parent before the first merge. - Mixing persistence and mutation accidentally, which can make the algorithm harder to reason about than either approach alone. ## Summary - Equivalence classes partition a set into disjoint groups defined by an equivalence relation. - Union-find supports fast representative lookup with `find` and class merging with `union`. - In a functional language, path compression usually means returning an updated structure from `find`. - Persistent implementations trade some raw performance for immutability and snapshot-friendly behavior. - Use maps or arrays plus rank heuristics so the structure remains efficient at scale.