specialize functions that fail in a Monad to Maybe (proposal #2309)
authorRoss Paterson <ross@soi.city.ac.uk>
Tue, 22 Jul 2008 15:48:12 +0000 (15:48 +0000)
committerRoss Paterson <ross@soi.city.ac.uk>
Tue, 22 Jul 2008 15:48:12 +0000 (15:48 +0000)
Specialize functions signatures like

lookup :: (Monad m, Ord k) => k -> Map k a -> m a
to
lookup :: (Ord k) => k -> Map k a -> Maybe a

for simplicity and safety.  No information is lost, as each of these
functions had only one use of fail, which is now changed to Nothing.

Data/IntMap.hs
Data/IntSet.hs
Data/Map.hs
Data/Set.hs

index 8eb1982..b3aa985 100644 (file)
@@ -165,6 +165,7 @@ import Prelude hiding (lookup,map,filter,foldr,foldl,null)
 import Data.Bits 
 import qualified Data.IntSet as IntSet
 import Data.Monoid (Monoid(..))
+import Data.Maybe (fromMaybe)
 import Data.Typeable
 import Data.Foldable (Foldable(foldMap))
 import Control.Monad ( liftM )
@@ -314,13 +315,8 @@ notMember :: Key -> IntMap a -> Bool
 notMember k m = not $ member k m
 
 -- | /O(min(n,W))/. Lookup the value at a key in the map. See also 'Data.Map.lookup'.
-lookup :: (Monad m) => Key -> IntMap a -> m a
-lookup k t = case lookup' k t of
-    Just x -> return x
-    Nothing -> fail "Data.IntMap.lookup: Key not found"
-
-lookup' :: Key -> IntMap a -> Maybe a
-lookup' k t
+lookup :: Key -> IntMap a -> Maybe a
+lookup k t
   = let nk = natFromInt k  in seq nk (lookupN nk t)
 
 lookupN :: Nat -> IntMap a -> Maybe a
@@ -873,20 +869,19 @@ updateMaxWithKeyUnsigned f t
         Nil -> error "updateMaxWithKeyUnsigned Nil"
 
 
--- | /O(log n)/. Retrieves the maximal (key,value) couple of the map, and the map stripped from that element.
--- @fail@s (in the monad) when passed an empty map.
+-- | /O(log n)/. Retrieves the maximal (key,value) pair of the map, and
+-- the map stripped of that element, or 'Nothing' if passed an empty map.
 --
--- > v <- maxViewWithKey (fromList [(5,"a"), (3,"b")])
--- > v == ((5,"a"), singleton 3 "b")
--- > maxViewWithKey empty              Error: empty map
+-- > maxViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((5,"a"), singleton 3 "b")
+-- > maxViewWithKey empty == Nothing
 
-maxViewWithKey :: (Monad m) => IntMap a -> m ((Key, a), IntMap a)
+maxViewWithKey :: IntMap a -> Maybe ((Key, a), IntMap a)
 maxViewWithKey t
     = case t of
-        Bin p m l r | m < 0 -> let (result, t') = maxViewUnsigned l in return (result, bin p m t' r)
-        Bin p m l r         -> let (result, t') = maxViewUnsigned r in return (result, bin p m l t')
-        Tip k y -> return ((k,y), Nil)
-        Nil -> fail "maxViewWithKey: empty map has no maximal element"
+        Bin p m l r | m < 0 -> let (result, t') = maxViewUnsigned l in Just (result, bin p m t' r)
+        Bin p m l r         -> let (result, t') = maxViewUnsigned r in Just (result, bin p m l t')
+        Tip k y -> Just ((k,y), Nil)
+        Nil -> Nothing
 
 maxViewUnsigned :: IntMap a -> ((Key, a), IntMap a)
 maxViewUnsigned t 
@@ -895,20 +890,19 @@ maxViewUnsigned t
         Tip k y -> ((k,y), Nil)
         Nil -> error "maxViewUnsigned Nil"
 
--- | /O(log n)/. Retrieves the minimal (key,value) couple of the map, and the map stripped from that element.
--- @fail@s (in the monad) when passed an empty map.
+-- | /O(log n)/. Retrieves the minimal (key,value) pair of the map, and
+-- the map stripped of that element, or 'Nothing' if passed an empty map.
 --
--- > v <- minViewWithKey (fromList [(5,"a"), (3,"b")])
--- > v ==  ((3,"b"), singleton 5 "a")
--- > minViewWithKey empty              Error: empty map
+-- > minViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((3,"b"), singleton 5 "a")
+-- > minViewWithKey empty == Nothing
 
-minViewWithKey :: (Monad m) => IntMap a -> m ((Key, a), IntMap a)
+minViewWithKey :: IntMap a -> Maybe ((Key, a), IntMap a)
 minViewWithKey t
     = case t of
-        Bin p m l r | m < 0 -> let (result, t') = minViewUnsigned r in return (result, bin p m l t')
-        Bin p m l r         -> let (result, t') = minViewUnsigned l in return (result, bin p m t' r)
-        Tip k y -> return ((k,y),Nil)
-        Nil -> fail "minViewWithKey: empty map has no minimal element"
+        Bin p m l r | m < 0 -> let (result, t') = minViewUnsigned r in Just (result, bin p m l t')
+        Bin p m l r         -> let (result, t') = minViewUnsigned l in Just (result, bin p m t' r)
+        Tip k y -> Just ((k,y),Nil)
+        Nil -> Nothing
 
 minViewUnsigned :: IntMap a -> ((Key, a), IntMap a)
 minViewUnsigned t 
@@ -934,50 +928,43 @@ updateMax f = updateMaxWithKey (const f)
 updateMin :: (a -> a) -> IntMap a -> IntMap a
 updateMin f = updateMinWithKey (const f)
 
-
--- Duplicate the Identity monad here because base < mtl.
-newtype Identity a = Identity { runIdentity :: a }
-instance Monad Identity where
-       return a = Identity a
-       m >>= k  = k (runIdentity m)
 -- Similar to the Arrow instance.
 first :: (a -> c) -> (a, b) -> (c, b)
 first f (x,y) = (f x,y)
 
-
--- | /O(log n)/. Retrieves the maximal key of the map, and the map stripped from that element.
--- @fail@s (in the monad) when passed an empty map.
-maxView :: (Monad m) => IntMap a -> m (a, IntMap a)
+-- | /O(log n)/. Retrieves the maximal key of the map, and the map
+-- stripped of that element, or 'Nothing' if passed an empty map.
+maxView :: IntMap a -> Maybe (a, IntMap a)
 maxView t = liftM (first snd) (maxViewWithKey t)
 
--- | /O(log n)/. Retrieves the minimal key of the map, and the map stripped from that element.
--- @fail@s (in the monad) when passed an empty map.
-minView :: (Monad m) => IntMap a -> m (a, IntMap a)
+-- | /O(log n)/. Retrieves the minimal key of the map, and the map
+-- stripped of that element, or 'Nothing' if passed an empty map.
+minView :: IntMap a -> Maybe (a, IntMap a)
 minView t = liftM (first snd) (minViewWithKey t)
 
 -- | /O(log n)/. Delete and find the maximal element.
 deleteFindMax :: IntMap a -> (a, IntMap a)
-deleteFindMax = runIdentity . maxView
+deleteFindMax = fromMaybe (error "deleteFindMax: empty map has no maximal element") . maxView
 
 -- | /O(log n)/. Delete and find the minimal element.
 deleteFindMin :: IntMap a -> (a, IntMap a)
-deleteFindMin = runIdentity . minView
+deleteFindMin = fromMaybe (error "deleteFindMin: empty map has no minimal element") . minView
 
 -- | /O(log n)/. The minimal key of the map.
 findMin :: IntMap a -> a
-findMin = fst . runIdentity . minView
+findMin = maybe (error "findMin: empty map has no minimal element") fst . minView
 
 -- | /O(log n)/. The maximal key of the map.
 findMax :: IntMap a -> a
-findMax = fst . runIdentity . maxView
+findMax = maybe (error "findMax: empty map has no maximal element") fst . maxView
 
 -- | /O(log n)/. Delete the minimal key.
 deleteMin :: IntMap a -> IntMap a
-deleteMin = snd . runIdentity . minView
+deleteMin = maybe (error "deleteMin: empty map has no minimal element") snd . minView
 
 -- | /O(log n)/. Delete the maximal key.
 deleteMax :: IntMap a -> IntMap a
-deleteMax = snd . runIdentity . maxView
+deleteMax = maybe (error "deleteMax: empty map has no maximal element") snd . maxView
 
 
 {--------------------------------------------------------------------
index 9662928..61ee962 100644 (file)
@@ -106,6 +106,7 @@ import Data.Bits
 
 import qualified Data.List as List
 import Data.Monoid (Monoid(..))
+import Data.Maybe (fromMaybe)
 import Data.Typeable
 
 {-
@@ -545,15 +546,15 @@ splitMember' x t
   Min/Max
 ----------------------------------------------------------------------}
 
--- | /O(min(n,W))/. Retrieves the maximal key of the set, and the set stripped from that element
--- @fail@s (in the monad) when passed an empty set.
-maxView :: (Monad m) => IntSet -> m (Int, IntSet)
+-- | /O(min(n,W))/. Retrieves the maximal key of the set, and the set
+-- stripped of that element, or 'Nothing' if passed an empty set.
+maxView :: IntSet -> Maybe (Int, IntSet)
 maxView t
     = case t of
-        Bin p m l r | m < 0 -> let (result,t') = maxViewUnsigned l in return (result, bin p m t' r)
-        Bin p m l r         -> let (result,t') = maxViewUnsigned r in return (result, bin p m l t')            
-        Tip y -> return (y,Nil)
-        Nil -> fail "maxView: empty set has no maximal element"
+        Bin p m l r | m < 0 -> let (result,t') = maxViewUnsigned l in Just (result, bin p m t' r)
+        Bin p m l r         -> let (result,t') = maxViewUnsigned r in Just (result, bin p m l t')            
+        Tip y -> Just (y,Nil)
+        Nil -> Nothing
 
 maxViewUnsigned :: IntSet -> (Int, IntSet)
 maxViewUnsigned t 
@@ -562,15 +563,15 @@ maxViewUnsigned t
         Tip y -> (y, Nil)
         Nil -> error "maxViewUnsigned Nil"
 
--- | /O(min(n,W))/. Retrieves the minimal key of the set, and the set stripped from that element
--- @fail@s (in the monad) when passed an empty set.
-minView :: (Monad m) => IntSet -> m (Int, IntSet)
+-- | /O(min(n,W))/. Retrieves the minimal key of the set, and the set
+-- stripped of that element, or 'Nothing' if passed an empty set.
+minView :: IntSet -> Maybe (Int, IntSet)
 minView t
     = case t of
-        Bin p m l r | m < 0 -> let (result,t') = minViewUnsigned r in return (result, bin p m l t')            
-        Bin p m l r         -> let (result,t') = minViewUnsigned l in return (result, bin p m t' r)
-        Tip y -> return (y, Nil)
-        Nil -> fail "minView: empty set has no minimal element"
+        Bin p m l r | m < 0 -> let (result,t') = minViewUnsigned r in Just (result, bin p m l t')            
+        Bin p m l r         -> let (result,t') = minViewUnsigned l in Just (result, bin p m t' r)
+        Tip y -> Just (y, Nil)
+        Nil -> Nothing
 
 minViewUnsigned :: IntSet -> (Int, IntSet)
 minViewUnsigned t 
@@ -579,43 +580,33 @@ minViewUnsigned t
         Tip y -> (y, Nil)
         Nil -> error "minViewUnsigned Nil"
 
-
--- Duplicate the Identity monad here because base < mtl.
-newtype Identity a = Identity { runIdentity :: a }
-instance Monad Identity where
-       return a = Identity a
-       m >>= k  = k (runIdentity m)
-
-
 -- | /O(min(n,W))/. Delete and find the minimal element.
 -- 
 -- > deleteFindMin set = (findMin set, deleteMin set)
 deleteFindMin :: IntSet -> (Int, IntSet)
-deleteFindMin = runIdentity . minView
+deleteFindMin = fromMaybe (error "deleteFindMin: empty set has no minimal element") . minView
 
 -- | /O(min(n,W))/. Delete and find the maximal element.
 -- 
 -- > deleteFindMax set = (findMax set, deleteMax set)
 deleteFindMax :: IntSet -> (Int, IntSet)
-deleteFindMax = runIdentity . maxView
+deleteFindMax = fromMaybe (error "deleteFindMax: empty set has no maximal element") . maxView
 
 -- | /O(min(n,W))/. The minimal element of a set.
 findMin :: IntSet -> Int
-findMin = fst . runIdentity . minView
+findMin = maybe (error "findMin: empty set has no minimal element") fst . minView
 
 -- | /O(min(n,W))/. The maximal element of a set.
 findMax :: IntSet -> Int
-findMax = fst . runIdentity . maxView
+findMax = maybe (error "findMax: empty set has no maximal element") fst . maxView
 
 -- | /O(min(n,W))/. Delete the minimal element.
 deleteMin :: IntSet -> IntSet
-deleteMin = snd . runIdentity . minView
+deleteMin = maybe (error "deleteMin: empty set has no minimal element") snd . minView
 
 -- | /O(min(n,W))/. Delete the maximal element.
 deleteMax :: IntSet -> IntSet
-deleteMax = snd . runIdentity . maxView
-
-
+deleteMax = maybe (error "deleteMax: empty set has no maximal element") snd . maxView
 
 {----------------------------------------------------------------------
   Map
index 1009a4e..2ecf708 100644 (file)
@@ -276,19 +276,10 @@ size t
 
 -- | /O(log n)/. Lookup the value at a key in the map.
 --
--- The function will 
--- @return@ the result in the monad or @fail@ in it the key isn't in the 
--- map. Often, the monad to use is 'Maybe', so you get either 
--- @('Just' result)@ or @'Nothing'@.
+-- The function will return the corresponding value as @('Just' value)@,
+-- or 'Nothing' if the key isn't in the map.
 --
--- > let m = fromList [(5,'a'), (3,'b'), (7,'c')]
--- > value1 <- Data.Map.lookup 5 m
--- > value1
--- >   'a'
--- > value2 <- Data.Map.lookup 1 m
--- >   Error: Key not found
---
--- An example of using @lookup@ with @Maybe@ monad:
+-- An example of using @lookup@:
 --
 -- > import Prelude hiding (lookup)
 -- > import Data.Map
@@ -312,18 +303,14 @@ size t
 -- >   John's currency: Just "Euro"
 -- >   Pete's currency: Nothing
 
-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
+lookup :: Ord k => k -> Map k a -> Maybe a
+lookup k t
   = case t of
       Tip -> Nothing
       Bin _ 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       
 
 lookupAssoc :: Ord k => k -> Map k a -> Maybe (k,a)
@@ -654,10 +641,8 @@ findIndex k t
 -- > fromJust (lookupIndex 5 (fromList [(5,"a"), (3,"b")])) == 1
 -- > isJust (lookupIndex 6 (fromList [(5,"a"), (3,"b")]))   == False
 
-lookupIndex :: (Monad m,Ord k) => k -> Map k a -> m Int
-lookupIndex k t = case f 0 t of
-    Nothing -> fail "Data.Map.lookupIndex: Key not found."
-    Just x -> return x
+lookupIndex :: Ord k => k -> Map k a -> Maybe Int
+lookupIndex k t = f 0 t
   where
     f _   Tip  = Nothing
     f idx (Bin _ kx _ l r)
@@ -810,49 +795,46 @@ updateMaxWithKey f t
       Bin _ kx x l r     -> balance kx x l (updateMaxWithKey f r)
       Tip                -> Tip
 
--- | /O(log n)/. Retrieves the minimal (key,value) pair of the map, and the map stripped from that element
--- @fail@s (in the monad) when passed an empty map.
+-- | /O(log n)/. Retrieves the minimal (key,value) pair of the map, and
+-- the map stripped of that element, or 'Nothing' if passed an empty map.
 --
--- > v <- minViewWithKey (fromList [(5,"a"), (3,"b")])
--- > v ==  ((3,"b"), singleton 5 "a")
--- > minViewWithKey empty              Error: empty map
+-- > minViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((3,"b"), singleton 5 "a")
+-- > minViewWithKey empty == Nothing
 
-minViewWithKey :: Monad m => Map k a -> m ((k,a), Map k a)
-minViewWithKey Tip = fail "Map.minViewWithKey: empty map"
-minViewWithKey x = return (deleteFindMin x)
+minViewWithKey :: Map k a -> Maybe ((k,a), Map k a)
+minViewWithKey Tip = Nothing
+minViewWithKey x = Just (deleteFindMin x)
 
--- | /O(log n)/. Retrieves the maximal (key,value) pair of the map, and the map stripped from that element
--- @fail@s (in the monad) when passed an empty map.
+-- | /O(log n)/. Retrieves the maximal (key,value) pair of the map, and
+-- the map stripped of that element, or 'Nothing' if passed an empty map.
 --
--- > v <- maxViewWithKey (fromList [(5,"a"), (3,"b")])
--- > v == ((5,"a"), singleton 3 "b")
--- > maxViewWithKey empty              Error: empty map
+-- > maxViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((5,"a"), singleton 3 "b")
+-- > maxViewWithKey empty == Nothing
 
-maxViewWithKey :: Monad m => Map k a -> m ((k,a), Map k a)
-maxViewWithKey Tip = fail "Map.maxViewWithKey: empty map"
-maxViewWithKey x = return (deleteFindMax x)
+maxViewWithKey :: Map k a -> Maybe ((k,a), Map k a)
+maxViewWithKey Tip = Nothing
+maxViewWithKey x = Just (deleteFindMax x)
 
--- | /O(log n)/. Retrieves the minimal key\'s value of the map, and the map stripped from that element
--- @fail@s (in the monad) when passed an empty map.
+-- | /O(log n)/. Retrieves the value associated with minimal key of the
+-- map, and the map stripped of that element, or 'Nothing' if passed an
+-- empty map.
 --
--- > v <- minView (fromList [(5,"a"), (3,"b")])
--- > v == ("b", singleton 5 "a")
--- > minView empty                     Error: empty map
+-- > minView (fromList [(5,"a"), (3,"b")]) == Just ("b", singleton 5 "a")
+-- > minView empty == Nothing
 
-minView :: Monad m => Map k a -> m (a, Map k a)
-minView Tip = fail "Map.minView: empty map"
-minView x = return (first snd $ deleteFindMin x)
+minView :: Map k a -> Maybe (a, Map k a)
+minView Tip = Nothing
+minView x = Just (first snd $ deleteFindMin x)
 
--- | /O(log n)/. Retrieves the maximal key\'s value of the map, and the map stripped from that element
--- @fail@s (in the monad) when passed an empty map.
+-- | /O(log n)/. Retrieves the value associated with maximal key of the
+-- map, and the map stripped of that element, or 'Nothing' if passed an
 --
--- > v <- maxView (fromList [(5,"a"), (3,"b")]) 
--- > v == ("a", singleton 3 "b")
--- > maxView empty                     Error: empty map
+-- > maxView (fromList [(5,"a"), (3,"b")]) == Just ("a", singleton 3 "b")
+-- > maxView empty == Nothing
 
-maxView :: Monad m => Map k a -> m (a, Map k a)
-maxView Tip = fail "Map.maxView: empty map"
-maxView x = return (first snd $ deleteFindMax x)
+maxView :: Map k a -> Maybe (a, Map k a)
+maxView Tip = Nothing
+maxView x = Just (first snd $ deleteFindMax x)
 
 -- Update the 1st component of a tuple (special case of Control.Arrow.first)
 first :: (a -> b) -> (a,c) -> (b,c)
index 5f85934..a52370f 100644 (file)
@@ -770,18 +770,17 @@ deleteFindMax t
       Bin _ x l r   -> let (xm,r') = deleteFindMax r in (xm,balance x l r')
       Tip           -> (error "Set.deleteFindMax: can not return the maximal element of an empty set", Tip)
 
--- | /O(log n)/. Retrieves the minimal key of the set, and the set stripped from that element
--- @fail@s (in the monad) when passed an empty set.
-minView :: Monad m => Set a -> m (a, Set a)
-minView Tip = fail "Set.minView: empty set"
-minView x = return (deleteFindMin x)
-
--- | /O(log n)/. Retrieves the maximal key of the set, and the set stripped from that element
--- @fail@s (in the monad) when passed an empty set.
-maxView :: Monad m => Set a -> m (a, Set a)
-maxView Tip = fail "Set.maxView: empty set"
-maxView x = return (deleteFindMax x)
-
+-- | /O(log n)/. Retrieves the minimal key of the set, and the set
+-- stripped of that element, or 'Nothing' if passed an empty set.
+minView :: Set a -> Maybe (a, Set a)
+minView Tip = Nothing
+minView x = Just (deleteFindMin x)
+
+-- | /O(log n)/. Retrieves the maximal key of the set, and the set
+-- stripped of that element, or 'Nothing' if passed an empty set.
+maxView :: Set a -> Maybe (a, Set a)
+maxView Tip = Nothing
+maxView x = Just (deleteFindMax x)
 
 {--------------------------------------------------------------------
   [balance x l r] balances two trees with value x.