libghc-unordered-containers-doc 0.2.5.0-1 / usr / share / doc / libghc-unordered-containers-doc / html / unordered-containers.txt

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


-- | Efficient hashing-based container types
--   
--   Efficient hashing-based container types. The containers have been
--   optimized for performance critical use, both in terms of large data
--   quantities and high speed.
--   
--   The declared cost of each operation is either worst-case or amortized,
--   but remains valid even if structures are shared.
@package unordered-containers
@version 0.2.5.0


-- | A map from <i>hashable</i> keys to values. A map cannot contain
--   duplicate keys; each key can map to at most one value. A
--   <a>HashMap</a> makes no guarantees as to the order of its elements.
--   
--   The implementation is based on <i>hash array mapped tries</i>. A
--   <a>HashMap</a> is often faster than other tree-based set types,
--   especially when key comparison is expensive, as in the case of
--   strings.
--   
--   Many operations have a average-case complexity of <i>O(log n)</i>. The
--   implementation uses a large base (i.e. 16) so in practice these
--   operations are constant time.
module Data.HashMap.Strict

-- | A map from keys to values. A map cannot contain duplicate keys; each
--   key can map to at most one value.
data HashMap k v

-- | <i>O(1)</i> Construct an empty map.
empty :: HashMap k v

-- | <i>O(1)</i> Construct a map with a single element.
singleton :: Hashable k => k -> v -> HashMap k v

-- | <i>O(1)</i> Return <a>True</a> if this map is empty, <a>False</a>
--   otherwise.
null :: HashMap k v -> Bool

-- | <i>O(n)</i> Return the number of key-value mappings in this map.
size :: HashMap k v -> Int

-- | <i>O(log n)</i> Return <a>True</a> if the specified key is present in
--   the map, <a>False</a> otherwise.
member :: (Eq k, Hashable k) => k -> HashMap k a -> Bool

-- | <i>O(log n)</i> Return the value to which the specified key is mapped,
--   or <a>Nothing</a> if this map contains no mapping for the key.
lookup :: (Eq k, Hashable k) => k -> HashMap k v -> Maybe v

-- | <i>O(log n)</i> Return the value to which the specified key is mapped,
--   or the default value if this map contains no mapping for the key.
lookupDefault :: (Eq k, Hashable k) => v -> k -> HashMap k v -> v

-- | <i>O(log n)</i> Return the value to which the specified key is mapped.
--   Calls <a>error</a> if this map contains no mapping for the key.
(!) :: (Eq k, Hashable k) => HashMap k v -> k -> v

-- | <i>O(log n)</i> Associate the specified value with the specified key
--   in this map. If this map previously contained a mapping for the key,
--   the old value is replaced.
insert :: (Eq k, Hashable k) => k -> v -> HashMap k v -> HashMap k v

-- | <i>O(log n)</i> Associate the value with the key in this map. If this
--   map previously contained a mapping for the key, the old value is
--   replaced by the result of applying the given function to the new and
--   old value. Example:
--   
--   <pre>
--   insertWith f k v map
--     where f new old = new + old
--   </pre>
insertWith :: (Eq k, Hashable k) => (v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v

-- | <i>O(log n)</i> Remove the mapping for the specified key from this map
--   if present.
delete :: (Eq k, Hashable k) => k -> HashMap k v -> HashMap k v

-- | <i>O(log n)</i> Adjust the value tied to a given key in this map only
--   if it is present. Otherwise, leave the map alone.
adjust :: (Eq k, Hashable k) => (v -> v) -> k -> HashMap k v -> HashMap k v

-- | <i>O(n+m)</i> The union of two maps. If a key occurs in both maps, the
--   mapping from the first will be the mapping in the result.
union :: (Eq k, Hashable k) => HashMap k v -> HashMap k v -> HashMap k v

-- | <i>O(n+m)</i> The union of two maps. If a key occurs in both maps, the
--   provided function (first argument) will be used to compute the result.
unionWith :: (Eq k, Hashable k) => (v -> v -> v) -> HashMap k v -> HashMap k v -> HashMap k v

-- | Construct a set containing all elements from a list of sets.
unions :: (Eq k, Hashable k) => [HashMap k v] -> HashMap k v

-- | <i>O(n)</i> Transform this map by applying a function to every value.
map :: (v1 -> v2) -> HashMap k v1 -> HashMap k v2

-- | <i>O(n)</i> Transform this map by applying a function to every value.
mapWithKey :: (k -> v1 -> v2) -> HashMap k v1 -> HashMap k v2

-- | <i>O(n)</i> Transform this map by accumulating an Applicative result
--   from every value.
traverseWithKey :: Applicative f => (k -> v1 -> f v2) -> HashMap k v1 -> f (HashMap k v2)

-- | <i>O(n*log m)</i> Difference of two maps. Return elements of the first
--   map not existing in the second.
difference :: (Eq k, Hashable k) => HashMap k v -> HashMap k w -> HashMap k v

-- | <i>O(n*log m)</i> Intersection of two maps. Return elements of the
--   first map for keys existing in the second.
intersection :: (Eq k, Hashable k) => HashMap k v -> HashMap k w -> HashMap k v

-- | <i>O(n+m)</i> Intersection of two maps. If a key occurs in both maps
--   the provided function is used to combine the values from the two maps.
intersectionWith :: (Eq k, Hashable k) => (v1 -> v2 -> v3) -> HashMap k v1 -> HashMap k v2 -> HashMap k v3

-- | <i>O(n)</i> Reduce this map by applying a binary operator to all
--   elements, using the given starting value (typically the left-identity
--   of the operator). Each application of the operator is evaluated before
--   before using the result in the next application. This function is
--   strict in the starting value.
foldl' :: (a -> v -> a) -> a -> HashMap k v -> a

-- | <i>O(n)</i> Reduce this map by applying a binary operator to all
--   elements, using the given starting value (typically the left-identity
--   of the operator). Each application of the operator is evaluated before
--   before using the result in the next application. This function is
--   strict in the starting value.
foldlWithKey' :: (a -> k -> v -> a) -> a -> HashMap k v -> a

-- | <i>O(n)</i> Reduce this map by applying a binary operator to all
--   elements, using the given starting value (typically the right-identity
--   of the operator).
foldr :: (v -> a -> a) -> a -> HashMap k v -> a

-- | <i>O(n)</i> Reduce this map by applying a binary operator to all
--   elements, using the given starting value (typically the right-identity
--   of the operator).
foldrWithKey :: (k -> v -> a -> a) -> a -> HashMap k v -> a

-- | <i>O(n)</i> Filter this map by retaining only elements which values
--   satisfy a predicate.
filter :: (v -> Bool) -> HashMap k v -> HashMap k v

-- | <i>O(n)</i> Filter this map by retaining only elements satisfying a
--   predicate.
filterWithKey :: (k -> v -> Bool) -> HashMap k v -> HashMap k v

-- | <i>O(n)</i> Return a list of this map's keys. The list is produced
--   lazily.
keys :: HashMap k v -> [k]

-- | <i>O(n)</i> Return a list of this map's values. The list is produced
--   lazily.
elems :: HashMap k v -> [v]

-- | <i>O(n)</i> Return a list of this map's elements. The list is produced
--   lazily.
toList :: HashMap k v -> [(k, v)]

-- | <i>O(n*log n)</i> Construct a map with the supplied mappings. If the
--   list contains duplicate mappings, the later mappings take precedence.
fromList :: (Eq k, Hashable k) => [(k, v)] -> HashMap k v

-- | <i>O(n*log n)</i> Construct a map from a list of elements. Uses the
--   provided function to merge duplicate entries.
fromListWith :: (Eq k, Hashable k) => (v -> v -> v) -> [(k, v)] -> HashMap k v


-- | A map from <i>hashable</i> keys to values. A map cannot contain
--   duplicate keys; each key can map to at most one value. A
--   <a>HashMap</a> makes no guarantees as to the order of its elements.
--   
--   The implementation is based on <i>hash array mapped tries</i>. A
--   <a>HashMap</a> is often faster than other tree-based set types,
--   especially when key comparison is expensive, as in the case of
--   strings.
--   
--   Many operations have a average-case complexity of <i>O(log n)</i>. The
--   implementation uses a large base (i.e. 16) so in practice these
--   operations are constant time.
module Data.HashMap.Lazy

-- | A map from keys to values. A map cannot contain duplicate keys; each
--   key can map to at most one value.
data HashMap k v

-- | <i>O(1)</i> Construct an empty map.
empty :: HashMap k v

-- | <i>O(1)</i> Construct a map with a single element.
singleton :: Hashable k => k -> v -> HashMap k v

-- | <i>O(1)</i> Return <a>True</a> if this map is empty, <a>False</a>
--   otherwise.
null :: HashMap k v -> Bool

-- | <i>O(n)</i> Return the number of key-value mappings in this map.
size :: HashMap k v -> Int

-- | <i>O(log n)</i> Return <a>True</a> if the specified key is present in
--   the map, <a>False</a> otherwise.
member :: (Eq k, Hashable k) => k -> HashMap k a -> Bool

-- | <i>O(log n)</i> Return the value to which the specified key is mapped,
--   or <a>Nothing</a> if this map contains no mapping for the key.
lookup :: (Eq k, Hashable k) => k -> HashMap k v -> Maybe v

-- | <i>O(log n)</i> Return the value to which the specified key is mapped,
--   or the default value if this map contains no mapping for the key.
lookupDefault :: (Eq k, Hashable k) => v -> k -> HashMap k v -> v

-- | <i>O(log n)</i> Return the value to which the specified key is mapped.
--   Calls <a>error</a> if this map contains no mapping for the key.
(!) :: (Eq k, Hashable k) => HashMap k v -> k -> v

-- | <i>O(log n)</i> Associate the specified value with the specified key
--   in this map. If this map previously contained a mapping for the key,
--   the old value is replaced.
insert :: (Eq k, Hashable k) => k -> v -> HashMap k v -> HashMap k v

-- | <i>O(log n)</i> Associate the value with the key in this map. If this
--   map previously contained a mapping for the key, the old value is
--   replaced by the result of applying the given function to the new and
--   old value. Example:
--   
--   <pre>
--   insertWith f k v map
--     where f new old = new + old
--   </pre>
insertWith :: (Eq k, Hashable k) => (v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v

-- | <i>O(log n)</i> Remove the mapping for the specified key from this map
--   if present.
delete :: (Eq k, Hashable k) => k -> HashMap k v -> HashMap k v

-- | <i>O(log n)</i> Adjust the value tied to a given key in this map only
--   if it is present. Otherwise, leave the map alone.
adjust :: (Eq k, Hashable k) => (v -> v) -> k -> HashMap k v -> HashMap k v

-- | <i>O(n+m)</i> The union of two maps. If a key occurs in both maps, the
--   mapping from the first will be the mapping in the result.
union :: (Eq k, Hashable k) => HashMap k v -> HashMap k v -> HashMap k v

-- | <i>O(n+m)</i> The union of two maps. If a key occurs in both maps, the
--   provided function (first argument) will be used to compute the result.
unionWith :: (Eq k, Hashable k) => (v -> v -> v) -> HashMap k v -> HashMap k v -> HashMap k v

-- | Construct a set containing all elements from a list of sets.
unions :: (Eq k, Hashable k) => [HashMap k v] -> HashMap k v

-- | <i>O(n)</i> Transform this map by applying a function to every value.
map :: (v1 -> v2) -> HashMap k v1 -> HashMap k v2

-- | <i>O(n)</i> Transform this map by applying a function to every value.
mapWithKey :: (k -> v1 -> v2) -> HashMap k v1 -> HashMap k v2

-- | <i>O(n)</i> Transform this map by accumulating an Applicative result
--   from every value.
traverseWithKey :: Applicative f => (k -> v1 -> f v2) -> HashMap k v1 -> f (HashMap k v2)

-- | <i>O(n*log m)</i> Difference of two maps. Return elements of the first
--   map not existing in the second.
difference :: (Eq k, Hashable k) => HashMap k v -> HashMap k w -> HashMap k v

-- | <i>O(n*log m)</i> Intersection of two maps. Return elements of the
--   first map for keys existing in the second.
intersection :: (Eq k, Hashable k) => HashMap k v -> HashMap k w -> HashMap k v

-- | <i>O(n+m)</i> Intersection of two maps. If a key occurs in both maps
--   the provided function is used to combine the values from the two maps.
intersectionWith :: (Eq k, Hashable k) => (v1 -> v2 -> v3) -> HashMap k v1 -> HashMap k v2 -> HashMap k v3

-- | <i>O(n)</i> Reduce this map by applying a binary operator to all
--   elements, using the given starting value (typically the left-identity
--   of the operator). Each application of the operator is evaluated before
--   before using the result in the next application. This function is
--   strict in the starting value.
foldl' :: (a -> v -> a) -> a -> HashMap k v -> a

-- | <i>O(n)</i> Reduce this map by applying a binary operator to all
--   elements, using the given starting value (typically the left-identity
--   of the operator). Each application of the operator is evaluated before
--   before using the result in the next application. This function is
--   strict in the starting value.
foldlWithKey' :: (a -> k -> v -> a) -> a -> HashMap k v -> a

-- | <i>O(n)</i> Reduce this map by applying a binary operator to all
--   elements, using the given starting value (typically the right-identity
--   of the operator).
foldr :: (v -> a -> a) -> a -> HashMap k v -> a

-- | <i>O(n)</i> Reduce this map by applying a binary operator to all
--   elements, using the given starting value (typically the right-identity
--   of the operator).
foldrWithKey :: (k -> v -> a -> a) -> a -> HashMap k v -> a

-- | <i>O(n)</i> Filter this map by retaining only elements which values
--   satisfy a predicate.
filter :: (v -> Bool) -> HashMap k v -> HashMap k v

-- | <i>O(n)</i> Filter this map by retaining only elements satisfying a
--   predicate.
filterWithKey :: (k -> v -> Bool) -> HashMap k v -> HashMap k v

-- | <i>O(n)</i> Return a list of this map's keys. The list is produced
--   lazily.
keys :: HashMap k v -> [k]

-- | <i>O(n)</i> Return a list of this map's values. The list is produced
--   lazily.
elems :: HashMap k v -> [v]

-- | <i>O(n)</i> Return a list of this map's elements. The list is produced
--   lazily.
toList :: HashMap k v -> [(k, v)]

-- | <i>O(n)</i> Construct a map with the supplied mappings. If the list
--   contains duplicate mappings, the later mappings take precedence.
fromList :: (Eq k, Hashable k) => [(k, v)] -> HashMap k v

-- | <i>O(n*log n)</i> Construct a map from a list of elements. Uses the
--   provided function to merge duplicate entries.
fromListWith :: (Eq k, Hashable k) => (v -> v -> v) -> [(k, v)] -> HashMap k v


-- | A set of <i>hashable</i> values. A set cannot contain duplicate items.
--   A <a>HashSet</a> makes no guarantees as to the order of its elements.
--   
--   The implementation is based on <i>hash array mapped trie</i>. A
--   <a>HashSet</a> is often faster than other tree-based set types,
--   especially when value comparison is expensive, as in the case of
--   strings.
--   
--   Many operations have a average-case complexity of <i>O(log n)</i>. The
--   implementation uses a large base (i.e. 16) so in practice these
--   operations are constant time.
module Data.HashSet

-- | A set of values. A set cannot contain duplicate values.
data HashSet a

-- | <i>O(1)</i> Construct an empty set.
empty :: HashSet a

-- | <i>O(1)</i> Construct a set with a single element.
singleton :: Hashable a => a -> HashSet a

-- | <i>O(n+m)</i> Construct a set containing all elements from both sets.
--   
--   To obtain good performance, the smaller set must be presented as the
--   first argument.
union :: (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a

-- | Construct a set containing all elements from a list of sets.
unions :: (Eq a, Hashable a) => [HashSet a] -> HashSet a

-- | <i>O(1)</i> Return <a>True</a> if this set is empty, <a>False</a>
--   otherwise.
null :: HashSet a -> Bool

-- | <i>O(n)</i> Return the number of elements in this set.
size :: HashSet a -> Int

-- | <i>O(min(n,W))</i> Return <a>True</a> if the given value is present in
--   this set, <a>False</a> otherwise.
member :: (Eq a, Hashable a) => a -> HashSet a -> Bool

-- | <i>O(min(n,W))</i> Add the specified value to this set.
insert :: (Eq a, Hashable a) => a -> HashSet a -> HashSet a

-- | <i>O(min(n,W))</i> Remove the specified value from this set if
--   present.
delete :: (Eq a, Hashable a) => a -> HashSet a -> HashSet a

-- | <i>O(n)</i> Transform this set by applying a function to every value.
--   The resulting set may be smaller than the source.
map :: (Hashable b, Eq b) => (a -> b) -> HashSet a -> HashSet b

-- | <i>O(n)</i> Difference of two sets. Return elements of the first set
--   not existing in the second.
difference :: (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a

-- | <i>O(n)</i> Intersection of two sets. Return elements present in both
--   the first set and the second.
intersection :: (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a

-- | <i>O(n)</i> Reduce this set by applying a binary operator to all
--   elements, using the given starting value (typically the left-identity
--   of the operator). Each application of the operator is evaluated before
--   before using the result in the next application. This function is
--   strict in the starting value.
foldl' :: (a -> b -> a) -> a -> HashSet b -> a

-- | <i>O(n)</i> Reduce this set by applying a binary operator to all
--   elements, using the given starting value (typically the right-identity
--   of the operator).
foldr :: (b -> a -> a) -> a -> HashSet b -> a

-- | <i>O(n)</i> Filter this set by retaining only elements satisfying a
--   predicate.
filter :: (a -> Bool) -> HashSet a -> HashSet a

-- | <i>O(n)</i> Return a list of this set's elements. The list is produced
--   lazily.
toList :: HashSet a -> [a]

-- | <i>O(n*min(W, n))</i> Construct a set from a list of elements.
fromList :: (Eq a, Hashable a) => [a] -> HashSet a
instance Typeable1 HashSet
instance (Data a, Eq a, Hashable a) => Data (HashSet a)
instance Show a => Show (HashSet a)
instance (Eq a, Hashable a, Read a) => Read (HashSet a)
instance (Hashable a, Eq a) => Monoid (HashSet a)
instance Foldable HashSet
instance (Hashable a, Eq a) => Eq (HashSet a)
instance NFData a => NFData (HashSet a)