Identity element for adding to a map

Question
1

Is there an identity element for adding to Map operation?
I want to write something like the following.

myMap + (src -> dst) + ( if(cond)  dst -> src) else identity)

Its similar to

mySum + f(x) + (if (cond) f(g) else 0)

The best I can think of is the following, which is a lot of extra code.

  def makeAdj_16[V](edges:Seq[(V,V)],directed:Boolean):Map[V,Set[V]] = {
    edges.foldLeft(Map[V,Set[V]]()){
      case (adj,(src,dst)) =>
        val m1 = adj + (src -> (adj.getOrElse(src,Set[V]())+dst)) 
        if (directed)
          m1
        else
          m1 + (dst -> (adj.getOrElse(dst,Set[V]())+src))
    }
  }
2

myMap ++ (if (cond) Map(dst -> src) else Map())

3 Likes
3

BTW, the question of whether I need parens around an if such as (if (cond) Map(dst -> src) else Map()) is always unclear to me. I usually end up putting more parens than necessary in my code.

4

so ++ has an identity element but + does not.

5

That actually makes sense, when you think about it. What you’re describing as an “identity element” is what I think of as a “zero” in terms of a Monoid – the value of a Monoid type that you can add to any other value of that type and not change it.

(This is pretty much the rough definition of a Monoid: a type that can be “added” together, and which has a “zero” value. Map is basically a Monoid, as is List, String, Int, and lots of others. Int is really useful to think about here, because it’s a Monoid but isn’t a collection in any conventional sense.)

The thing is, when you’re looking at a List[A], or a Map[A,B], or something like that, the Monoid itself is the List or Map, not the values you put into it. And so the zero also needs to be of that collection type – it is the “empty” value of that type, like Map.empty.

++ is the operator that combines two collections, so it’s the way you can “add” the zero. +, on the other hand, isn’t really well-defined in this way: it puts something into a collection, but doesn’t combine two collections, so it doesn’t make sense as a way to add the zero of the collection.

(You can make a case that, since + is the way to combine an Int with its zero, that it should work here. Unfortunately, it doesn’t work that way on Scala collections.)

1 Like