-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Persistent containers Map and Set based on hashing.
--   
--   An implementation of persistent <a>Map</a> and <a>Set</a> containers
--   based on hashing. The implementation is build on top of
--   <a>Data.IntMap.IntMap</a> and <a>Data.IntSet.IntSet</a>, with very
--   similar API. It uses <a>Hashable</a> class from the <tt>hashable</tt>
--   package for hashing.
--   
--   This package can be used as a drop-in replacement for <a>Data.Map</a>
--   and <a>Data.Set</a> modules.
--   
--   The <tt><a>Map</a> key value</tt> is an <a>Data.IntMap.IntMap</a>
--   indexed by the hash value, containing either one (<a>key</a>,
--   <a>value</a>) or a <tt><a>Data.Map.Map</a> key value</tt> for all keys
--   with the same hash value.
--   
--   The <tt><a>Set</a> elem</tt> is an <a>Data.IntMap.IntMap</a> indexed
--   by the hash value, containing either one <a>elem</a> or
--   <tt><a>Data.Set.Set</a> elem</tt> for all elements with the same hash
--   value.
@package hashmap
@version 1.3.0.1


-- | Persistent <a>Set</a> based on hashing, which is defined as
--   
--   <pre>
--   data <a>Set</a> e = <a>IntMap</a> (Some e)
--   </pre>
--   
--   is an <a>IntMap</a> indexed by hash values of elements, containing a
--   value of <tt>Some e</tt>. That contains either one <tt>e</tt> or a
--   <tt><a>Set</a> e</tt> with elements of the same hash values.
--   
--   The interface of a <a>Set</a> is a suitable subset of <a>IntSet</a>
--   and can be used as a drop-in replacement of <a>Set</a>.
--   
--   The complexity of operations is determined by the complexities of
--   <a>IntMap</a> and <a>Set</a> operations. See the sources of <a>Set</a>
--   to see which operations from <tt>containers</tt> package are used.
module Data.HashSet

-- | The abstract type of a <tt>Set</tt>. Its interface is a suitable
--   subset of <a>IntSet</a>.
data Set a

-- | The <tt>HashSet</tt> is a type synonym for <tt>Set</tt> for backward
--   compatibility. It is deprecated and will be removed in furture
--   releases.

-- | <i>Deprecated: HashSet is deprecated. Please use Set instead.</i>
type HashSet a = Set a

-- | Same as <a>difference</a>.
(\\) :: 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. <a>insert</a> 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)

-- | <tt><a>map</a> f s</tt> is the set obtained by applying <tt>f</tt> to
--   each element of <tt>s</tt>.
--   
--   It's worth noting that the size of the result may be smaller if, for
--   some <tt>(x,y)</tt>, <tt>x /= y &amp;&amp; f x == f y</tt>
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 <a>Map</a> based on hashing, which is defined as
--   
--   <pre>
--   data <a>Map</a> k v = <a>IntMap</a> (Some k v)
--   </pre>
--   
--   is an <a>IntMap</a> indexed by hash values of keys, containing a value
--   of <tt>Some e</tt>. That contains either one <tt>(<tt>k</tt>,
--   <tt>v</tt>)</tt> pair or a <tt><a>Map</a> k v</tt> with keys of the
--   same hash values.
--   
--   The interface of a <a>Map</a> is a suitable subset of <a>IntMap</a>
--   and can be used as a drop-in replacement of <a>Map</a>.
--   
--   The complexity of operations is determined by the complexities of
--   <a>IntMap</a> and <a>Map</a> operations. See the sources of <a>Map</a>
--   to see which operations from <tt>containers</tt> package are used.
module Data.HashMap

-- | The abstract type of a <tt>Map</tt>. Its interface is a suitable
--   subset of <a>IntMap</a>.
data Map k v

-- | The <tt>HashMap</tt> is a type synonym for <tt>Map</tt> for backward
--   compatibility. It is deprecated and will be removed in furture
--   releases.

-- | <i>Deprecated: HashMap is deprecated. Please use Map instead.</i>
type HashMap k v = Map k v

-- | Find the value at a key. Calls <a>error</a> when the element can not
--   be found.
(!) :: (Hashable k, Ord k) => Map k a -> k -> a

-- | Same as <a>difference</a>.
(\\) :: 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 <tt>(<a>findWithDefault</a> def k map)</tt> returns the
--   value at key <tt>k</tt> or returns <tt>def</tt> 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. <a>insert</a> is equivalent to <tt><a>insertWith</a>
--   <a>const</a></tt>.
insert :: (Hashable k, Ord k) => k -> a -> Map k a -> Map k a

-- | Insert with a combining function. <tt><a>insertWith</a> f key value
--   mp</tt> will insert the pair (key, value) into <tt>mp</tt> if key does
--   not exist in the map. If the key does exist, the function will insert
--   <tt>f new_value old_value</tt>.
insertWith :: (Hashable k, Ord k) => (a -> a -> a) -> k -> a -> Map k a -> Map k a

-- | Insert with a combining function. <tt><a>insertWithKey</a> f key value
--   mp</tt> will insert the pair (key, value) into <tt>mp</tt> if key does
--   not exist in the map. If the key does exist, the function will insert
--   <tt>f key new_value old_value</tt>.
insertWithKey :: (Hashable k, Ord k) => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a

-- | The expression (<tt><a>insertLookupWithKey</a> f k x map</tt>) is a
--   pair where the first element is equal to (<tt><a>lookup</a> k
--   map</tt>) and the second element equal to (<tt><a>insertWithKey</a> f
--   k x map</tt>).
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 (<tt><a>update</a> f k map</tt>) updates the value
--   <tt>x</tt> at <tt>k</tt> (if it is in the map). If (<tt>f x</tt>) is
--   <a>Nothing</a>, the element is deleted. If it is (<tt><a>Just</a>
--   y</tt>), the key <tt>k</tt> is bound to the new value <tt>y</tt>.
update :: (Hashable k, Ord k) => (a -> Maybe a) -> k -> Map k a -> Map k a

-- | The expression (<tt><a>update</a> f k map</tt>) updates the value
--   <tt>x</tt> at <tt>k</tt> (if it is in the map). If (<tt>f k x</tt>) is
--   <a>Nothing</a>, the element is deleted. If it is (<tt><a>Just</a>
--   y</tt>), the key <tt>k</tt> is bound to the new value <tt>y</tt>.
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 <a>updateLookupWithKey</a>.
--   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 (<tt><a>alter</a> f k map</tt>) alters the value
--   <tt>x</tt> at <tt>k</tt>, or absence thereof. <a>alter</a> can be used
--   to insert, delete, or update a value in an <a>Map</a>.
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. (<tt><a>union</a> ==
--   <a>unionWith</a> <a>const</a></tt>).
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 <a>Nothing</a>, the element is discarded (proper
--   set difference). If it returns (<tt><a>Just</a> y</tt>), the element
--   is updated with a new value <tt>y</tt>.
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 <tt><a>mapAccum</a></tt> 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 <tt><a>mapAccumWithKey</a></tt> 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 <tt><a>fold</a> f z ==
--   <a>foldr</a> f z . <a>elems</a></tt>.
fold :: (a -> b -> b) -> b -> Map k a -> b

-- | Fold the keys and values in the map, such that <tt><a>foldWithKey</a>
--   f z == <a>foldr</a> (<a>uncurry</a> f) z . <tt>toAscList</tt></tt>.
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 <a>Just</a> results.
mapMaybe :: Ord k => (a -> Maybe b) -> Map k a -> Map k b

-- | Map keys/values and collect the <a>Just</a> results.
mapMaybeWithKey :: Ord k => (k -> a -> Maybe b) -> Map k a -> Map k b

-- | Map values and separate the <a>Left</a> and <a>Right</a> results.
mapEither :: Ord k => (a -> Either b c) -> Map k a -> (Map k b, Map k c)

-- | Map keys/values and separate the <a>Left</a> and <a>Right</a> 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 (<tt><a>isSubmapOfBy</a> f m1 m2</tt>) returns
--   <a>True</a> if all keys in <tt>m1</tt> are in <tt>m2</tt>, and when
--   <tt>f</tt> returns <a>True</a> 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
--   (<tt><a>isProperSubmapOfBy</a> f m1 m2</tt>) returns <a>True</a> when
--   <tt>m1</tt> and <tt>m2</tt> are not equal, all keys in <tt>m1</tt> are
--   in <tt>m2</tt>, and when <tt>f</tt> returns <a>True</a> 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 k, GHC.Classes.Ord v) => GHC.Classes.Ord (Data.HashMap.Some k v)
instance (GHC.Classes.Eq k, GHC.Classes.Eq v) => 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)
