module Data.Map (
-- * Map type
- Map -- instance Eq,Show
+ Map -- instance Eq,Show,Read
-- * Operators
, (!), (\\)
) 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
-}
#if __GLASGOW_HASKELL__
+import Text.Read
import Data.Generics.Basics
import Data.Generics.Instances
#endif
-- | /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?
{--------------------------------------------------------------------
Insertion
- [insert] is the inlined version of [insertWith (\k x y -> x)]
--------------------------------------------------------------------}
-- | /O(log n)/. Insert a new key and value in the map.
+-- If the key is already present in the map, the associated value is
+-- replaced with the supplied value, i.e. 'insert' is equivalent to
+-- @'insertWith' 'const'@.
insert :: Ord k => k -> a -> Map k a -> Map k a
insert kx x t
= case t of
-- | /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.
--------------------------------------------------------------------}
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
fmap f m = map f m
{--------------------------------------------------------------------
+ Read
+--------------------------------------------------------------------}
+instance (Ord k, Read k, Read e) => Read (Map k e) where
+#ifdef __GLASGOW_HASKELL__
+ readPrec = parens $ prec 10 $ do
+ Ident "fromList" <- lexP
+ xs <- readPrec
+ return (fromList xs)
+
+ readListPrec = readListPrecDefault
+#else
+ readsPrec p = readParen (p > 10) $ \ r -> do
+ ("fromList",s) <- lex r
+ (xs,t) <- reads s
+ return (fromList xs,t)
+#endif
+
+-- parses a pair of things with the syntax a:=b
+readPair :: (Read a, Read b) => ReadS (a,b)
+readPair s = do (a, ct1) <- reads s
+ (":=", ct2) <- lex ct1
+ (b, ct3) <- reads ct2
+ return ((a,b), ct3)
+
+{--------------------------------------------------------------------
Show
--------------------------------------------------------------------}
instance (Show k, Show a) => Show (Map k a) where
- showsPrec d m = showMap (toAscList m)
+ showsPrec d m = showParen (d > 10) $
+ showString "fromList " . shows (toList m)
showMap :: (Show k,Show a) => [(k,a)] -> ShowS
showMap []
= showChar '{' . showElem x . showTail xs
where
showTail [] = showChar '}'
- showTail (x:xs) = showChar ',' . showElem x . showTail xs
+ showTail (x:xs) = showString ", " . showElem x . showTail xs
- showElem (k,x) = shows k . showString ":=" . shows x
+ showElem (k,x) = shows k . showString " := " . shows x
-- | /O(n)/. Show the tree that implements the map. The tree is shown
projects / haskell-directory.git / blobdiff