From 06b9bd7ae1f3c9aa955086bb855f99116255af13 Mon Sep 17 00:00:00 2001
From: malcolm <unknown>
Date: Wed, 26 Jan 2005 14:36:42 +0000
Subject: [PATCH] [project @ 2005-01-26 14:36:42 by malcolm] Patch from John
 Meacham: Generalise a couple functions in Data.Map to be
 usable in an arbitrary monad (rather than being restricted
 to Maybe).

---
 Data/Map.hs |   19 ++++++++++++-------
 1 file changed, 12 insertions(+), 7 deletions(-)

diff --git a/Data/Map.hs b/Data/Map.hs
index b92bc36..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)
-- 
1.7.10.4