Hoogle Search

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

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

containers Data.Map.Lazy

Build a map from an ascending list in linear time with a combining function for equal keys. The precondition (input list is ascending) is not checked.
```
fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "ba")]
valid (fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")]) == True
valid (fromAscListWith (++) [(5,"a"), (3,"b"), (5,"b")]) == False
```

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

containers	Data.Map.Lazy

Build a map from an ascending list in linear time with a combining function for equal keys. The precondition (input list is ascending) is not checked.

let f k a1 a2 = (show k) ++ ":" ++ a1 ++ a2
fromAscListWithKey f [(3,"b"), (5,"a"), (5,"b"), (5,"b")] == fromList [(3, "b"), (5, "5:b5:ba")]
valid (fromAscListWithKey f [(3,"b"), (5,"a"), (5,"b"), (5,"b")]) == True
valid (fromAscListWithKey f [(5,"a"), (3,"b"), (5,"b"), (5,"b")]) == False

Also see the performance note on fromListWith.

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

containers	Data.Map.Lazy

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,"b")] == 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.Lazy

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.Lazy

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.Lazy

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.Lazy

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"), (5,"b"), (3,"b")]) == False

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

containers Data.Map.Lazy

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.Lazy

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.Lazy

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.

Page 41 of many | Previous | Next

Hoogle Search

Performance