Why are these two monoids not equivalent?

Question
1 
//Monoids for sets

  implicit def setUnion[A] : Monoid[Set[A]] =
    new Monoid[Set[A]] {
      override def empty: Set[A] = Set.empty

      override def combine(x: Set[A], y: Set[A]): Set[A] =
        x ++ y
    }


  implicit val setUnion= new Monoid[Set[_]] {
    override def empty: Set[_] = Set.empty //This compiles even though empty takes a type parameter

    override def combine(x: Set[_], y: Set[_]): Set[_] =
      x ++ y
  }

The second implementation is never looked up by the compiler. Why?
The second implementation cannot have a type parameter. Hence I have replaced it with _. But is it the same as the first implementation which uses animplicit def as opposed to an implicit val.

2

Both implementations work and do the same, but the latter resolves differently. Take for example this method:

def concat[A : Monoid](a1: A, a2: A) = Monoid[A].combine(a1,a2)

If we pass it some sets, the resolution will fail with the latter monoid defined:

@ concat(Set(1,2), Set(3,4)) 
cmd13.sc:1: could not find implicit value for evidence parameter of type cats.Monoid[scala.collection.immutable.Set[Int]]
val res13 = concat(Set(1,2), Set(3,4))

As you can see from the error, the compiler is looking for a Monoid[Set[Int]], so the instance Monoid[Set[_]] is not specific enough. The compiler doesn’t know, that the less specific instance is allowed here. You can help it by adding an explicit type to the call:

@ concat[Set[_]](Set(1,2), Set(3,4)) 
res13: Set[_] = Set(1, 2, 3, 4)

Note, that the compiler loses type information this way, the result is now a Set of unknown type, not a Set[Int]

2 Likes
3

Note that you can have singe instance of Monoid and then cast it in implicit method:

  implicit def setUnion[A]: Monoid[Set[A]] =
    _setUnion.asInstanceOf[Monoid[Set[A]]

  private val _setUnion = new Monoid[Set[_]] {
    override def empty: Set[_] =
      Set.empty

    override def combine(x: Set[_], y: Set[_]): Set[_] =
      x ++ y
  }

This way you have good type inference and low memory overhead.

3 Likes
4

Also note, that if you’re using the cats library, there is MonoidK, which handles monoids for higher kinded types like this.

1 Like