) 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)
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
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' (==)@).
-- | /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.
- 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.
--------------------------------------------------------------------}
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