persistent-equivalence 0.2 → 0.3
raw patch · 2 files changed
+26/−22 lines, 2 files
Files
Data/Equivalence/Persistent.hs view
@@ -3,8 +3,7 @@ 'Equivalence' is an equivalence relation. The empty equivalence relation is constructed over a ranges of values using 'emptyEquivalence'. Less discerning equivalence relations can be obtained with 'equate' and- 'equateAll'. The relation can be tested with 'equiv' and 'equivalent', and- canonical representatives can be chosen with 'repr'.+ 'equateAll'. The relation can be tested with 'equiv' and 'equivalent'. An example follows: @@ -23,7 +22,6 @@ Equivalence, emptyEquivalence, domain,- repr, equiv, equivalent, equate,@@ -36,6 +34,7 @@ import Data.Array.Diff import Data.IORef import Data.List+import Data.Maybe import System.IO.Unsafe arrayFrom :: (IArray a e, Ix i) => (i,i) -> (i -> e) -> a i e@@ -75,19 +74,20 @@ domain (Equivalence rs _) = bounds rs -reprHelper :: Ix i => DiffArray i i -> i -> (DiffArray i i, i)+reprHelper :: Ix i => DiffArray i i -> i -> (Maybe (DiffArray i i), i) reprHelper ps i- | pi == i = (ps, i)- | otherwise = let (ps', r) = reprHelper ps pi in (ps' // [(i,r)], r)+ | pi == i = (Nothing, i)+ | otherwise = let (ps', r) = reprHelper ps pi+ in (Just (fromMaybe ps ps' // [(i,r)]), r) where pi = ps ! i -{-|+{- 'repr' gives a canonical representative of the equivalence class containing @x@. It is chosen arbitrarily, but is always the same for a given class and 'Equivalence' value. - If you are using this function, you're probably doing something wrong.- Please note that:+ This is not exported, because clients that use this are doing something+ wrong. Note that: * The representative chosen depends on the order in which the equivalence relation was built, and is not always the same for@@ -100,14 +100,14 @@ you have to provide one as input to the function anyway, so you may as well use that. - Because of this, the function may be removed in a future version. Please- contact me if you have a compelling use for it.+ The only guarantee provided is that repr always returns the same value for+ the exact same 'Equivalence'. -} repr :: Ix i => Equivalence i -> i -> i repr (Equivalence rs vps) i = unsafePerformIO $ do ps <- readIORef vps let (ps', r) = reprHelper ps (ps ! i)- writeIORef vps ps'+ maybe (return ()) (writeIORef vps) ps' return r {-|@@ -132,10 +132,14 @@ equate :: Ix i => i -> i -> Equivalence i -> Equivalence i equate x y (Equivalence rs vps) = unsafePerformIO $ do ps <- readIORef vps- let (ps', px) = reprHelper ps x- (ps'', py) = reprHelper ps' y- writeIORef vps ps''- return (go px py ps'')+ let (ps', px) = reprHelper ps x+ (ps'', py) = reprHelper (fromMaybe ps ps') y+ psFinal <- case ps' of+ Nothing -> do maybe (return ()) (writeIORef vps) ps''+ return (fromMaybe ps ps'')+ Just t -> do writeIORef vps (fromMaybe t ps'')+ return (fromMaybe t ps'')+ return (go px py psFinal) where go px py ps | px == py = Equivalence rs vps@@ -156,3 +160,4 @@ equateAll :: Ix i => [i] -> Equivalence i -> Equivalence i equateAll [] eq = eq equateAll (x:xs) eq = foldl' (flip (equate x)) eq xs+
persistent-equivalence.cabal view
@@ -1,7 +1,7 @@ Name: persistent-equivalence-Version: 0.2+Version: 0.3 Synopsis: Persistent equivalence relations (aka union-find)-Description: This is a semi-persistent data structure for equivalence+Description: This is a persistent data structure for equivalence relations (known in the imperative world as union-find or disjoint set union). It exhibits optimal performance when used in a linear pattern, but degrades when other@@ -13,10 +13,9 @@ paper, this version is safe with multiple threads, but does not optimize for backtracking. .- Version 0.2 removes unnecessary atomic operations when- doing updates that are never semantically meaningful,- hopefully leading to better scalability in a parallel- setting.+ Version 0.3 contains some performance improvements for+ concurrent applications, and removes the 'repr' function,+ which was poorly defined and had no good uses. License: BSD3 License-file: LICENSE Author: Chris Smith <cdsmith@gmail.com>