Sum over Haskell Map

Question

Is there a standard function to sum all values in a Haskell map. My Map reads something like [(a,2),(b,4),(c,6)]?

Essentially what I am trying to do is a normalized frequency distribution. So the values of the keys in the above map are counts for a,b,c. I need to normalize them as [(a,1/6),(b,1/3),(c,1/2)]

Answer 1

You can simply do Map.foldl' (+) 0 (or M.foldl', if you imported Data.Map as M).

This is just like foldl' (+) 0 . Map.elems, but slightly more efficient. (Don't forget the apostrophe — using foldl or foldr to do sums with the standard numeric types (Int, Integer, Float, Double, etc.) will build up huge thunks, which will use up lots of memory and possibly cause your program to overflow the stack.)

However, only sufficiently recent versions of containers (>= 0.4.2.0) contain Data.Map.foldl', and you shouldn't upgrade it with cabal install, since it comes with GHC. So unless you're on GHC 7.2 or above, foldl' (+) 0 . Map.elems is the best way to accomplish this.

You could also use Data.Foldable.sum, which works on any instance of the Foldable typeclass, but will still build up large thunks on the common numeric types.

Here's a complete example:

normalize :: (Fractional a) => Map k a -> Map k a
normalize m = Map.map (/ total) m
  where total = foldl' (+) 0 $ Map.elems m

You'll need to import Data.List to use foldl'.

Answer 2

let
    total = foldr (\(_, n) r -> r + n) 0 l
in map (\(x, y) -> (x, y/total) l

Where l is your map.

Answer 3

Simple:

import qualified Data.Map as M

sumMap = M.foldl' (+) 0

normalizeMap m =
  let s = sumMap m in
    M.map (/ s) m

main = do
  let m = M.fromList [("foo", 1), ("bar", 2), ("baz", 6)]
  (print . sumMap) m
  (print . normalizeMap) m

prints:

9.0
fromList [("bar",0.2222222222222222),("baz",0.6666666666666666),("foo",0.1111111111111111)]