I'd say the cleanest way to go is to split your Info data structure into an intermediate key and a value part like so: type Key = String data Value = Value {count :: !Int, healthTopics :: ![String]} keyvalue :: Info -> (Key,Value) keyvalue (Info _ h k) = (k,Value 1 [h]) and give Value a Monoid instance: instance Monoid Value where mempty = Value 0 [] mappend (Value c s) (Value c' s') = Value (c+c') (s++s') (Or you could use (Sum Int) instead of Int and have type Value = (Sum Int,[String]). Then the Monoid instance is derived for you.) Now you can transform a list of Infos into a Map using a generic function: makeMap :: [Info] -> M.Map Key Value makeMap = M.fromListWith mappend . map keyvalue Semantically, it's pretty identical to ALeX Kazik's suggestion of using foldl' and alter. Internally, fromListWith uses a strict fold, so strictness should be the same as using foldl'. Olaf