I don't think anyone's pointed it out, but you can't build a Foldable structure with just Foldable. The Foldable class only allows you to "reduce" objects that already exist. For instance you cannot write this function where the Map is Data.Map rather than your MultiMap: getValues :: Foldable f => k -> Data.Map k v -> f v Really all you can do is produce an API like Data.Map, Data.Set have: toList :: MultiMap k v -> [(k,v)] toMap :: Ord k => MultiMap k v -> Map k v toSet :: (Ord k, Ord v) => MultiMap k v -> Set (k,v) In a nutshell, you seem to be wanting "container oblivious code". You can't really do this in Haskell I'm afraid. You can traverse and reduce containers generically with the Traverse and Foldable classes but you can't build them generically[*]. Best wishes Stephen [*] This might not be a disadvantage once you get over the initial disappointment - usually when you build something, you really do need to know what it is.