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

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

diff --git a/Data/Map.hs b/Data/Map.hs
index a76b62b..da12f9d 100644 (file)
--- a/Data/Map.hs
+++ b/Data/Map.hs
@@ -28,7 +28,7 @@
 
 module Data.Map  ( 
             -- * Map type
-              Map          -- instance Eq,Show
+              Map          -- instance Eq,Show,Read
 
             -- * Operators
             , (!), (\\)
@@ -148,10 +148,13 @@ module Data.Map  (
             ) where
 
 import Prelude hiding (lookup,map,filter,foldr,foldl,null)
-import Data.Monoid
 import qualified Data.Set as Set
 import qualified Data.List as List
+import Data.Monoid (Monoid(..))
 import Data.Typeable
+import Control.Applicative (Applicative(..))
+import Data.Traversable (Traversable(traverse))
+import Data.Foldable (Foldable(foldMap))
 
 {-
 -- for quick check
@@ -162,6 +165,7 @@ import List(nub,sort)
 -}
 
 #if __GLASGOW_HASKELL__
+import Text.Read
 import Data.Generics.Basics
 import Data.Generics.Instances
 #endif
@@ -189,6 +193,11 @@ data Map k a  = Tip
 
 type Size     = Int
 
+instance (Ord k) => Monoid (Map k v) where
+    mempty  = empty
+    mappend = union
+    mconcat = unions
+
 #if __GLASGOW_HASKELL__
 
 {--------------------------------------------------------------------
@@ -279,9 +288,11 @@ singleton k x
 
 {--------------------------------------------------------------------
   Insertion
-  [insert] is the inlined version of [insertWith (\k x y -> x)]
 --------------------------------------------------------------------}
 -- | /O(log n)/. Insert a new key and value in the map.
+-- If the key is already present in the map, the associated value is
+-- replaced with the supplied value, i.e. 'insert' is equivalent to
+-- @'insertWith' 'const'@.
 insert :: Ord k => k -> a -> Map k a -> Map k a
 insert kx x t
   = case t of
@@ -293,11 +304,19 @@ insert kx x t
                EQ -> Bin sz kx x l r
 
 -- | /O(log n)/. Insert with a combining function.
+-- @'insertWith' f key value mp@ 
+-- will insert the pair (key, value) into @mp@ if key does
+-- not exist in the map. If the key does exist, the function will
+-- insert @f new_value old_value@.
 insertWith :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
 insertWith f k x m          
   = insertWithKey (\k x y -> f x y) k x m
 
 -- | /O(log n)/. Insert with a combining function.
+-- @'insertWithKey' f key value mp@ 
+-- will insert the pair (key, value) into @mp@ if key does
+-- not exist in the map. If the key does exist, the function will
+-- insert @f key new_value old_value@.
 insertWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
 insertWithKey f kx x t
   = case t of
@@ -1232,7 +1251,7 @@ deleteFindMax t
   - A lower [delta] leads to a more 'perfectly' balanced tree.
   - A higher [delta] performs less rebalancing.
 
-  - Balancing is automaic for random data and a balancing
+  - Balancing is automatic for random data and a balancing
     scheme is only necessary to avoid pathological worst cases.
     Almost any choice will do, and in practice, a rather large
     [delta] may perform better than smaller one.
@@ -1295,28 +1314,55 @@ instance (Eq k,Eq a) => Eq (Map k a) where
 --------------------------------------------------------------------}
 
 instance (Ord k, Ord v) => Ord (Map k v) where
-    compare m1 m2 = compare (toList m1) (toList m2)
+    compare m1 m2 = compare (toAscList m1) (toAscList m2)
 
 {--------------------------------------------------------------------
-  Monoid 
+  Functor
 --------------------------------------------------------------------}
+instance Functor (Map k) where
+  fmap f m  = map f m
 
-instance (Ord k) => Monoid (Map k v) where
-    mempty = empty
-    mappend = union
-    mconcat = unions
+instance Traversable (Map k) where
+  traverse f Tip = pure Tip
+  traverse f (Bin s k v l r)
+    = flip (Bin s k) <$> traverse f l <*> f v <*> traverse f r
+
+instance Foldable (Map k) where
+  foldMap _f Tip = mempty
+  foldMap f (Bin _s _k v l r)
+    = foldMap f l `mappend` f v `mappend` foldMap f r
 
 {--------------------------------------------------------------------
-  Functor
+  Read
 --------------------------------------------------------------------}
-instance Functor (Map k) where
-  fmap f m  = map f m
+instance (Ord k, Read k, Read e) => Read (Map k e) 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
+
+-- parses a pair of things with the syntax a:=b
+readPair :: (Read a, Read b) => ReadS (a,b)
+readPair s = do (a, ct1)    <- reads s
+                (":=", ct2) <- lex ct1
+                (b, ct3)    <- reads ct2
+                return ((a,b), ct3)
 
 {--------------------------------------------------------------------
   Show
 --------------------------------------------------------------------}
 instance (Show k, Show a) => Show (Map k a) where
-  showsPrec d m  = showMap (toAscList m)
+  showsPrec d m  = showParen (d > 10) $
+    showString "fromList " . shows (toList m)
 
 showMap :: (Show k,Show a) => [(k,a)] -> ShowS
 showMap []     
@@ -1325,9 +1371,9 @@ showMap (x:xs)
   = showChar '{' . showElem x . showTail xs
   where
     showTail []     = showChar '}'
-    showTail (x:xs) = showChar ',' . showElem x . showTail xs
+    showTail (x:xs) = showString ", " . showElem x . showTail xs
     
-    showElem (k,x)  = shows k . showString ":=" . shows x
+    showElem (k,x)  = shows k . showString " := " . shows x
   
 
 -- | /O(n)/. Show the tree that implements the map. The tree is shown