equivalence 0.3.1 → 0.3.2

raw patch · 4 files changed

+39/−34 lines, 4 filesdep ~STMonadTransPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependency ranges changed: STMonadTrans

API changes (from Hackage documentation)

Files

• CHANGES.txt +4/−0
• equivalence.cabal +6/−6
• src/Data/Equivalence/Monad.hs +5/−5
• src/Data/Equivalence/STT.hs +24/−23

@@ -1,3 +1,7 @@+0.3.2+-----+* add Applicative constraints for backwards compatibility with GHC 7.8+ 0.3.1 ----- * use transformers-compat for backwards compatibility with older versions of transformers

@@ -1,11 +1,11 @@ Name:            equivalence-Version:         0.3.1+Version:         0.3.2 License:         BSD3 License-File:    LICENSE Author:          Patrick Bahr Maintainer:      paba@di.ku.dk-Homepage:        https://bitbucket.org/paba/equivalence/-bug-reports:     https://bitbucket.org/paba/equivalence/issues/new+Homepage:        https://github.com/pa-ba/equivalence+bug-reports:     https://github.com/pa-ba/equivalence/issues/new Synopsis:        Maintaining an equivalence relation implemented as union-find using STT. Description:	    This is an implementation of Tarjan's Union-Find algorithm (Robert@@ -24,8 +24,8 @@   source-repository head-  type:     hg-  location: https://bitbucket.org/paba/equivalence/+  type:     git+  location: https://github.com/pa-ba/equivalence   Test-Suite test@@ -39,7 +39,7 @@  Library   Build-Depends:-    base >= 4 && < 5, containers, mtl >= 2.0.1, STMonadTrans,+    base >= 4 && < 5, containers, mtl >= 2.0.1, STMonadTrans >= 0.4.1,     transformers >= 0.2, transformers-compat >= 0.3   Exposed-Modules:     Data.Equivalence.STT,

@@ -89,7 +89,7 @@ instance Functor m => Functor (EquivT s c v m) where   fmap f (EquivT m) = EquivT $ fmap f m -instance (Functor m, Monad m) => Applicative (EquivT s c v m) where+instance (Applicative m, Monad m) => Applicative (EquivT s c v m) where   pure = EquivT . pure   (EquivT f) <*> (EquivT a) = EquivT (f <*> a) @@ -122,7 +122,7 @@ an equivalence class descriptor for a singleton class and how to combine two equivalence class descriptors. -} -runEquivT :: (Monad m)+runEquivT :: (Monad m, Applicative m)           => (v -> c) -- ^ used to construct an equivalence class descriptor for a singleton class           -> (c -> c -> c) -- ^ used to combine the equivalence class descriptor of two classes                            --   which are meant to be combined.@@ -136,7 +136,7 @@ {-| This function is a special case of 'runEquivT' that only maintains trivial equivalence class descriptors of type @()@. -} -runEquivT' :: (Monad m) => (forall s. EquivT' s v m a) -> m a+runEquivT' :: (Monad m, Applicative m) => (forall s. EquivT' s v m a) -> m a runEquivT' = runEquivT (const ()) (\_ _-> ())  {-| This function runs a monadic computation that maintains an@@ -159,7 +159,7 @@ {-| This class specifies the interface for a monadic computation that maintains an equivalence relation.  -} -class (Monad m, Ord v) => MonadEquiv c v d m | m -> v, m -> c, m -> d where+class (Monad m, Applicative m, Ord v) => MonadEquiv c v d m | m -> v, m -> c, m -> d where     {-| This function decides whether the two given elements are         equivalent in the current equivalence relation -} @@ -228,7 +228,7 @@                                        -instance (Monad m, Ord v) => MonadEquiv (Class s d v) v d (EquivT s d v m) where+instance (Monad m, Applicative m, Ord v) => MonadEquiv (Class s d v) v d (EquivT s d v m) where     equivalent x y = EquivT $ do       part <- ask       lift $ S.equivalent part x y

@@ -61,6 +61,7 @@  import Control.Monad.ST.Trans import Control.Monad+import Control.Applicative  import Data.Maybe @@ -116,7 +117,7 @@ @a@). The arguments are used to maintain equivalence class descriptors. -} -leastEquiv :: Monad m+leastEquiv :: (Monad m, Applicative m)            => (a -> c) -- ^ used to construct an equivalence class descriptor for a singleton class            -> (c -> c -> c) -- ^ used to combine the equivalence class descriptor of two classes                             --   which are meant to be combined.@@ -133,7 +134,7 @@  This function performs path compression.  -} -representative' :: Monad m => Entry s c a -> STT s m (Maybe (Entry s c a),Bool)+representative' :: (Monad m, Applicative m) => Entry s c a -> STT s m (Maybe (Entry s c a),Bool) representative' (Entry e) = do   ed <- readSTRef e   case ed of@@ -151,7 +152,7 @@  This function performs path compression.  -} -representative :: (Monad m, Ord a) => Equiv s c a -> a -> STT s m (Entry s c a)+representative :: (Monad m, Applicative m, Ord a) => Equiv s c a -> a -> STT s m (Entry s c a) representative eq v = do   mentry <- getEntry eq v   case mentry of -- check whether there is an entry@@ -167,7 +168,7 @@ {-| This function provides the representative entry of the given equivalence class. This function performs path compression. -} -classRep :: (Monad m, Ord a) => Equiv s c a -> Class s c a -> STT s m (Entry s c a)+classRep :: (Monad m, Applicative m, Ord a) => Equiv s c a -> Class s c a -> STT s m (Entry s c a) classRep eq (Class p) = do   entry <- readSTRef p   (mrepr,del) <- representative' entry@@ -187,7 +188,7 @@ entry's value, inserts it into the lookup table (thereby removing any existing entry). -} -mkEntry' :: (Monad m, Ord a)+mkEntry' :: (Monad m, Applicative m, Ord a)         => Equiv s c a -> Entry s c a         -> STT s m (Entry s c a)  -- ^ the constructed entry mkEntry' eq (Entry e) = readSTRef e >>= mkEntry eq . entryValue@@ -196,7 +197,7 @@ value, inserts it into the lookup table (thereby removing any existing entry). -} -mkEntry :: (Monad m, Ord a)+mkEntry :: (Monad m, Applicative m, Ord a)         => Equiv s c a -> a         -> STT s m (Entry s c a)  -- ^ the constructed entry mkEntry Equiv {entries = mref, singleDesc = mkDesc} val = do@@ -214,13 +215,13 @@ {-| This function provides the equivalence class the given element is contained in. -} -getClass :: (Monad m, Ord a) => Equiv s c a -> a -> STT s m (Class s c a)+getClass :: (Monad m, Applicative m, Ord a) => Equiv s c a -> a -> STT s m (Class s c a) getClass eq v = do    en <- (getEntry' eq v)   liftM Class $ newSTRef en    -getEntry' :: (Monad m, Ord a) => Equiv s c a -> a -> STT s m (Entry s c a)+getEntry' :: (Monad m, Applicative m, Ord a) => Equiv s c a -> a -> STT s m (Entry s c a) getEntry' eq v = do   mentry <- getEntry eq v   case mentry of@@ -231,7 +232,7 @@ equivalence relation representation or @Nothing@ if there is none, yet.  -} -getEntry :: (Monad m, Ord a) => Equiv s c a -> a -> STT s m (Maybe (Entry s c a))+getEntry :: (Monad m, Applicative m, Ord a) => Equiv s c a -> a -> STT s m (Maybe (Entry s c a)) getEntry Equiv { entries = mref} val = do   m <- readSTRef mref   case Map.lookup val m of@@ -245,7 +246,7 @@ descriptor. The returned entry is the representative of the new equivalence class -} -equateEntry :: (Monad m, Ord a) => Equiv s c a -> Entry s c a -> Entry s c a -> STT s m (Entry s c a)+equateEntry :: (Monad m, Applicative m, Ord a) => Equiv s c a -> Entry s c a -> Entry s c a -> STT s m (Entry s c a) equateEntry Equiv {combDesc = mkDesc} repx@(Entry rx) repy@(Entry ry) =    if (rx /= ry) then do     dx@Root{entryWeight = wx, entryDesc = chx, entryValue = vx} <- readSTRef rx@@ -263,7 +264,7 @@   -combineEntries :: (Monad m, Ord a)+combineEntries :: (Monad m, Applicative m, Ord a)                => Equiv s c a -> [b] -> (b -> STT s m (Entry s c a)) -> STT s m () combineEntries  _ [] _ = return () combineEntries eq (e:es) rep = do@@ -280,7 +281,7 @@ list. Afterwards all elements in the argument list represent the same equivalence class! -} -combineAll :: (Monad m, Ord a) => Equiv s c a -> [Class s c a] -> STT s m ()+combineAll :: (Monad m, Applicative m, Ord a) => Equiv s c a -> [Class s c a] -> STT s m () combineAll eq cls = combineEntries eq cls (classRep eq)  @@ -289,7 +290,7 @@ class! One of it is returned in order to represent the new combined equivalence class. -} -combine :: (Monad m, Ord a) => Equiv s c a -> Class s c a -> Class s c a -> STT s m (Class s c a)+combine :: (Monad m, Applicative m, Ord a) => Equiv s c a -> Class s c a -> Class s c a -> STT s m (Class s c a) combine eq x y = combineAll eq [x,y] >> return x  @@ -297,21 +298,21 @@ unions the equivalence classes of the elements and combines their descriptor. -} -equateAll :: (Monad m, Ord a) => Equiv s c a -> [a] -> STT s m ()+equateAll :: (Monad m, Applicative m, Ord a) => Equiv s c a -> [a] -> STT s m () equateAll eq cls = combineEntries eq cls (representative eq)  {-| This function equates the two given elements. That is, it unions the equivalence classes of the two elements and combines their descriptor. -} -equate :: (Monad m, Ord a) => Equiv s c a -> a -> a -> STT s m ()+equate :: (Monad m, Applicative m, Ord a) => Equiv s c a -> a -> a -> STT s m () equate eq x y = equateAll eq [x,y]   {-| This function returns the descriptor of the given equivalence class. -} -desc :: (Monad m, Ord a) => Equiv s c a -> Class s c a -> STT s m c+desc :: (Monad m, Applicative m, Ord a) => Equiv s c a -> Class s c a -> STT s m c desc eq cl = do   Entry e <- classRep eq cl   liftM entryDesc $ readSTRef e@@ -319,7 +320,7 @@ {-| This function returns the descriptor of the given element's equivalence class. -} -classDesc :: (Monad m, Ord a) => Equiv s c a -> a -> STT s m c+classDesc :: (Monad m, Applicative m, Ord a) => Equiv s c a -> a -> STT s m c classDesc eq val = do   Entry e <- representative eq val   liftM entryDesc $ readSTRef e@@ -328,7 +329,7 @@ {-| This function decides whether the two given equivalence classes are the same. -} -same :: (Monad m, Ord a) => Equiv s c a -> Class s c a -> Class s c a -> STT s m Bool+same :: (Monad m, Applicative m, Ord a) => Equiv s c a -> Class s c a -> Class s c a -> STT s m Bool same eq c1 c2 = do   (Entry r1) <- classRep eq c1   (Entry r2) <- classRep eq c2@@ -338,7 +339,7 @@ same equivalence class according to the given equivalence relation representation. -} -equivalent :: (Monad m, Ord a) => Equiv s c a -> a -> a -> STT s m Bool+equivalent :: (Monad m, Applicative m, Ord a) => Equiv s c a -> a -> a -> STT s m Bool equivalent eq v1 v2 = do   (Entry r1) <- representative eq v1   (Entry r2) <- representative eq v2@@ -350,13 +351,13 @@   This function modifies the content of a reference cell.  -} -modifySTRef :: (Monad m) => STRef s a -> (a -> a) -> STT s m ()+modifySTRef :: (Monad m, Applicative m) => STRef s a -> (a -> a) -> STT s m () modifySTRef r f = readSTRef r >>= (writeSTRef r . f)   {-| This function marks the given root entry as deleted.  -} -removeEntry :: (Monad m, Ord a) => Entry s c a -> STT s m ()+removeEntry :: (Monad m, Applicative m, Ord a) => Entry s c a -> STT s m () removeEntry (Entry r) = modifySTRef r change     where change e = e {entryDeleted = True} @@ -365,7 +366,7 @@ equivalence class does not exists anymore @False@ is returned; otherwise @True@. -} -remove :: (Monad m, Ord a) => Equiv s c a -> Class s c a -> STT s m Bool+remove :: (Monad m, Applicative m, Ord a) => Equiv s c a -> Class s c a -> STT s m Bool remove eq (Class p) = do   entry <- readSTRef p   (mrepr,del) <- representative' entry@@ -388,7 +389,7 @@ element. If there is no corresponding equivalence class, @False@ is returned; otherwise @True@. -} -removeClass :: (Monad m, Ord a) => Equiv s c a -> a -> STT s m Bool+removeClass :: (Monad m, Applicative m, Ord a) => Equiv s c a -> a -> STT s m Bool removeClass eq v = do   mentry <- getEntry eq v   case mentry of