Unordered Containers

https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/
Admin
Unordered Containers is a Haskell library providing efficient hash-based data structures including...
Tokens:186,063
Snippets:773
Trust Score:9.7
Update:1 year ago
Show doc for...
Tokens:
Raw
### HashSet Monoid Example

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashSet

An example demonstrating the `mappend` operation for `HashSet`s. It shows that the union of `fromList [1,2]` and `fromList [2,3]` results in `fromList [1,2,3]`.

```Haskell
>>> mappend (fromList [1,2]) (fromList [2,3])
fromList [1,2,3]
```

--------------------------------

### Create a HashSet from a list

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashSet

Provides an example of creating a HashSet from a list of elements using `fromList`. This is a common way to initialize a HashSet.

```Haskell
>>> **fromList [1,2]
**fromList [1,2]
```

--------------------------------

### Haskell Example: Group Values by Key

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Internal

Demonstrates using `fromListWith` to group values by their keys, creating lists of values for each key.

```Haskell
let xs = [('a', 1), ('b', 2), ('a', 3)]
in fromListWith (++) [ (k, [v]) | (k, v) <- xs ]

= fromList [('a', [3, 1]), ('b', [2])]
```

--------------------------------

### HashSet Monoid Example

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashSet-Internal

An example demonstrating the `mappend` operation for `HashSet`s. It shows that the union of `fromList [1,2]` and `fromList [2,3]` results in `fromList [1,2,3]`.

```Haskell
>>> mappend (fromList [1,2]) (fromList [2,3])
fromList [1,2,3]
```

--------------------------------

### Haskell Example: Count Element Occurrences

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Internal

Demonstrates using `fromListWith` to count the occurrences of each element in a list.

```Haskell
let xs = ['a', 'b', 'a']
in fromListWith (+) [ (x, 1) | x <- xs ]

= fromList [('a', 2), ('b', 1)]
```

--------------------------------

### HashSet: Insert an element

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashSet-Internal

Shows how to add an element to a `HashSet` using `HashSet.insert`. The example `HashSet.insert 1 HashSet.empty` results in `fromList [1]`.

```haskell
>>> **HashSet.insert 1 HashSet.empty
**fromList [1]
```

--------------------------------

### HashSet Construction Functions

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashSet-Internal

Provides functions for creating and initializing HashSets. This includes creating an empty set, a set with a single element, and checking if a set is empty or getting its size.

```Haskell
empty :: HashSet a
singleton :: Hashable a => a -> HashSet a
null :: HashSet a -> Bool
size :: HashSet a -> Int
```

--------------------------------

### HashSet: Get the number of elements

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashSet-Internal

Shows how to retrieve the number of elements in a `HashSet` using `HashSet.size`. Examples include `HashSet.size HashSet.empty` returning `0` and `HashSet.size (HashSet.fromList [1,2,3])` returning `3`.

```haskell
>>> **HashSet.size HashSet.empty
**0
>>> **HashSet.size (HashSet.fromList [1,2,3])
**3
```

--------------------------------

### HashMap Show Instance

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Internal

The Show instance provides a way to convert a HashMap into a String representation. It includes methods like `showsPrec`, `show`, and `showList` for formatting the output.

```Haskell
instance (Show k, Show v) => Show (HashMap k v) where
  showsPrec :: Int -> HashMap k v -> ShowS
  showsPrec = showsPrec
  show :: HashMap k v -> String
  show = show
  showList :: [HashMap k v] -> ShowS
  showList = showList
```

--------------------------------

### Search and Swap Element in Mutable Array

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/src/Data.HashMap

The `searchSwap` function searches for a specific key (`toFind`) within a mutable array (`mary`) starting from a given index (`start`). If the key is found, it swaps the element with the element at the `start` index. This is useful for optimizing subsequent searches by moving found elements to a known position.

```Haskell
searchSwap :: forall k s v.
Eq k =>
k -> Int -> MArray s (Leaf k v) -> ST s (Maybe (Leaf k v))
searchSwap toFind start = go start toFind start
  where
    go :: Int -> t -> Int -> MArray s (Leaf t v) -> ST s (Maybe (Leaf t v))
go i0 k i mary
      | i >= A.lengthM mary = pure Nothing
      | otherwise = do
        l@(L k' _v) <- A.read mary i
        if k == k'
          then do
            A.write mary i (L k' _v)
            pure (Just (L k' _v))
          else go i0 k (i + 1) mary
```

--------------------------------

### HashSet Show1 Instance Methods

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashSet

Provides methods for the `Show1` instance of `HashSet`, including `liftShowsPrec` for showing `HashSet`s with a given precedence and `liftShowList` for showing lists of `HashSet`s.

```Haskell
liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> HashSet a -> ShowS
liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [HashSet a] -> ShowS
```

--------------------------------

### Show1 Instance for HashMap

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/src/Data.HashMap

Provides the Show1 instance for HashMap, enabling structured display of HashMap contents with varying levels of detail. It uses `liftShowsPrec` to handle the display logic.

```Haskell
instance Show k => Show1 (HashMap k) where
    liftShowsPrec :: forall a.
(Int -> a -> ShowS)
-> ([a] -> ShowS) -> Int -> HashMap k a -> ShowS
liftShowsPrec = (Int -> k -> ShowS)
-> ([k] -> ShowS)
-> (Int -> a -> ShowS)
-> ([a] -> ShowS)
-> Int
-> HashMap k a
-> ShowS
forall a b.
(Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> Int
-> HashMap a b
-> ShowS
forall (f :: * -> * -> *) a b.
Show2 f =>
(Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> Int
-> f a b
-> ShowS
liftShowsPrec2 Int -> k -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec [k] -> ShowS
forall a. Show a => [a] -> ShowS
showList
```

--------------------------------

### Show Instance for HashMap

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/src/Data.HashMap

Implements the Show instance for HashMap, providing a way to convert HashMap values into human-readable string representations. It uses `showsPrec` and `toList` to format the output.

```Haskell
instance (Show k, Show v) => Show (HashMap k v) where
    showsPrec :: Int -> HashMap k v -> ShowS
showsPrec Int
d HashMap k v
m = Bool -> ShowS -> ShowS
showParen (Int
d Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
10) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$
      [Char] -> ShowS
showString [Char]
"fromList " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
      [(k, v)] -> ShowS
forall a. Show a => a -> ShowS
shows (HashMap k v -> [(k, v)]
forall k v. HashMap k v -> [(k, v)]
tolist HashMap k v
m)
```

--------------------------------

### Haskell HashMap: fromListWith Example 1

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Lazy

Example demonstrating how to use `fromListWith` to count occurrences of elements in a list. The `(+)` function is used to sum the counts for duplicate elements.

```Haskell
let xs = ['a', 'b', 'a']
in fromListWith (+) [ (x, 1) | x <- xs ]

= fromList [('a', 2), ('b', 1)]
```

--------------------------------

### Haskell HashSet Show Instance

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/src/Data.HashSet

Provides the Show instance for HashSet, enabling the display of HashSet values as strings. It leverages the `toList` function to convert the HashSet to a list and then uses `shows` for formatting.

```Haskell
instance (Show a) => Show (HashSet a) where
    showsPrec :: Int -> HashSet a -> ShowS
showsPrec Int
d HashSet a
m = Bool -> ShowS -> ShowS
showParen (Int
d Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
10) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$
      String -> ShowS
showString String
"fromList " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
      [a] -> ShowS
forall a. Show a => a -> ShowS
shows (HashSet a -> [a]
forall a. HashSet a -> [a]
tolist HashSet a
m)
```

--------------------------------

### Get Package Including Revisions

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/package/unordered-containers

This snippet demonstrates how to retrieve the unordered-containers package, ensuring that all metadata revisions are included. This is done using the 'cabal get' command.

```Shell
cabal get
```

--------------------------------

### Haskell HashMap: fromListWith Example 2

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Lazy

Example demonstrating how to use `fromListWith` to group values by keys, concatenating them into lists. The `(++)` function is used to merge values for duplicate keys.

```Haskell
let xs = [('a', 1), ('b', 2), ('a', 3)]
in fromListWith (++) [ (k, [v]) | (k, v) <- xs ]

= fromList [('a', [3, 1]), ('b', [2])]
```

--------------------------------

### Strict Left Fold on HashSet

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/src/Data.HashSet

Performs a strict left fold on the elements of the HashSet using a binary operator and a starting value. The accumulator is evaluated before each step. This function is strict in the starting value.

```Haskell
foldl' :: (a -> b -> a) -> a -> HashSet b -> a
foldl' f z0 = H.foldlWithKey' g z0 . asMap
  where g z k _ = f z k
```

--------------------------------

### HashSet Show1 Instance Methods

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashSet-Internal

Provides methods for the `Show1` instance of `HashSet`, including `liftShowsPrec` for showing `HashSet`s with a given precedence and `liftShowList` for showing lists of `HashSet`s.

```Haskell
liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> HashSet a -> ShowS
liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [HashSet a] -> ShowS
```

--------------------------------

### Haskell HashMap foldl' (Strict Left Fold)

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Internal-Strict

Performs a strict left fold on a HashMap, applying a binary operator to all elements with a given starting value. The operator is evaluated before the next application, ensuring strictness in the starting value. Time complexity is O(n).

```Haskell
foldl' :: (a -> v -> a) -> a -> HashMap k v -> a
```

--------------------------------

### Haskell HashSet Show1 Instance

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/src/Data.HashSet

Defines the Show1 instance for HashSet, allowing for structured showing of HashSet values with different levels of detail. It uses `liftShowsPrec` to handle the conversion of HashSet elements to their string representations.

```Haskell
instance Show1 HashSet where
    liftShowsPrec :: forall a.
(Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> HashSet a -> ShowS
liftShowsPrec sp sl d m =
        (Int -> [a] -> ShowS) -> String -> Int -> [a] -> ShowS
forall a. (Int -> a -> ShowS) -> String -> Int -> a -> ShowS
showsUnaryWith ((Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> [a] -> ShowS
forall a.
(Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> [a] -> ShowS
forall (f :: * -> *) a.
Show1 f =>
(Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> f a -> ShowS
liftShowsPrec Int -> a -> ShowS
sp [a] -> ShowS
sl) String
"fromList" Int
d (HashSet a -> [a]
forall a. HashSet a -> [a]
tolist HashSet a
m)
```

--------------------------------

### Haskell HashMap foldr' (Strict Right Fold)

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Internal-Strict

Performs a strict right fold on a HashMap, applying a binary operator to all elements with a given starting value. The operator is evaluated before the next application, ensuring strictness in the starting value. Time complexity is O(n).

```Haskell
foldr' :: (v -> a -> a) -> a -> HashMap k v -> a
```

--------------------------------

### HashMap Show Instance

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Internal-Strict

Describes the Show instance for HashMap, which provides a string representation of the HashMap. This requires the keys and values to have Show instances. The output format is typically `fromList [...]`.

```Haskell
instance (Show k, Show v) => Show (HashMap k v) where
  showsPrec :: Int -> HashMap k v -> ShowS
  showsPrec = showsPrec
  show :: HashMap k v -> String
  show = show
  showList :: [HashMap k v] -> ShowS
  showList = showList
```

--------------------------------

### Haskell HashMap foldlWithKey' (Strict Left Fold with Key)

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Internal-Strict

Performs a strict left fold on a HashMap with access to keys, applying a binary operator to all key-value pairs with a given starting value. The operator is evaluated before the next application, ensuring strictness in the starting value. Time complexity is O(n).

```Haskell
foldlWithKey' :: (a -> k -> v -> a) -> a -> HashMap k v -> a
```

--------------------------------

### HashMap Data Instance

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Internal

Provides the Data instance for HashMap, enabling generic programming capabilities for HashMaps. Requires Data k, Data v, Eq k, and Hashable k constraints.

```Haskell
Data (HashMap k v)
```

--------------------------------

### Haskell HashMap foldrWithKey' (Strict Right Fold with Key)

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Internal-Strict

Performs a strict right fold on a HashMap with access to keys, applying a binary operator to all key-value pairs with a given starting value. The operator is evaluated before the next application, ensuring strictness in the starting value. Time complexity is O(n).

```Haskell
foldrWithKey' :: (k -> v -> a -> a) -> a -> HashMap k v -> a
```

--------------------------------

### HashMap Show Instance

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Lazy

Describes the Show instance for HashMap, which provides a string representation of the HashMap. This requires the keys and values to have Show instances. The output format is typically `fromList [...]`.

```Haskell
instance (Show k, Show v) => Show (HashMap k v) where
  showsPrec :: Int -> HashMap k v -> ShowS
  showsPrec = showsPrec
  show :: HashMap k v -> String
  show = show
  showList :: [HashMap k v] -> ShowS
  showList = showList
```

--------------------------------

### HashMap Construction: Empty and Singleton

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Internal

Provides functions to construct HashMaps. `empty` creates an empty map with O(1) complexity. `singleton` creates a map with a single element, also with O(1) complexity, requiring the key type `k` to be an instance of `Hashable`.

```Haskell
empty :: HashMap k v Source #
O(1) Construct an empty map.
singleton :: Hashable k => k -> v -> HashMap k v Source #
O(1) Construct a map with a single element.
```

--------------------------------

### Get the size of a HashSet

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/src/Data.HashSet

Returns the number of elements in the HashSet. This is an O(1) operation.

```Haskell
size :: HashSet a -> Int
size = HashMap.size . toMap
```

--------------------------------

### Create HashSet from List

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/src/Data.HashSet

Constructs a HashSet from a list of elements. Requires elements to be instances of Eq and Hashable. This is an efficient way to initialize a HashSet.

```Haskell
-- | \(O(n \min(W, n))\) Construct a set from a list of elements.
fromList :: (Eq a, Hashable a) => [a] -> HashSet a
fromList :: forall a. (Eq a, Hashable a) => [a] -> HashSet a
fromList = HashMap a () -> HashSet a
forall a. HashMap a () -> HashSet a
HashSet (HashMap a () -> HashSet a)
-> ([a] -> HashMap a ()) -> [a] -> HashSet a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (HashMap a () -> a -> HashMap a ()) 
-> HashMap a () -> [a] -> HashMap a ()
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' (\ HashMap a ()
m a
k -> a -> () -> HashMap a () -> HashMap a ()
forall k v.
(Eq k, Hashable k) =>
k -> v -> HashMap k v -> HashMap k v
H.insert a
k () HashMap a ()
m) HashMap a ()
forall k v. HashMap k v
H.empty
{-# INLINE fromList #-}
```

--------------------------------

### Haskell Get Elements from HashMap

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Internal

Returns a lazily produced list of all values present in the HashMap.

```Haskell
elems :: HashMap k v -> [v]
```

--------------------------------

### HashMap Show2 Instance

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/src/Data.HashMap

Defines the `Show2` instance for `HashMap`, allowing for pretty-printing of HashMaps with custom show functions for keys and values.

```Haskell
instance Show2 HashMap where
    liftShowsPrec2 :: forall a b.
(Int -> a -> ShowS)
-> ([a] -> ShowS) 
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> Int
-> HashMap a b
-> ShowS
liftShowsPrec2 Int -> a -> ShowS
spk [a] -> ShowS
slk Int -> b -> ShowS
spv [b] -> ShowS
slv Int
 d HashMap a b
 m = 
        (Int -> [(a, b)] -> ShowS) -> [Char] -> Int -> [(a, b)] -> ShowS
forall a. (Int -> a -> ShowS) -> [Char] -> Int -> a -> ShowS
FC.showsUnaryWith ((Int -> (a, b) -> ShowS)
-> ([(a, b)] -> ShowS) -> Int -> [(a, b)] -> ShowS
forall a. 
(Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> [a] -> ShowS
forall (f :: * -> *) a.
Show1 f =>
(Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> f a -> ShowS
liftShowsPrec Int -> (a, b) -> ShowS
sp [(a, b)] -> ShowS
sl) [Char]
"fromList" Int
 d (HashMap a b -> [(a, b)]
forall k v. HashMap k v -> [(k, v)]
toList HashMap a b
 m)
      where
        sp :: Int -> (a, b) -> ShowS
sp = (Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> Int
-> (a, b)
-> ShowS
forall a b.
(Int -> a -> ShowS)
-> ([a] -> ShowS)

```

--------------------------------

### Haskell Get Keys from HashMap

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Internal

Returns a lazily produced list of all keys present in the HashMap.

```Haskell
keys :: HashMap k v -> [k]
```

--------------------------------

### HashMap Show1 Instance

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Internal-Strict

Defines the Show1 instance for HashMap, allowing for custom string representations of HashMaps with the same key type but potentially different value types. Includes liftShowsPrec and liftShowList.

```Haskell
liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> HashMap k a -> ShowS
liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [HashMap k a] -> ShowS
```

--------------------------------

### Haskell HashMap: Example - Count Occurrences

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Strict

Demonstrates using `fromListWith` to count the occurrences of elements in a list.

```Haskell
let xs = ['a', 'b', 'a']
in fromListWith (+) [ (x, 1) | x <- xs ]

= fromList [('a', 2), ('b', 1)]
```

--------------------------------

### HashMap Show1 Instance

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Internal

Defines the Show1 instance for HashMap, allowing for custom string representations of HashMaps with the same key type but potentially different value types. Includes liftShowsPrec and liftShowList.

```Haskell
liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> HashMap k a -> ShowS
liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [HashMap k a] -> ShowS
```

--------------------------------

### Haskell HashMap: Get Elements

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Strict

Returns a lazily produced list of all values in the HashMap. This is an O(n) operation.

```Haskell
elems :: HashMap k v -> [v]
```

--------------------------------

### HashSet Data Instance Methods

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashSet

Details the methods for the `Data` instance of `HashSet`, including `gfoldl`, `gunfold`, `toConstr`, `dataTypeOf`, `dataCast1`, `dataCast2`, `gmapT`, `gmapQl`, `gmapQr`, `gmapQ`, `gmapQi`, `gmapM`, `gmapMp`, and `gmapMo`, which are used for generic programming and data serialization.

```Haskell
gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> HashSet a -> c (HashSet a)
gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (HashSet a)
toConstr :: HashSet a -> Constr
dataTypeOf :: HashSet a -> DataType
dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (HashSet a))
dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (HashSet a))
gmapT :: (forall b. Data b => b -> b) -> HashSet a -> HashSet a
gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> HashSet a -> r
gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> HashSet a -> r
gmapQ :: (forall d. Data d => d -> u) -> HashSet a -> [u]
gmapQi :: Int -> (forall d. Data d => d -> u) -> HashSet a -> u
gmapM :: Monad m => (forall d. Data d => d -> m d) -> HashSet a -> m (HashSet a)
gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> HashSet a -> m (HashSet a)
gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> HashSet a -> m (HashSet a)
```

--------------------------------

### Haskell HashMap: Get Keys

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Strict

Returns a lazily produced list of all keys in the HashMap. This is an O(n) operation.

```Haskell
keys :: HashMap k v -> [k]
```

--------------------------------

### HashMap Show2 Instance

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Internal

Defines the Show2 instance for HashMap, which allows for custom string representations of HashMaps with potentially different key and value types. Includes liftShowsPrec2 and liftShowList2.

```Haskell
liftShowsPrec2 :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> (Int -> b -> ShowS) -> ([b] -> ShowS) -> Int -> HashMap a b -> ShowS
liftShowList2 :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> (Int -> b -> ShowS) -> ([b] -> ShowS) -> [HashMap a b] -> ShowS
```

--------------------------------

### Get the size of a HashMap in Haskell

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Internal

Retrieves the number of key-value mappings in a HashMap. The time complexity for this operation is O(n).

```Haskell
size :: HashMap k v -> Int
```

--------------------------------

### General fromListWithKey Accumulation Pattern

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Internal

Illustrates the general pattern of value accumulation using `fromListWithKey` when multiple entries exist for the same key. It shows how the provided function `f` is applied iteratively to combine the values.

```Haskell
fromListWith f [(k, a), (k, b), (k, c), (k, d)]
= fromList [(k, f k d (f k c (f k b a)))]
```

--------------------------------

### Get the size of a HashSet

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashSet

Shows how to retrieve the number of elements in a HashSet using the `size` function. The time complexity is O(n).

```Haskell
>>> **HashSet.size HashSet.empty
**0
>>> **HashSet.size (HashSet.fromList [1,2,3])
**3
```

--------------------------------

### Haskell HashMap: Fold Left

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Strict

Reduces a HashMap by applying a binary operator to all elements, starting with a given value. This is an O(n) operation.

```Haskell
foldl :: (a -> v -> a) -> a -> HashMap k v -> a
```

--------------------------------

### HashMap Show2 Instance

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Internal-Strict

Defines the Show2 instance for HashMap, which allows for custom string representations of HashMaps with potentially different key and value types. Includes liftShowsPrec2 and liftShowList2.

```Haskell
liftShowsPrec2 :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> (Int -> b -> ShowS) -> ([b] -> ShowS) -> Int -> HashMap a b -> ShowS
liftShowList2 :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> (Int -> b -> ShowS) -> ([b] -> ShowS) -> [HashMap a b] -> ShowS
```

--------------------------------

### Haskell HashMap: Fold Right

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Strict

Reduces a HashMap by applying a binary operator to all elements, starting with a given value. This is an O(n) operation.

```Haskell
foldr :: (v -> a -> a) -> a -> HashMap k v -> a
```

--------------------------------

### Read Instance for HashMap

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/src/Data.HashMap

Provides the Read instance for HashMap, enabling parsing of HashMap values from string representations. It defines `readPrec` for parsing individual HashMaps and `readListPrec` for parsing lists of HashMaps.

```Haskell
instance (Eq k, Hashable k, Read k, Read e) => Read (HashMap k e) where
    readPrec :: ReadPrec (HashMap k e)
readPrec = ReadPrec (HashMap k e) -> ReadPrec (HashMap k e)
forall a. Read a => ReadPrec a
parens (ReadPrec (HashMap k e) -> ReadPrec (HashMap k e))
-> ReadPrec (HashMap k e) -> ReadPrec (HashMap k e)
forall a b. (a -> b) -> a -> b
$
    Int -> ReadPrec (HashMap k e) -> ReadPrec (HashMap k e)
forall a. Int -> ReadPrec a -> ReadPrec a
prec Int
10 (ReadPrec (HashMap k e) -> ReadPrec (HashMap k e))
-> ReadPrec (HashMap k e) -> ReadPrec (HashMap k e)
forall a b. (a -> b) -> a -> b
$
    do
      Ident [Char]
"fromList" <- ReadPrec Lexeme
lexP
      [(k, e)] -> HashMap k e
forall k v. (Eq k, Hashable k) => [(k, v)] -> HashMap k v
fromList ([(k, e)] -> HashMap k e)
-> ReadPrec [(k, e)] -> ReadPrec (HashMap k e)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<>
      ReadPrec [(k, e)]
forall a. Read a => ReadPrec a
readPrec

    readListPrec :: ReadPrec [HashMap k e]
readListPrec = ReadPrec [HashMap k e]
forall a. Read a => ReadPrec [a]
readListPrecDefault
```

--------------------------------

### Haskell HashMap Construction: Empty and Singleton

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/src/Data.HashMap

Functions for creating HashMaps. 'empty' constructs an empty HashMap, and 'singleton' creates a HashMap with a single key-value pair, utilizing the 'Leaf' constructor.

```Haskell
empty :: HashMap k v
empty = Empty

singleton :: (Hashable k) => k -> v -> HashMap k v
singleton k v = Leaf (H.hashWithSalt k) (L k v)
```

--------------------------------

### HashSet Read Instance

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/src/Data.HashSet

Provides the Read instance for HashSet, allowing HashSets to be parsed from strings. It expects the format 'fromList [element1, element2, ...]' and requires elements to be instances of Read.

```Haskell
instance (Eq a, Hashable a, Read a) => Read (HashSet a) where
    readPrec :: ReadPrec (HashSet a)
readPrec = ReadPrec (HashSet a) -> ReadPrec (HashSet a)
forall a. ReadPrec a -> ReadPrec a
parens (ReadPrec (HashSet a) -> ReadPrec (HashSet a))
-> ReadPrec (HashSet a) -> ReadPrec (HashSet a)
forall a b. (a -> b) -> a -> b
$ Int -> ReadPrec (HashSet a) -> ReadPrec (HashSet a)
forall a. Int -> ReadPrec a -> ReadPrec a
prec Int
10 (ReadPrec (HashSet a) -> ReadPrec (HashSet a))
-> ReadPrec (HashSet a) -> ReadPrec (HashSet a)
forall a b. (a -> b) -> a -> b
$ do
      Ident String
"fromList" <- ReadPrec Lexeme
lexP
      [a] -> HashSet a
forall a. (Eq a, Hashable a) => [a] -> HashSet a
fromList ([a] -> HashSet a) -> ReadPrec [a] -> ReadPrec (HashSet a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<>
 ReadPrec [a]
forall a. Read a => ReadPrec a
readPrec
```

--------------------------------

### HashMap Show Instance

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Strict

Describes the Show instance for HashMap, which provides a string representation of the HashMap. This requires the keys and values to have Show instances.

```Haskell
instance (Show k, Show v) => Show (HashMap k v) where
  showsPrec :: Int -> HashMap k v -> ShowS
  showsPrec = showsPrec
  show :: HashMap k v -> String
  show = show
  showList :: [HashMap k v] -> ShowS
  showList = showList
```

--------------------------------

### HashSet Data Structures and Functions

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/doc-index-All

This section details functions for HashSets, including their definition, insertion, intersection, mapping, and membership testing. It highlights functions available in Data.HashSet and Data.HashSet.Internal modules.

```Haskell
HashSet :: Data.HashSet.Internal, Data.HashSet
1 (Type/Class) :: Data.HashSet.Internal, Data.HashSet
2 (Data Constructor) :: Data.HashSet.Internal
insert :: Data.HashSet.Internal, Data.HashSet
intersection :: Data.HashSet.Internal, Data.HashSet
intersectionWith :: Data.HashSet.Internal, Data.HashSet
intersectionWithKey :: Data.HashSet.Internal, Data.HashSet
isSubsetOf :: Data.HashSet.Internal, Data.HashSet
keysSet :: Data.HashSet.Internal, Data.HashMap.Strict, Data.HashMap.Lazy
map :: Data.HashSet.Internal, Data.HashSet
member :: Data.HashSet.Internal, Data.HashSet
null :: Data.HashSet.Internal, Data.HashSet
```

--------------------------------

### Haskell HashMap: Example - Group Values by Key

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Strict

Demonstrates using `fromListWith` to group values by their keys, concatenating values for duplicate keys.

```Haskell
let xs = [('a', 1), ('b', 2), ('a', 3)]
in fromListWith (++) [ (k, [v]) | (k, v) <- xs ]

= fromList [('a', [3, 1]), ('b', [2])]
```

--------------------------------

### Haskell HashMap Basic Interface

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Strict

Covers fundamental operations for HashMaps such as checking if a map is empty, getting its size, and checking for the presence of a key.

```Haskell
null :: HashMap k v -> Bool
size :: HashMap k v -> Int
member :: (Eq k, Hashable k) => k -> HashMap k a -> Bool
```

--------------------------------

### Haskell HashMap foldl

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/src/Data.HashMap

Reduces a HashMap by applying a binary operator to all elements, using a given starting value. This operation has a time complexity of O(n).

```Haskell
-- | \(O(n)\) Reduce this map by applying a binary operator to all
-- elements, using the given starting value (typically the
-- left-identity of the operator).
foldl :: (a -> v -> a) -> a -> HashMap k v -> a
foldl :: forall a v k. (a -> v -> a) -> a -> HashMap k v -> a
foldl a -> v -> a
f = (a -> k -> v -> a) -> a -> HashMap k v -> a
forall a k v. (a -> k -> v -> a) -> a -> HashMap k v -> a
foldlWithKey (a
a k
_k v
v -> a -> v -> a
f a
a v
v)
{-# INLINE foldl #-}
```

--------------------------------

### Use fromListWithKey with Custom Combination

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Internal

Demonstrates the usage of `fromListWithKey` with a custom `combine` function. It shows how a list of key-value pairs with duplicate keys is processed to produce a map where values are combined according to the specified logic for each key type.

```Haskell
fromListWithKey combine [(Div, 2), (Div, 6), (Sub, 2), (Sub, 3)]
= fromList [(Div, 3), (Sub, 1)]
```

--------------------------------

### Basic HashSet Operations in Haskell

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/src/Data

Demonstrates fundamental operations on a HashSet, including checking membership, inserting new elements, deleting existing elements, and combining sets.

```Haskell
>>> import qualified Data.HashSet as HashSet
>>> let dataStructures = HashSet.fromList ["Set", "Map", "Graph", "Sequence"]

-- Check if "Map" and "Trie" are in the set of data structures.
>>> HashSet.member "Map" dataStructures
True
>>> HashSet.member "Trie" dataStructures
False

-- Add a new entry to the set:
>>> let moreDataStructures = HashSet.insert "Trie" dataStructures
>>> HashSet.member "Trie" moreDataStructures
> True

-- Remove the "Graph" entry from the set of data structures.
>>> let fewerDataStructures = HashSet.delete "Graph" dataStructures
>>> HashSet.toList fewerDataStructures
["Map","Set","Sequence"]

-- Create a new set and combine it with our original set.
>>> let unorderedDataStructures = HashSet.fromList ["HashSet", "HashMap"]
>>> HashSet.union dataStructures unorderedDataStructures
fromList ["Map","HashSet","Graph","HashMap","Set","Sequence"]
```

--------------------------------

### Haskell HashMap foldr

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/src/Data.HashMap

Reduces a HashMap by applying a binary operator to all elements, using a given starting value. This operation has a time complexity of O(n).

```Haskell
-- | \(O(n)\) 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
foldr :: forall v a k. (v -> a -> a) -> a -> HashMap k v -> a
foldr v -> a -> a
f = (k -> v -> a -> a) -> a -> HashMap k v -> a
forall k v a. (k -> v -> a -> a) -> a -> HashMap k v -> a
foldrWithKey ((v -> a -> a) -> k -> v -> a -> a
forall a b. a -> b -> a
const v -> a -> a
f)
{-# INLINE foldr #-}
```

--------------------------------

### Haskell HashMap: Fold Left with Key

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Strict

Reduces a HashMap by applying a binary operator to all key-value pairs, starting with a given value. This is an O(n) operation.

```Haskell
foldlWithKey :: (a -> k -> v -> a) -> a -> HashMap k v -> a
```

--------------------------------

### HashMap Show1 Instance

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Lazy

Defines the Show1 instance for HashMap, allowing for custom string representations of HashMaps with the same key type but potentially different value types. Includes liftShowsPrec and liftShowList.

```Haskell
liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> HashMap k a -> ShowS
liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [HashMap k a] -> ShowS
```

--------------------------------

### Haskell HashMap: Fold Right with Key

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Strict

Reduces a HashMap by applying a binary operator to all key-value pairs, starting with a given value. This is an O(n) operation.

```Haskell
foldrWithKey :: (k -> v -> a -> a) -> a -> HashMap k v -> a
```

--------------------------------

### Haskell Strict Left Fold for HashMap

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Internal

Performs a strict left fold on a HashMap, applying a binary operator to all elements. The function is strict in the starting value.

```Haskell
foldl' :: (a -> v -> a) -> a -> HashMap k v -> a
```

--------------------------------

### HashMap Type Constructors and Data Constructors

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/doc-index-All

This section lists type and data constructors for HashMaps, including Leaf and HashMap itself, along with their module references.

```Haskell
Leaf :: Data.HashMap.Internal
1 (Data Constructor) :: Data.HashMap.Internal
2 (Type/Class) :: Data.HashMap.Internal
```

--------------------------------

### Create an empty HashSet

Source: https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashSet

Shows how to construct an empty HashSet using `HashSet.empty`. This operation has a time complexity of O(1).

```Haskell
>>> **HashSet.empty
**fromList []
```
Tokens:
Raw