) 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
-- | /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?
-- | /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)
- 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.
compare m1 m2 = compare (toList m1) (toList m2)
{--------------------------------------------------------------------
- Monoid
---------------------------------------------------------------------}
-
-instance (Ord k) => Monoid (Map k v) where
- mempty = empty
- mappend = union
- mconcat = unions
-
-{--------------------------------------------------------------------
Functor
--------------------------------------------------------------------}
instance Functor (Map k) where