-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Persistent containers Map and Set based on hashing.
--
-- An implementation of persistent Map and Set containers
-- based on hashing. The implementation is build on top of
-- Data.IntMap.IntMap and Data.IntSet.IntSet, with very
-- similar API. It uses Hashable class from the hashable
-- package for hashing.
--
-- This package can be used as a drop-in replacement for Data.Map
-- and Data.Set modules.
--
-- The Map key value is an Data.IntMap.IntMap
-- indexed by the hash value, containing either one (key,
-- value) or a Data.Map.Map key value for all keys
-- with the same hash value.
--
-- The Set elem is an Data.IntMap.IntMap indexed
-- by the hash value, containing either one elem or
-- Data.Set.Set elem for all elements with the same hash
-- value.
@package hashmap
@version 1.3.2
-- | Persistent Set based on hashing, which is defined as
--
--
-- data Set e = IntMap (Some e)
--
--
-- is an IntMap indexed by hash values of elements, containing a
-- value of Some e. That contains either one e or a
-- Set e with elements of the same hash values.
--
-- The interface of a Set is a suitable subset of IntSet
-- and can be used as a drop-in replacement of Set.
--
-- The complexity of operations is determined by the complexities of
-- IntMap and Set operations. See the sources of Set
-- to see which operations from containers package are used.
module Data.HashSet
-- | The abstract type of a Set. Its interface is a suitable
-- subset of IntSet.
data Set a
-- | The HashSet is a type synonym for Set for backward
-- compatibility. It is deprecated and will be removed in furture
-- releases.
-- | Deprecated: HashSet is deprecated. Please use Set instead.
type HashSet a = Set a
-- | Same as difference.
(\\) :: Ord a => Set a -> Set a -> Set a
-- | Is the set empty?
null :: Set a -> Bool
-- | Number of elements in the set.
size :: Set a -> Int
-- | Is the element a member of the set?
member :: (Hashable a, Ord a) => a -> Set a -> Bool
-- | Is the element not a member of the set?
notMember :: (Hashable a, Ord a) => a -> Set a -> Bool
-- | Is this a subset?
isSubsetOf :: Ord a => Set a -> Set a -> Bool
-- | Is this a proper subset? (ie. a subset but not equal).
isProperSubsetOf :: Ord a => Set a -> Set a -> Bool
-- | The empty set.
empty :: Set a
-- | A set of one element.
singleton :: Hashable a => a -> Set 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 -> Set a -> Set a
-- | Delete a value in the set. Returns the original set when the value was
-- not present.
delete :: (Hashable a, Ord a) => a -> Set a -> Set a
-- | The union of two sets.
union :: Ord a => Set a -> Set a -> Set a
-- | The union of a list of sets.
unions :: Ord a => [Set a] -> Set a
-- | Difference between two sets.
difference :: Ord a => Set a -> Set a -> Set a
-- | The intersection of two sets.
intersection :: Ord a => Set a -> Set a -> Set a
-- | Filter all elements that satisfy some predicate.
filter :: Ord a => (a -> Bool) -> Set a -> Set a
-- | 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) -> Set a -> (Set a, Set a)
-- | 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) -> Set a -> Set b
-- | Fold over the elements of a set in an unspecified order.
fold :: (a -> b -> b) -> b -> Set a -> b
-- | The elements of a set. (For sets, this is equivalent to toList).
elems :: Set a -> [a]
-- | Convert the set to a list of elements.
toList :: Set a -> [a]
-- | Create a set from a list of elements.
fromList :: (Hashable a, Ord a) => [a] -> Set a
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.HashSet.Set a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.HashSet.Set a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.HashSet.Some a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.HashSet.Some a)
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.HashSet.Some a)
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.HashSet.Set a)
instance GHC.Classes.Ord a => GHC.Base.Monoid (Data.HashSet.Set a)
instance GHC.Show.Show a => GHC.Show.Show (Data.HashSet.Set a)
instance (Data.Hashable.Class.Hashable a, GHC.Classes.Ord a, GHC.Read.Read a) => GHC.Read.Read (Data.HashSet.Set a)
instance (Data.Hashable.Class.Hashable a, GHC.Classes.Ord a, Data.Data.Data a) => Data.Data.Data (Data.HashSet.Set a)
-- | Persistent Map based on hashing, which is defined as
--
--
-- data Map k v = IntMap (Some k v)
--
--
-- is an IntMap indexed by hash values of keys, containing a value
-- of Some e. That contains either one (k,
-- v) pair or a Map k v with keys of the
-- same hash values.
--
-- The interface of a Map is a suitable subset of IntMap
-- and can be used as a drop-in replacement of Map.
--
-- The complexity of operations is determined by the complexities of
-- IntMap and Map operations. See the sources of Map
-- to see which operations from containers package are used.
module Data.HashMap
-- | The abstract type of a Map. Its interface is a suitable
-- subset of IntMap.
data Map k v
-- | The HashMap is a type synonym for Map for backward
-- compatibility. It is deprecated and will be removed in furture
-- releases.
-- | Deprecated: HashMap is deprecated. Please use Map instead.
type HashMap k v = Map k v
-- | Find the value at a key. Calls error when the element can not
-- be found.
(!) :: (Hashable k, Ord k) => Map k a -> k -> a
-- | Same as difference.
(\\) :: Ord k => Map k a -> Map k b -> Map k a
-- | Is the map empty?
null :: Map k a -> Bool
-- | Number of elements in the map.
size :: Map k a -> Int
-- | Is the key a member of the map?
member :: (Hashable k, Ord k) => k -> Map k a -> Bool
-- | Is the key not a member of the map?
notMember :: (Hashable k, Ord k) => k -> Map k a -> Bool
-- | Lookup the value at a key in the map.
lookup :: (Hashable k, Ord k) => k -> Map k a -> Maybe a
-- | The expression (findWithDefault def k map) returns the
-- value at key k or returns def when the key is not an
-- element of the map.
findWithDefault :: (Hashable k, Ord k) => a -> k -> Map k a -> a
-- | The empty map.
empty :: Map k a
-- | A map of one element.
singleton :: Hashable k => k -> a -> Map k a
-- | Insert a new key/value pair 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 :: (Hashable k, Ord k) => k -> a -> Map k a -> Map k a
-- | Insert with a combining function. insertWith f key value
-- mp will insert the pair (key, value) into mp if key does
-- not exist in the map. If the key does exist, the function will insert
-- f new_value old_value.
insertWith :: (Hashable k, Ord k) => (a -> a -> a) -> k -> a -> Map k a -> Map k a
-- | Insert with a combining function. insertWithKey f key value
-- mp will insert the pair (key, value) into mp if key does
-- not exist in the map. If the key does exist, the function will insert
-- f key new_value old_value.
insertWithKey :: (Hashable k, Ord k) => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
-- | The expression (insertLookupWithKey f k x map) is a
-- pair where the first element is equal to (lookup k
-- map) and the second element equal to (insertWithKey f
-- k x map).
insertLookupWithKey :: (Hashable k, Ord k) => (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)
-- | Delete a key and its value from the map. When the key is not a member
-- of the map, the original map is returned.
delete :: (Hashable k, Ord k) => k -> Map k a -> Map k a
-- | Adjust a value at a specific key. When the key is not a member of the
-- map, the original map is returned.
adjust :: (Hashable k, Ord k) => (a -> a) -> k -> Map k a -> Map k a
-- | Adjust a value at a specific key. When the key is not a member of the
-- map, the original map is returned.
adjustWithKey :: (Hashable k, Ord k) => (k -> a -> a) -> k -> Map k a -> Map k a
-- | The expression (update f k map) updates the value
-- x at k (if it is in the map). If (f x) is
-- Nothing, the element is deleted. If it is (Just
-- y), the key k is bound to the new value y.
update :: (Hashable k, Ord k) => (a -> Maybe a) -> k -> Map k a -> Map k a
-- | The expression (update f k map) updates the value
-- x at k (if it is in the map). If (f k x) is
-- Nothing, the element is deleted. If it is (Just
-- y), the key k is bound to the new value y.
updateWithKey :: (Hashable k, Ord k) => (k -> a -> Maybe a) -> k -> Map k a -> Map k a
-- | Lookup and update. The function returns original value, if it is
-- updated. This is different behavior than updateLookupWithKey.
-- Returns the original key value if the map entry is deleted.
updateLookupWithKey :: (Hashable k, Ord k) => (k -> a -> Maybe a) -> k -> Map k a -> (Maybe a, Map k a)
-- | 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 Map.
alter :: (Hashable k, Ord k) => (Maybe a -> Maybe a) -> k -> Map k a -> Map k a
-- | The (left-biased) union of two maps. It prefers the first map when
-- duplicate keys are encountered, i.e. (union ==
-- unionWith const).
union :: Ord k => Map k a -> Map k a -> Map k a
-- | The union with a combining function.
unionWith :: Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
-- | The union with a combining function.
unionWithKey :: Ord k => (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
-- | The union of a list of maps.
unions :: Ord k => [Map k a] -> Map k a
-- | The union of a list of maps, with a combining operation.
unionsWith :: Ord k => (a -> a -> a) -> [Map k a] -> Map k a
-- | Difference between two maps (based on keys).
difference :: Ord k => Map k a -> Map k b -> Map k a
-- | Difference with a combining function.
differenceWith :: Ord k => (a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
-- | Difference with a combining function. When two equal keys are
-- encountered, the combining function is applied to the key and both
-- values. If it returns Nothing, the element is discarded (proper
-- set difference). If it returns (Just y), the element
-- is updated with a new value y.
differenceWithKey :: Ord k => (k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
-- | The (left-biased) intersection of two maps (based on keys).
intersection :: Ord k => Map k a -> Map k b -> Map k a
-- | The intersection with a combining function.
intersectionWith :: Ord k => (a -> b -> c) -> Map k a -> Map k b -> Map k c
-- | The intersection with a combining function.
intersectionWithKey :: Ord k => (k -> a -> b -> c) -> Map k a -> Map k b -> Map k c
-- | Map a function over all values in the map.
map :: (a -> b) -> Map k a -> Map k b
-- | Map a function over all values in the map.
mapWithKey :: (k -> a -> b) -> Map k a -> Map k b
-- | The function mapAccum threads an accumulating argument
-- through the map in unspecified order of keys.
mapAccum :: (a -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
-- | The function mapAccumWithKey threads an accumulating
-- argument through the map in unspecified order of keys.
mapAccumWithKey :: (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
-- | Fold the values in the map, such that fold f z ==
-- foldr f z . elems.
fold :: (a -> b -> b) -> b -> Map k a -> b
-- | Fold the keys and values in the map, such that foldWithKey
-- f z == foldr (uncurry f) z . toAscList.
foldWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
-- | Return all elements of the map in arbitrary order of their keys.
elems :: Map k a -> [a]
-- | Return all keys of the map in arbitrary order.
keys :: Map k a -> [k]
-- | The set of all keys of the map.
keysSet :: Ord k => Map k a -> Set k
-- | Return all key/value pairs in the map in arbitrary key order.
assocs :: Map k a -> [(k, a)]
-- | Convert the map to a list of key/value pairs.
toList :: Map k a -> [(k, a)]
-- | Create a map from a list of key/value pairs.
fromList :: (Hashable k, Ord k) => [(k, a)] -> Map k a
-- | Create a map from a list of key/value pairs with a combining function.
fromListWith :: (Hashable k, Ord k) => (a -> a -> a) -> [(k, a)] -> Map k a
-- | Build a map from a list of key/value pairs with a combining function.
fromListWithKey :: (Hashable k, Ord k) => (k -> a -> a -> a) -> [(k, a)] -> Map k a
-- | Filter all values that satisfy some predicate.
filter :: Ord k => (a -> Bool) -> Map k a -> Map k a
-- | Filter all keys/values that satisfy some predicate.
filterWithKey :: Ord k => (k -> a -> Bool) -> Map k a -> Map k a
-- | 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.
partition :: Ord k => (a -> Bool) -> Map k a -> (Map k a, Map k a)
-- | 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) -> Map k a -> (Map k a, Map k a)
-- | Map values and collect the Just results.
mapMaybe :: Ord k => (a -> Maybe b) -> Map k a -> Map k b
-- | Map keys/values and collect the Just results.
mapMaybeWithKey :: Ord k => (k -> a -> Maybe b) -> Map k a -> Map k b
-- | Map values and separate the Left and Right results.
mapEither :: Ord k => (a -> Either b c) -> Map k a -> (Map k b, Map k c)
-- | Map keys/values and separate the Left and Right results.
mapEitherWithKey :: Ord k => (k -> a -> Either b c) -> Map k a -> (Map k b, Map k c)
-- | Is this a submap?
isSubmapOf :: (Ord k, Eq a) => Map k a -> Map k a -> Bool
-- | The expression (isSubmapOfBy f m1 m2) returns
-- True if all keys in m1 are in m2, and when
-- f returns True when applied to their respective
-- values.
isSubmapOfBy :: Ord k => (a -> b -> Bool) -> Map k a -> Map k b -> Bool
-- | Is this a proper submap? (ie. a submap but not equal).
isProperSubmapOf :: (Ord k, Eq a) => Map k a -> Map k a -> Bool
-- | Is this a proper submap? (ie. a submap but not equal). The expression
-- (isProperSubmapOfBy f m1 m2) returns True when
-- m1 and m2 are not equal, all keys in m1 are
-- in m2, and when f returns True when applied
-- to their respective values.
isProperSubmapOfBy :: Ord k => (a -> b -> Bool) -> Map k a -> Map k b -> Bool
instance (GHC.Classes.Ord k, GHC.Classes.Ord v) => GHC.Classes.Ord (Data.HashMap.Map k v)
instance (GHC.Classes.Eq k, GHC.Classes.Eq v) => GHC.Classes.Eq (Data.HashMap.Map k v)
instance (GHC.Classes.Ord v, GHC.Classes.Ord k) => GHC.Classes.Ord (Data.HashMap.Some k v)
instance (GHC.Classes.Eq v, GHC.Classes.Eq k) => GHC.Classes.Eq (Data.HashMap.Some k v)
instance (Control.DeepSeq.NFData k, Control.DeepSeq.NFData v) => Control.DeepSeq.NFData (Data.HashMap.Some k v)
instance (Control.DeepSeq.NFData k, Control.DeepSeq.NFData v) => Control.DeepSeq.NFData (Data.HashMap.Map k v)
instance GHC.Base.Functor (Data.HashMap.Map k)
instance GHC.Classes.Ord k => GHC.Base.Monoid (Data.HashMap.Map k a)
instance Data.Foldable.Foldable (Data.HashMap.Map k)
instance Data.Traversable.Traversable (Data.HashMap.Map k)
instance (GHC.Show.Show k, GHC.Show.Show a) => GHC.Show.Show (Data.HashMap.Map k a)
instance (GHC.Read.Read k, Data.Hashable.Class.Hashable k, GHC.Classes.Ord k, GHC.Read.Read a) => GHC.Read.Read (Data.HashMap.Map k a)
instance (Data.Data.Data k, Data.Hashable.Class.Hashable k, GHC.Classes.Ord k, Data.Data.Data a) => Data.Data.Data (Data.HashMap.Map k a)