O(n \log n). Build a map from a list of key/value pairs with a combining function.
If the keys are in non-decreasing order, this function takes O(n) time.
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.
See also: fromListUpsert
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 O(a), 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