hashmap 0.9.0 → 1.0.0

raw patch · 3 files changed

+308/−23 lines, 3 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• Data/HashMap.hs +12/−15
• Data/HashSet.hs +283/−0
• hashmap.cabal +13/−8

@@ -115,8 +115,7 @@  import Prelude hiding (lookup,map,filter,null) -import Control.Applicative (Applicative(pure,(<*>)),(<$>))-import Control.Monad ( liftM )+import Control.Applicative (Applicative(pure,(<*>))) import Data.Hashable import Data.Foldable (Foldable(foldMap)) import Data.List (foldl')@@ -195,9 +194,9 @@ #include "Typeable.h" INSTANCE_TYPEABLE2(HashMap,hashMapTc,"HashMap") -#if __GLASGOW_HASKELL__  +#if __GLASGOW_HASKELL__ {--------------------------------------------------------------------   A Data instance --------------------------------------------------------------------}@@ -294,7 +293,7 @@                     => (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)+    (found, m') -> (found >>= M.lookup k, HashMap m')   {--------------------------------------------------------------------@@ -349,7 +348,7 @@                     => (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)+    (found, m') -> (found >>= M.lookup k, HashMap m')  -- | The expression (@'alter' f k map@) alters the value @x@ at @k@, or absence -- thereof.  'alter' can be used to insert, delete, or update a value in an@@ -478,14 +477,14 @@ 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)+    (acc, m') -> (acc, HashMap m')  -- | The function @'mapAccumWithKey'@ threads an accumulating argument through -- the map in unspecified order of keys. 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)+    (acc, m') -> (acc, HashMap m')   {--------------------------------------------------------------------@@ -503,16 +502,15 @@  -- | Partition the map according to some predicate. The first map contains all -- elements that satisfy the predicate, the second all elements that fail the--- predicate. See also 'split'.+-- predicate. 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)+partition p m = (filter p m, filter (not . p) m)  -- | Partition the map according to some predicate. The first map contains all -- elements that satisfy the predicate, the second all elements that fail the -- predicate. 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)+partitionWithKey p m = (filterWithKey p m, filterWithKey (\k -> not . p k) m)  -- | Map values and collect the 'Just' results. mapMaybe :: Ord k => (a -> Maybe b) -> HashMap k a -> HashMap k b@@ -534,15 +532,14 @@                        ,mapMaybeWithKey (\k a -> maybe_right (f k a)) m)  -- Helper functions for this section+maybe_left :: Either a b -> Maybe a maybe_left (Left a) = Just a maybe_left (Right _) = Nothing -maybe_right (Right a) = Just a+maybe_right :: Either a b -> Maybe b+maybe_right (Right b) = Just b 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

@@ -0,0 +1,283 @@+{-# LANGUAGE CPP #-}+{-# OPTIONS -Wall #-}++-----------------------------------------------------------------------------+-- |+-- Module      :  Data.HashSet+-- Copyright   :  (c) Milan Straka 2010+-- License     :  BSD-style+-- Maintainer  :  fox@ucw.cz+-- Stability   :  provisional+-- Portability :  portable+--+-- Persistent 'HashSet', which is defined as+--+-- @+--   data 'HashSet' e = 'Data.IntMap.IntMap' ('Data.Set.Set' e)+-- @+--+-- is an 'Data.IntMap.IntMap' indexed by hash values of elements,+-- containing a set @'Data.Set.Set' e@ with elements of the same hash values.+--+-- The interface of a 'HashSet' is a suitable subset of 'Data.IntSet.IntSet'.+--+-- The complexity of operations is determined by the complexities of+-- 'Data.IntMap.IntMap' and 'Data.Set.Set' operations. See the sources of+-- 'HashSet' to see which operations from @containers@ package are used.+-----------------------------------------------------------------------------++module Data.HashSet ( HashSet++                    -- * Operators+                    , (\\)++                    -- * Query+                    , null+                    , size+                    , member+                    , notMember+                    , isSubsetOf+                    , isProperSubsetOf++                    -- * Construction+                    , empty+                    , singleton+                    , insert+                    , delete++                    -- * Combine+                    , union+                    , unions+                    , difference+                    , intersection++                    -- * Filter+                    , filter+                    , partition++                    -- * Map+                    , map++                    -- * Fold+                    , fold++                    -- * Conversion+                    , elems+                    , toList+                    , fromList+                    ) where++import Prelude hiding (lookup,map,filter,null)++import Data.Hashable+import Data.List (foldl')+import Data.Monoid (Monoid(..))+import Data.Typeable++#if __GLASGOW_HASKELL__+import Text.Read+import Data.Data (Data(..), mkNoRepType)+#endif++import qualified Data.IntMap as I+import qualified Data.Set as S+++{--------------------------------------------------------------------+  Operators+--------------------------------------------------------------------}++-- | Same as 'difference'.+(\\) :: Ord a => HashSet a -> HashSet a -> HashSet a+s1 \\ s2 = difference s1 s2+++{--------------------------------------------------------------------+  Types+--------------------------------------------------------------------}++-- | The abstract type of a @HashSet@. Its interface is a suitable+-- subset of 'Data.IntSet.IntSet'.+newtype HashSet a = HashSet (I.IntMap (S.Set a)) deriving (Eq, Ord)++instance Ord a => Monoid (HashSet a) where+  mempty  = empty+  mappend = union+  mconcat = unions++instance Show a => Show (HashSet a) where+  showsPrec d m   = showParen (d > 10) $+    showString "fromList " . shows (toList m)++instance (Hashable a, Ord a, Read a) => Read (HashSet 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_TYPEABLE1(HashSet,hashSetTc,"HashSet")+++#if __GLASGOW_HASKELL__+{--------------------------------------------------------------------+  A Data instance+--------------------------------------------------------------------}++-- This instance preserves data abstraction at the cost of inefficiency.+-- We omit reflection services for the sake of data abstraction.++instance (Hashable a, Ord a, Data a) => Data (HashSet a) where+  gfoldl f z m = z fromList `f` (toList m)+  toConstr _   = error "toConstr"+  gunfold _ _  = error "gunfold"+  dataTypeOf _ = mkNoRepType "Data.HashSet.HashSet"+  dataCast1 f  = gcast1 f+#endif+++{--------------------------------------------------------------------+  Query+--------------------------------------------------------------------}+-- | Is the set empty?+null :: HashSet a -> Bool+null (HashSet s) = I.null s++-- | Number of elements in the set.+size :: HashSet a -> Int+size (HashSet s) = I.fold ((+) . S.size) 0 s++-- | Is the element a member of the set?+member :: (Hashable a, Ord a) => a -> HashSet a -> Bool+member a (HashSet s) =+  case I.lookup (hash a) s of+    Nothing -> False+    Just s' -> S.member a s'++-- | Is the element not a member of the set?+notMember :: (Hashable a, Ord a) => a -> HashSet a -> Bool+notMember k s = not $ member k s++-- | Is this a subset?+isSubsetOf :: Ord a => HashSet a -> HashSet a -> Bool+isSubsetOf (HashSet s1) (HashSet s2) =+  I.isSubmapOfBy (S.isSubsetOf) s1 s2++-- | Is this a proper subset? (ie. a subset but not equal).+isProperSubsetOf :: Ord a => HashSet a -> HashSet a -> Bool+isProperSubsetOf s1 s2 = isSubsetOf s1 s2 && size s1 < size s2+++{--------------------------------------------------------------------+  Construction+--------------------------------------------------------------------}+-- | The empty set.+empty :: HashSet a+empty = HashSet I.empty++-- | A set of one element.+singleton :: Hashable a => a -> HashSet a+singleton a = HashSet $+  I.singleton (hash a) $ S.singleton a++-- | Add a value to the set. When the value is already an element of the set,+-- it is replaced by the new one, ie. 'insert' is left-biased.+insert :: (Hashable a, Ord a) => a -> HashSet a -> HashSet a+insert a (HashSet s) = HashSet $+  I.insertWith (\_ -> S.insert a) (hash a) (S.singleton a) s+++nonempty :: S.Set a -> Maybe (S.Set a)+nonempty m | S.null m  = Nothing+           | otherwise = Just m++-- | Delete a value in the set. Returns the original set when the value was not+-- present.+delete :: (Hashable a, Ord a) => a -> HashSet a -> HashSet a+delete a (HashSet s) = HashSet $+  I.update (nonempty . S.delete a) (hash a) s+++{--------------------------------------------------------------------+  Combine+--------------------------------------------------------------------}++-- | The union of two sets.+union :: Ord a => HashSet a -> HashSet a -> HashSet a+union (HashSet s1) (HashSet s2) = HashSet $ I.unionWith S.union s1 s2++-- | The union of a list of sets.+unions :: Ord a => [HashSet a] -> HashSet a+unions xs = foldl' union empty xs++-- | Difference between two sets.+difference :: Ord a => HashSet a -> HashSet a -> HashSet a+difference (HashSet s1) (HashSet s2) = HashSet $+  I.differenceWith (\t1 t2 -> nonempty $ S.difference t1 t2) s1 s2++delete_empty :: I.IntMap (S.Set a) -> I.IntMap (S.Set a)+delete_empty = I.filter (not . S.null)++-- | The intersection of two sets.+intersection :: Ord a => HashSet a -> HashSet a -> HashSet a+intersection (HashSet s1) (HashSet s2) = HashSet $ delete_empty $+  I.intersectionWith S.intersection s1 s2+++{--------------------------------------------------------------------+  Filter+--------------------------------------------------------------------}+-- | Filter all elements that satisfy some predicate.+filter :: Ord a => (a -> Bool) -> HashSet a -> HashSet a+filter p (HashSet s) = HashSet $+  I.mapMaybe (nonempty . S.filter p) s++-- | Partition the set according to some predicate. The first set contains all+-- elements that satisfy the predicate, the second all elements that fail the+-- predicate.+partition :: Ord a => (a -> Bool) -> HashSet a -> (HashSet a, HashSet a)+partition p s = (filter p s, filter (not . p) s)+++{--------------------------------------------------------------------+  Map+--------------------------------------------------------------------}+-- | @'map' f s@ is the set obtained by applying @f@ to each element of @s@.+--+-- It's worth noting that the size of the result may be smaller if, for some+-- @(x,y)@, @x /= y && f x == f y@+map :: (Hashable b, Ord b) => (a -> b) -> HashSet a -> HashSet b+map f = fromList . fold ((:) . f) []+++{--------------------------------------------------------------------+  Fold+--------------------------------------------------------------------}+-- | Fold over the elements of a set in an unspecified order.+fold :: (a -> b -> b) -> b -> HashSet a -> b+fold f z (HashSet s) = I.fold (flip $ S.fold f) z s+++{--------------------------------------------------------------------+  Conversions+--------------------------------------------------------------------}+-- | The elements of a set. (For sets, this is equivalent to toList).+elems :: HashSet a -> [a]+elems = toList++-- | Convert the set to a list of elements.+toList :: HashSet a -> [a]+toList (HashSet s) = I.fold ((++) . S.toList) [] s++-- | Create a set from a list of elements.+fromList :: (Hashable a, Ord a) => [a] -> HashSet a+fromList xs = foldl' (flip insert) empty xs

@@ -1,15 +1,20 @@ Name:                hashmap-Version:             0.9.0-Synopsis:            Persistent HashMap with API of an IntMap.-Description:         An implementation of persistent 'HashMap'.+Version:             1.0.0+Synopsis:            Persistent containers HashMap and HashSet.+Description:         An implementation of persistent 'HashMap' and 'HashSet' on+                     top of 'Data.IntMap.IntMap' and 'Data.IntSet.IntSet',+                     with very similar API.                      .                      The class 'Hashable' is providing the 'Hashable.hash'                      method.                      .-                     The @'HashMap' key value@ itself is an-                     'Data.IntMap.IntMap' indexed by the hash value, containing-                     @'Data.Map.Map' key value@ for all keys with the same hash-                     value.+                     The @'HashMap' key value@ is an 'Data.IntMap.IntMap'+                     indexed by the hash value, containing @'Data.Map.Map' key value@+                     for all keys with the same hash value.+                     .+                     The @'HashSet' elem@ is an 'Data.IntMap.IntMap' indexed by+                     the hash value, containing @'Data.Set.Set' key value@ for+                     all elements with the same hash value. License:             BSD3 License-file:        LICENSE Author:              Milan Straka@@ -21,7 +26,7 @@   Library-  Exposed-modules:   Data.Hashable, Data.HashMap+  Exposed-modules:   Data.Hashable, Data.HashMap, Data.HashSet    Build-depends:     base >= 4.0 && < 5,                      containers >= 0.3,