X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=Data%2FMap.hs;h=a76b62bea5425c6ab93aa8ed1ff606f79eec0c49;hb=e9e2a5412bb7cda8d13a063ac403d9f18ac97380;hp=65a538fd625ecc99d724f08bbcd2ca1a6b9cd6fe;hpb=f3cd46e9212873a023ba04263f0c9c488e57f356;p=ghc-base.git

diff --git a/Data/Map.hs b/Data/Map.hs
index 65a538f..a76b62b 100644
--- a/Data/Map.hs
+++ b/Data/Map.hs
@@ -225,14 +225,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 +399,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)
@@ -675,7 +680,7 @@ intersectWithKey f t (Bin _ kx x l r)
       Nothing -> merge tl tr
       Just y  -> join kx (f kx y x) tl tr
   where
-    (found,lt,gt) = splitLookup kx t
+    (lt,found,gt) = splitLookup kx t
     tl            = intersectWithKey f lt l
     tr            = intersectWithKey f gt r
 
@@ -717,7 +722,7 @@ submap' f (Bin _ kx x l r) t
       Nothing -> False
       Just y  -> f x y && submap' f l lt && submap' f r gt
   where
-    (found,lt,gt) = splitLookup kx t
+    (lt,found,gt) = splitLookup kx t
 
 -- | /O(n+m)/. Is this a proper submap? (ie. a submap but not equal). 
 -- Defined as (@'isProperSubmapOf' = 'isProperSubmapOfBy' (==)@).
@@ -1104,13 +1109,13 @@ split k (Bin sx kx x l r)
 
 -- | /O(log n)/. The expression (@'splitLookup' k map@) splits a map just
 -- like 'split' but also returns @'lookup' k map@.
-splitLookup :: Ord k => k -> Map k a -> (Maybe a,Map k a,Map k a)
-splitLookup k Tip = (Nothing,Tip,Tip)
+splitLookup :: Ord k => k -> Map k a -> (Map k a,Maybe a,Map k a)
+splitLookup k Tip = (Tip,Nothing,Tip)
 splitLookup k (Bin sx kx x l r)
   = case compare k kx of
-      LT -> let (z,lt,gt) = splitLookup k l in (z,lt,join kx x gt r)
-      GT -> let (z,lt,gt) = splitLookup k r in (z,join kx x l lt,gt)
-      EQ -> (Just x,l,r)
+      LT -> let (lt,z,gt) = splitLookup k l in (lt,z,join kx x gt r)
+      GT -> let (lt,z,gt) = splitLookup k r in (join kx x l lt,z,gt)
+      EQ -> (l,Just x,r)
 
 {--------------------------------------------------------------------
   Utility functions that maintain the balance properties of the tree.