Hoogle Search

Note that Stackage only displays results for the latest LTS and Nightly snapshot. Learn more.

fromDescList :: Eq k => [(k, a)] -> Map k a

containers	Data.Map.Strict.Internal

Build a map from a descending list in linear time. The precondition (input list is descending) is not checked.

fromDescList [(5,"a"), (3,"b")]          == fromList [(3, "b"), (5, "a")]
fromDescList [(5,"a"), (5,"b"), (3,"a")] == fromList [(3, "b"), (5, "b")]
valid (fromDescList [(5,"a"), (5,"b"), (3,"b")]) == True
valid (fromDescList [(5,"a"), (3,"b"), (5,"b")]) == False

fromDescListWith :: Eq k => (a -> a -> a) -> [(k, a)] -> Map k a

containers Data.Map.Strict.Internal

Build a map from a descending list in linear time with a combining function for equal keys. The precondition (input list is descending) is not checked.
```
fromDescListWith (++) [(5,"a"), (5,"b"), (3,"b")] == fromList [(3, "b"), (5, "ba")]
valid (fromDescListWith (++) [(5,"a"), (5,"b"), (3,"b")]) == True
valid (fromDescListWith (++) [(5,"a"), (3,"b"), (5,"b")]) == False
```
Also see the performance note on fromListWith.
fromDescListWithKey :: Eq k => (k -> a -> a -> a) -> [(k, a)] -> Map k a

containers Data.Map.Strict.Internal

Build a map from a descending list in linear time with a combining function for equal keys. The precondition (input list is descending) is not checked.
```
let f k a1 a2 = (show k) ++ ":" ++ a1 ++ a2
fromDescListWithKey f [(5,"a"), (5,"b"), (5,"b"), (3,"b")] == fromList [(3, "b"), (5, "5:b5:ba")]
valid (fromDescListWithKey f [(5,"a"), (5,"b"), (5,"b"), (3,"b")]) == True
valid (fromDescListWithKey f [(5,"a"), (3,"b"), (5,"b"), (5,"b")]) == False
```
Also see the performance note on fromListWith.

fromDistinctAscList :: [(k, a)] -> Map k a

containers	Data.Map.Strict.Internal

Build a map from an ascending list of distinct elements in linear time. The precondition is not checked.

fromDistinctAscList [(3,"b"), (5,"a")] == fromList [(3, "b"), (5, "a")]
valid (fromDistinctAscList [(3,"b"), (5,"a")])          == True
valid (fromDistinctAscList [(3,"b"), (5,"a"), (5,"b")]) == False

fromDistinctDescList :: [(k, a)] -> Map k a

containers	Data.Map.Strict.Internal

Build a map from a descending list of distinct elements in linear time. The precondition is not checked.

fromDistinctDescList [(5,"a"), (3,"b")] == fromList [(3, "b"), (5, "a")]
valid (fromDistinctDescList [(5,"a"), (3,"b")])          == True
valid (fromDistinctDescList [(5,"a"), (3,"b"), (3,"a")]) == False

fromList :: Ord k => [(k, a)] -> Map k a

containers Data.Map.Strict.Internal

Build a map from a list of key/value pairs. See also fromAscList. If the list contains more than one value for the same key, the last value for the key is retained. If the keys of the list are ordered, a linear-time implementation is used.
```
fromList [] == empty
fromList [(5,"a"), (3,"b"), (5, "c")] == fromList [(5,"c"), (3,"b")]
fromList [(5,"c"), (3,"b"), (5, "a")] == fromList [(5,"a"), (3,"b")]
```
fromListWith :: Ord k => (a -> a -> a) -> [(k, a)] -> Map k a

containers Data.Map.Strict.Internal

Build a map from a list of key/value pairs with a combining function. See also fromAscListWith.
```
fromListWith (++) [(5,"a"), (5,"b"), (3,"x"), (5,"c")] == fromList [(3, "x"), (5, "cba")]
fromListWith (++) [] == empty
```
Note the reverse ordering of "cba" in the example. The symmetric combining function f is applied in a left-fold over the list, as f new old.
Performance
You should ensure that the given f is fast with this order of arguments. Symmetric functions may be slow in one order, and fast in another. For the common case of collecting values of matching keys in a list, as above: The complexity of (++) a b is <math>, so it is fast when given a short list as its first argument. Thus:
```
fromListWith       (++)  (replicate 1000000 (3, "x"))   -- O(n),  fast
fromListWith (flip (++)) (replicate 1000000 (3, "x"))   -- O(n²), extremely slow
```
because they evaluate as, respectively:
```
fromList [(3, "x" ++ ("x" ++ "xxxxx..xxxxx"))]   -- O(n)
fromList [(3, ("xxxxx..xxxxx" ++ "x") ++ "x")]   -- O(n²)
```
Thus, to get good performance with an operation like (++) while also preserving the same order as in the input list, reverse the input:
```
fromListWith (++) (reverse [(5,"a"), (5,"b"), (5,"c")]) == fromList [(5, "abc")]
```
and it is always fast to combine singleton-list values [v] with fromListWith (++), as in:
```
fromListWith (++) $ reverse $ map (\(k, v) -> (k, [v])) someListOfTuples
```
fromListWithKey :: Ord k => (k -> a -> a -> a) -> [(k, a)] -> Map k a

containers Data.Map.Strict.Internal

Build a map from a list of key/value pairs with a combining function. See also fromAscListWithKey.
```
let f key new_value old_value = show key ++ ":" ++ new_value ++ "|" ++ old_value
fromListWithKey f [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"c")] == fromList [(3, "3:a|b"), (5, "5:c|5:b|a")]
fromListWithKey f [] == empty
```
Also see the performance note on fromListWith.
toAscList :: Map k a -> [(k, a)]

containers Data.Map.Strict.Internal

Convert the map to a list of key/value pairs where the keys are in ascending order. Subject to list fusion.
```
toAscList (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]
```
toDescList :: Map k a -> [(k, a)]

containers Data.Map.Strict.Internal

Convert the map to a list of key/value pairs where the keys are in descending order. Subject to list fusion.
```
toDescList (fromList [(5,"a"), (3,"b")]) == [(5,"a"), (3,"b")]
```

Page 44 of many | Previous | Next

Hoogle Search

Performance