[project @ 2005-03-30 11:15:21 by simonmar]

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

diff --git a/Data/Map.hs b/Data/Map.hs
index b92bc36..d89ab6a 100644 (file)
--- a/Data/Map.hs
+++ b/Data/Map.hs
@@ -148,7 +148,6 @@ 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.Typeable
@@ -225,14 +224,18 @@ size t
 
 
 -- | /O(log n)/. Lookup the value at a key in the map.
-lookup :: Ord k => k -> Map k a -> Maybe a
-lookup k t
+lookup :: (Monad m,Ord k) => k -> Map k a -> m a
+lookup k t = case lookup' k t of
+    Just x -> return x
+    Nothing -> fail "Data.Map.lookup: Key not found"
+lookup' :: Ord k => k -> Map k a -> Maybe a
+lookup' k t
   = case t of
       Tip -> Nothing
       Bin sz kx x l r
           -> case compare k kx of
-               LT -> lookup k l
-               GT -> lookup k r
+               LT -> lookup' k l
+               GT -> lookup' k r
                EQ -> Just x       
 
 -- | /O(log n)/. Is the key a member of the map?
@@ -395,9 +398,10 @@ findIndex k t
 
 -- | /O(log n)/. Lookup the /index/ of a key. The index is a number from
 -- /0/ up to, but not including, the 'size' of the map. 
-lookupIndex :: Ord k => k -> Map k a -> Maybe Int
-lookupIndex k t
-  = lookup 0 t
+lookupIndex :: (Monad m,Ord k) => k -> Map k a -> m Int
+lookupIndex k t = case lookup 0 t of
+    Nothing -> fail "Data.Map.lookupIndex: Key not found."
+    Just x -> return x
   where
     lookup idx Tip  = Nothing
     lookup idx (Bin _ kx x l r)
@@ -1227,7 +1231,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.
@@ -1290,16 +1294,7 @@ 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)
-
-{--------------------------------------------------------------------
-  Monoid 
---------------------------------------------------------------------}
-
-instance (Ord k) => Monoid (Map k v) where
-    mempty = empty
-    mappend = union
-    mconcat = unions
+    compare m1 m2 = compare (toAscList m1) (toAscList m2)
 
 {--------------------------------------------------------------------
   Functor