[project @ 2005-11-29 14:31:59 by ross]

[ghc-base.git] / Data / Set.hs

diff --git a/Data/Set.hs b/Data/Set.hs
index 7e07fbe..fe3b0b4 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,9 +112,10 @@ module Data.Set  (
             ) where
 
 import Prelude hiding (filter,foldr,null,map)
-import Data.Monoid
 import qualified Data.List as List
+import Data.Monoid (Monoid(..))
 import Data.Typeable
+import Data.Foldable (Foldable(foldMap))
 
 {-
 -- just for testing
@@ -124,6 +125,7 @@ import qualified List
 -}
 
 #if __GLASGOW_HASKELL__
+import Text.Read
 import Data.Generics.Basics
 import Data.Generics.Instances
 #endif
@@ -146,6 +148,15 @@ data Set a    = Tip
 
 type Size     = Int
 
+instance Ord a => Monoid (Set a) where
+    mempty  = empty
+    mappend = union
+    mconcat = unions
+
+instance Foldable Set where
+    foldMap f Tip = mempty
+    foldMap f (Bin _s k l r) = foldMap f l `mappend` f k `mappend` foldMap f r
+
 #if __GLASGOW_HASKELL__
 
 {--------------------------------------------------------------------
@@ -208,6 +219,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 +303,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
@@ -427,7 +442,7 @@ elems s
 {--------------------------------------------------------------------
   Lists 
 --------------------------------------------------------------------}
--- | /O(n)/. Convert the set to an ascending list of elements.
+-- | /O(n)/. Convert the set to a list of elements.
 toList :: Set a -> [a]
 toList s
   = toAscList s
@@ -506,19 +521,11 @@ 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
-  showsPrec d s  = showSet (toAscList s)
+  showsPrec p xs = showParen (p > 10) $
+    showString "fromList " . shows (toList xs)
 
 showSet :: (Show a) => [a] -> ShowS
 showSet []     
@@ -528,7 +535,24 @@ showSet (x:xs)
   where
     showTail []     = showChar '}'
     showTail (x:xs) = showChar ',' . shows x . showTail xs
-    
+
+{--------------------------------------------------------------------
+  Read
+--------------------------------------------------------------------}
+instance (Read a, Ord a) => Read (Set a) where
+#ifdef __GLASGOW_HASKELL__
+  readPrec = parens $ prec 10 $ do
+    Ident "fromList" <- lexP
+    xs <- readPrec
+    return (fromList xs)
+
+  readListPrec = readListPrecDefault
+#else
+  readsPrec p = readParen (p > 10) $ \ r -> do
+    ("fromList",s) <- lex r
+    (xs,t) <- reads s
+    return (fromList xs,t)
+#endif
 
 {--------------------------------------------------------------------
   Typeable/Data