CODEWITHSUNDEEP
haskelldictionary
atlantis
atlantis

Reputation: 3126

Sum over Haskell Map

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)]

Upvotes: 5

Views: 2186

Answers (3)

ehird
ehird

Reputation: 40787

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

Upvotes: 4

dan_waterworth
dan_waterworth

Reputation: 6441

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)]

Upvotes: 3

Victor
Victor

Reputation: 385

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

Where l is your map.

Upvotes: 3

Related Questions