scalascalazsemigroup

Why there is no Semigroup instance for TrieMap in scalaz


While I can do

Map("a" -> 1) |+| Map("a" -> 2)

It seems there is no support for

TrieMap("a" -> 1) |+| TrieMap("a" -> 2)

Why ?


Solution

  • Scalaz doesn't provide every possible Type+Operation combination that form a Semigroup, but you can easily implement it, for instance with the following implicit:

    import scala.collection.concurrent.TrieMap
    import scalaz._, Scalaz._
    
    implicit def trieMapSemigroup[K: BuildKeyConstraint, V: Semigroup]: Semigroup[TrieMap[K, V]] =
      new Semigroup[TrieMap[K, V]] {
        def append(m1: TrieMap[K, V], m2: => TrieMap[K, V]) =
          (m1 /: m2) { case (res, (k, v)) =>
            res += (k -> res.get(k).cata(Semigroup[V].append(_, v), v))
          }
      }
    

    That gives you as expected:

    scala> TrieMap("a" -> 1) |+| TrieMap("a" -> 2)
    res: TrieMap(a -> 3)
    

    Of course that will work for every value as semigroup that has been defined in scalaz.


    What about Monoid?

    If you want an optimised version of the implicit that works as a Monoid too:

      implicit def trieMapMonoid[K: BuildKeyConstraint, V: Semigroup]: Monoid[TrieMap[K, V]] = new Monoid[TrieMap[K, V]] {
        def zero = TrieMap.empty[K, V]
    
        def append(m1: TrieMap[K, V], m2: => TrieMap[K, V]) = {
          val m2Instance: TrieMap[K, V] = m2
          val (from, to, semigroup) = {
            if (m1.size > m2Instance.size) (m2Instance, m1, Semigroup[V].append(_: V, _: V))
            else (m1, m2Instance, (Semigroup[V].append(_: V, _: V)).flip)
          }
          from.foldLeft(to) {
            case (res, (k, v)) => res += (k -> res.get(k).map(semigroup(_, v)).getOrElse(v))
          }
        }
      }
    

    (code shameless adapted from scalaz/std/Map.scala)