Why are Maps foldable over the values?

Questions
1

I bet this is something that we inherited from the language that shall not be named, but without googling through mailing list is there a reason why we can’t have both the key and the value (as a pair) when we fold over Maps?

I think that I’ve internalized the toList conversion (as demo’d here) until someone correctly pointed to me that it could be wasteful if I’m constructing the map just to fold over the grouped results.

2

The types force Foldable to only target the values. Let’s look at the definition of the typeclass (slightly simplified):

class Foldable t where
  -- | Combine the elements of a structure using a monoid.
  foldMap : Monoid m => (a -> m) -> t a -> m
  foldMap f = foldr ((<>) . f) mempty

Now t a needs to be of kind star meaning it has values (as opposed to a type constructor Optional : * -> *) so that clearly has to be Map k v. That leaves us with only one choice for t, it has to be Map k. Therefore the a in the definition of foldMap corresponds to the values of the map.

This is the same reason why the Functor instance for Either has to map over the second element and not the first one.

2 Likes
3

Interesting, I see this as a consequence of wanting to shoehorn a data type with two type parameters into a type class with only one. Are there an concepts (within type classes or the Haskell, PL world more broadly) of transforming them, so that I can think of Map k v as ThingWithPairs (k, v) and then deriving Foldable for ThingWithPairs . One wouldn’t get away from the need to construct the pairs (though hopefully they will be compiled away), but one would get away from needing to construct the list.

4

I don’t believe there is a generalised typeclass providing the abstraction you are asking about — a quick hoogle search for Monoid m => (a -> b -> m c) -> f a b -> c comes up empty. To be honest, anything that can satisfy that type signature is going to be map-like.

On the other hand we aren’t restricted to typeclasses. Our datatypes can export any useful functions that are sensible for that type — typeclasses are only useful if there is a useful abstraction over multiple types. So it would make sense for the DA.Next.Map module to export a foldMapEntries : Monoid m c => (a -> b -> c) -> Map a b -> c function that avoids the double handling involved in converting to/from a list of pairs.

1 Like