[project @ 2005-10-13 10:36:42 by ross]

[haskell-directory.git] / Data / Set.hs

diff --git a/Data/Set.hs b/Data/Set.hs
index 4b1e3a9..33641de 100644 (file)
--- a/Data/Set.hs
+++ b/Data/Set.hs
@@ -34,7 +34,7 @@
 
 module Data.Set  ( 
             -- * Set type
-              Set          -- instance Eq,Show
+              Set          -- instance Eq,Ord,Show,Read,Data,Typeable
 
             -- * Operators
             , (\\)
@@ -112,7 +112,6 @@ module Data.Set  (
             ) where
 
 import Prelude hiding (filter,foldr,null,map)
-import Data.Monoid
 import qualified Data.List as List
 import Data.Typeable
 
@@ -208,6 +207,8 @@ singleton x
   Insertion, Deletion
 --------------------------------------------------------------------}
 -- | /O(log n)/. Insert an element in a set.
+-- If the set already contains an element equal to the given value,
+-- it is replaced with the new value.
 insert :: Ord a => a -> Set a -> Set a
 insert x t
   = case t of
@@ -290,7 +291,9 @@ unions ts
   = foldlStrict union empty ts
 
 
--- | /O(n+m)/. The union of two sets. Uses the efficient /hedge-union/ algorithm.
+-- | /O(n+m)/. The union of two sets, preferring the first set when
+-- equal elements are encountered.
+-- The implementation uses the efficient /hedge-union/ algorithm.
 -- Hedge-union is more efficient on (bigset `union` smallset).
 union :: Ord a => Set a -> Set a -> Set a
 union Tip t2  = t2
@@ -506,15 +509,6 @@ instance Ord a => Ord (Set a) where
     compare s1 s2 = compare (toAscList s1) (toAscList s2) 
 
 {--------------------------------------------------------------------
-  Monoid 
---------------------------------------------------------------------}
-
-instance Ord a => Monoid (Set a) where
-    mempty = empty
-    mappend = union
-    mconcat = unions
-
-{--------------------------------------------------------------------
   Show
 --------------------------------------------------------------------}
 instance Show a => Show (Set a) where
@@ -528,9 +522,23 @@ showSet (x:xs)
   where
     showTail []     = showChar '}'
     showTail (x:xs) = showChar ',' . shows x . showTail xs
-    
 
 {--------------------------------------------------------------------
+  Read
+--------------------------------------------------------------------}
+instance (Read a, Ord a) => Read (Set a) where
+  readsPrec _ = readParen False $ \ r ->
+            [(fromList xs,t)     | ("{",s) <- lex r,
+                                   (xs,t)  <- readl s]
+      where readl s  = [([],t)   | ("}",t) <- lex s] ++
+                       [(x:xs,u) | (x,t)   <- reads s
+                                 , (xs,u)  <- readl' t]
+            readl' s = [([],t)   | ("}",t) <- lex s] ++
+                       [(x:xs,v) | (",",t) <- lex s
+                                 , (x,u)   <- reads t
+                                 , (xs,v)  <- readl' u]
+    
+{--------------------------------------------------------------------
   Typeable/Data
 --------------------------------------------------------------------}