module Data.HashMap ( HashMap
, (!), (\\)
, null
, size
, member
, notMember
, lookup
, findWithDefault
, empty
, singleton
, insert
, insertWith, insertWithKey, insertLookupWithKey
, delete
, adjust
, adjustWithKey
, update
, updateWithKey
, updateLookupWithKey
, alter
, union
, unionWith
, unionWithKey
, unions
, unionsWith
, difference
, differenceWith
, differenceWithKey
, intersection
, intersectionWith
, intersectionWithKey
, map
, mapWithKey
, mapAccum
, mapAccumWithKey
, fold
, foldWithKey
, elems
, keys
, keysSet
, assocs
, toList
, fromList
, fromListWith
, fromListWithKey
, filter
, filterWithKey
, partition
, partitionWithKey
, mapMaybe
, mapMaybeWithKey
, mapEither
, mapEitherWithKey
, isSubmapOf, isSubmapOfBy
, isProperSubmapOf, isProperSubmapOfBy
) where
import Prelude hiding (lookup,map,filter,null)
import Control.Applicative (Applicative(pure,(<*>)),(<$>))
import Control.Monad ( liftM )
import Data.Hashable
import Data.Foldable (Foldable(foldMap))
import Data.List (foldl')
import Data.Maybe (fromMaybe)
import Data.Monoid (Monoid(..))
import Data.Traversable (Traversable(traverse))
import Data.Typeable
#if __GLASGOW_HASKELL__
import Text.Read
import Data.Data (Data(..), mkNoRepType)
#endif
import qualified Data.IntMap as I
import qualified Data.Map as M
import qualified Data.Set as S
(!) :: (Hashable k, Ord k) => HashMap k a -> k -> a
m ! k = case lookup k m of
Nothing -> error "HashMap.(!): key not an element of the map"
Just v -> v
(\\) :: Ord k => HashMap k a -> HashMap k b -> HashMap k a
m1 \\ m2 = difference m1 m2
newtype HashMap k v = HashMap (I.IntMap (M.Map k v)) deriving (Eq, Ord)
instance Functor (HashMap k) where
fmap = map
instance Ord k => Monoid (HashMap k a) where
mempty = empty
mappend = union
mconcat = unions
instance Foldable (HashMap k) where
foldMap f (HashMap m) = foldMap (foldMap f) m
instance Traversable (HashMap k) where
traverse f (HashMap m) = pure HashMap <*> traverse (traverse f) m
instance (Show k, Show a) => Show (HashMap k a) where
showsPrec d m = showParen (d > 10) $
showString "fromList " . shows (toList m)
instance (Read k, Hashable k, Ord k, Read a) => Read (HashMap k a) 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
#include "Typeable.h"
INSTANCE_TYPEABLE2(HashMap,hashMapTc,"HashMap")
#if __GLASGOW_HASKELL__
instance (Data k, Hashable k, Ord k, Data a) => Data (HashMap k a) where
gfoldl f z m = z fromList `f` (toList m)
toConstr _ = error "toConstr"
gunfold _ _ = error "gunfold"
dataTypeOf _ = mkNoRepType "Data.HashMap.HashMap"
dataCast1 f = gcast1 f
#endif
null :: HashMap k a -> Bool
null (HashMap m) = I.null m
size :: HashMap k a -> Int
size (HashMap m) = I.fold ((+) . M.size) 0 m
member :: (Hashable k, Ord k) => k -> HashMap k a -> Bool
member k m = case lookup k m of
Nothing -> False
Just _ -> True
notMember :: (Hashable k, Ord k) => k -> HashMap k a -> Bool
notMember k m = not $ member k m
lookup :: (Hashable k, Ord k) => k -> HashMap k a -> Maybe a
lookup k (HashMap m) = I.lookup (hash k) m >>= M.lookup k
findWithDefault :: (Hashable k, Ord k) => a -> k -> HashMap k a -> a
findWithDefault def k m = case lookup k m of
Nothing -> def
Just x -> x
empty :: HashMap k a
empty = HashMap I.empty
singleton :: Hashable k => k -> a -> HashMap k a
singleton k x = HashMap $
I.singleton (hash k) $ M.singleton k x
insert :: (Hashable k, Ord k)
=> k -> a -> HashMap k a -> HashMap k a
insert k x (HashMap m) = HashMap $
I.insertWith (\_ -> M.insert k x) (hash k) (M.singleton k x) m
insertWith :: (Hashable k, Ord k)
=> (a -> a -> a) -> k -> a -> HashMap k a -> HashMap k a
insertWith f k x (HashMap m) = HashMap $
I.insertWith (\_ -> M.insertWith f k x) (hash k) (M.singleton k x) m
insertWithKey :: (Hashable k, Ord k)
=> (k -> a -> a -> a) -> k -> a -> HashMap k a -> HashMap k a
insertWithKey f k x (HashMap m) = HashMap $
I.insertWith (\_ -> M.insertWithKey f k x) (hash k) (M.singleton k x) m
insertLookupWithKey :: (Hashable k, Ord k)
=> (k -> a -> a -> a) -> k -> a -> HashMap k a -> (Maybe a, HashMap k a)
insertLookupWithKey f k x (HashMap m) =
case I.insertLookupWithKey (\_ _ -> M.insertWithKey f k x) (hash k) (M.singleton k x) m of
(found, insert) -> (found >>= M.lookup k, HashMap insert)
nonempty :: M.Map k a -> Maybe (M.Map k a)
nonempty m | M.null m = Nothing
| otherwise = Just m
delete :: (Hashable k, Ord k)
=> k -> HashMap k a -> HashMap k a
delete k (HashMap m) = HashMap $
I.update (nonempty . M.delete k) (hash k) m
adjust :: (Hashable k, Ord k)
=> (a -> a) -> k -> HashMap k a -> HashMap k a
adjust f k (HashMap m) = HashMap $
I.adjust (M.adjust f k) (hash k) m
adjustWithKey :: (Hashable k, Ord k)
=> (k -> a -> a) -> k -> HashMap k a -> HashMap k a
adjustWithKey f k (HashMap m) = HashMap $
I.adjust (M.adjustWithKey f k) (hash k) m
update :: (Hashable k, Ord k)
=> (a -> Maybe a) -> k -> HashMap k a -> HashMap k a
update f k (HashMap m) = HashMap $
I.update (nonempty . M.update f k) (hash k) m
updateWithKey :: (Hashable k, Ord k)
=> (k -> a -> Maybe a) -> k -> HashMap k a -> HashMap k a
updateWithKey f k (HashMap m) = HashMap $
I.update (nonempty . M.updateWithKey f k) (hash k) m
updateLookupWithKey :: (Hashable k, Ord k)
=> (k -> a -> Maybe a) -> k -> HashMap k a -> (Maybe a, HashMap k a)
updateLookupWithKey f k (HashMap m) =
case I.updateLookupWithKey (\_ -> nonempty . M.updateWithKey f k) (hash k) m of
(found, update) -> (found >>= M.lookup k, HashMap update)
alter :: (Hashable k, Ord k)
=> (Maybe a -> Maybe a) -> k -> HashMap k a -> HashMap k a
alter f k (HashMap m) = HashMap $
I.alter (nonempty . M.alter f k . fromMaybe M.empty) (hash k) m
unions :: Ord k => [HashMap k a] -> HashMap k a
unions xs = foldl' union empty xs
unionsWith :: Ord k => (a->a->a) -> [HashMap k a] -> HashMap k a
unionsWith f xs = foldl' (unionWith f) empty xs
union :: Ord k => HashMap k a -> HashMap k a -> HashMap k a
union (HashMap m1) (HashMap m2) = HashMap $
I.unionWith M.union m1 m2
unionWith :: Ord k => (a -> a -> a) -> HashMap k a -> HashMap k a -> HashMap k a
unionWith f (HashMap m1) (HashMap m2) = HashMap $
I.unionWith (M.unionWith f) m1 m2
unionWithKey :: Ord k => (k -> a -> a -> a) -> HashMap k a -> HashMap k a -> HashMap k a
unionWithKey f (HashMap m1) (HashMap m2) = HashMap $
I.unionWith (M.unionWithKey f) m1 m2
difference :: Ord k => HashMap k a -> HashMap k b -> HashMap k a
difference (HashMap m1) (HashMap m2) = HashMap $
I.differenceWith (\n1 n2 -> nonempty $ M.difference n1 n2) m1 m2
differenceWith :: Ord k => (a -> b -> Maybe a) -> HashMap k a -> HashMap k b -> HashMap k a
differenceWith f (HashMap m1) (HashMap m2) = HashMap $
I.differenceWith (\n1 n2 -> nonempty $ M.differenceWith f n1 n2) m1 m2
differenceWithKey :: Ord k => (k -> a -> b -> Maybe a) -> HashMap k a -> HashMap k b -> HashMap k a
differenceWithKey f (HashMap m1) (HashMap m2) = HashMap $
I.differenceWith (\n1 n2 -> nonempty $ M.differenceWithKey f n1 n2) m1 m2
delete_empty :: I.IntMap (M.Map k a) -> I.IntMap (M.Map k a)
delete_empty = I.filter (not . M.null)
intersection :: Ord k => HashMap k a -> HashMap k b -> HashMap k a
intersection (HashMap m1) (HashMap m2) = HashMap $ delete_empty $
I.intersectionWith M.intersection m1 m2
intersectionWith :: Ord k => (a -> b -> c) -> HashMap k a -> HashMap k b -> HashMap k c
intersectionWith f (HashMap m1) (HashMap m2) = HashMap $ delete_empty $
I.intersectionWith (M.intersectionWith f) m1 m2
intersectionWithKey :: Ord k => (k -> a -> b -> c) -> HashMap k a -> HashMap k b -> HashMap k c
intersectionWithKey f (HashMap m1) (HashMap m2) = HashMap $ delete_empty $
I.intersectionWith (M.intersectionWithKey f) m1 m2
isProperSubmapOf :: (Ord k, Eq a) => HashMap k a -> HashMap k a -> Bool
isProperSubmapOf m1 m2 = isSubmapOf m1 m2 && size m1 < size m2
isProperSubmapOfBy :: Ord k => (a -> b -> Bool) -> HashMap k a -> HashMap k b -> Bool
isProperSubmapOfBy f m1 m2 = isSubmapOfBy f m1 m2 && size m1 < size m2
isSubmapOf :: (Ord k, Eq a) => HashMap k a -> HashMap k a -> Bool
isSubmapOf (HashMap m1) (HashMap m2) =
I.isSubmapOfBy (M.isSubmapOf) m1 m2
isSubmapOfBy :: Ord k => (a -> b -> Bool) -> HashMap k a -> HashMap k b -> Bool
isSubmapOfBy f (HashMap m1) (HashMap m2) =
I.isSubmapOfBy (M.isSubmapOfBy f) m1 m2
map :: (a -> b) -> HashMap k a -> HashMap k b
map f (HashMap m) = HashMap $
I.map (M.map f) m
mapWithKey :: (k -> a -> b) -> HashMap k a -> HashMap k b
mapWithKey f (HashMap m) = HashMap $
I.map (M.mapWithKey f) m
mapAccum :: (a -> b -> (a,c)) -> a -> HashMap k b -> (a,HashMap k c)
mapAccum f a (HashMap m) =
case I.mapAccum (M.mapAccum f) a m of
(acc, m) -> (acc, HashMap m)
mapAccumWithKey :: (a -> k -> b -> (a,c)) -> a -> HashMap k b -> (a,HashMap k c)
mapAccumWithKey f a (HashMap m) =
case I.mapAccum (M.mapAccumWithKey f) a m of
(acc, m) -> (acc, HashMap m)
filter :: Ord k => (a -> Bool) -> HashMap k a -> HashMap k a
filter p (HashMap m) = HashMap $
I.mapMaybe (nonempty . M.filter p) m
filterWithKey :: Ord k => (k -> a -> Bool) -> HashMap k a -> HashMap k a
filterWithKey p (HashMap m) = HashMap $
I.mapMaybe (nonempty . M.filterWithKey p) m
partition :: Ord k => (a -> Bool) -> HashMap k a -> (HashMap k a, HashMap k a)
partition p m = (mapMaybe (maybe_true p) m, mapMaybe (maybe_false p) m)
partitionWithKey :: Ord k => (k -> a -> Bool) -> HashMap k a -> (HashMap k a, HashMap k a)
partitionWithKey p m = (mapMaybeWithKey (\k -> maybe_true (p k)) m
,mapMaybeWithKey (\k -> maybe_false (p k)) m)
mapMaybe :: Ord k => (a -> Maybe b) -> HashMap k a -> HashMap k b
mapMaybe f (HashMap m) = HashMap $
I.mapMaybe (nonempty . M.mapMaybe f) m
mapMaybeWithKey :: Ord k => (k -> a -> Maybe b) -> HashMap k a -> HashMap k b
mapMaybeWithKey f (HashMap m) = HashMap $
I.mapMaybe (nonempty . M.mapMaybeWithKey f) m
mapEither :: Ord k => (a -> Either b c) -> HashMap k a -> (HashMap k b, HashMap k c)
mapEither f m = (mapMaybe (maybe_left . f) m, mapMaybe (maybe_right . f) m)
mapEitherWithKey :: Ord k => (k -> a -> Either b c) -> HashMap k a -> (HashMap k b, HashMap k c)
mapEitherWithKey f m = (mapMaybeWithKey (\k a -> maybe_left (f k a)) m
,mapMaybeWithKey (\k a -> maybe_right (f k a)) m)
maybe_left (Left a) = Just a
maybe_left (Right _) = Nothing
maybe_right (Right a) = Just a
maybe_right (Left _) = Nothing
maybe_true p a = if p a then Just a else Nothing
maybe_false p a = if p a then Nothing else Just a
fold :: (a -> b -> b) -> b -> HashMap k a -> b
fold f z (HashMap m) = I.fold (flip $ M.fold f) z m
foldWithKey :: (k -> a -> b -> b) -> b -> HashMap k a -> b
foldWithKey f z (HashMap m) = I.fold (flip $ M.foldWithKey f) z m
elems :: HashMap k a -> [a]
elems (HashMap m) = I.fold ((++) . M.elems) [] m
keys :: HashMap k a -> [k]
keys (HashMap m) = I.fold ((++) . M.keys) [] m
keysSet :: Ord k => HashMap k a -> S.Set k
keysSet (HashMap m) = I.fold (S.union . M.keysSet) S.empty m
assocs :: HashMap k a -> [(k,a)]
assocs = toList
toList :: HashMap k a -> [(k,a)]
toList (HashMap m) =
I.fold ((++) . M.toList) [] m
fromList :: (Hashable k, Ord k)
=> [(k,a)] -> HashMap k a
fromList xs = foldl' (\m (k, v) -> insert k v m) empty xs
fromListWith :: (Hashable k, Ord k) => (a -> a -> a) -> [(k,a)] -> HashMap k a
fromListWith f xs = foldl' (\m (k, v) -> insertWith f k v m) empty xs
fromListWithKey :: (Hashable k, Ord k) => (k -> a -> a -> a) -> [(k,a)] -> HashMap k a
fromListWithKey f xs = foldl' (\m (k, v) -> insertWithKey f k v m) empty xs