Generic 'diff' implementation for Maps

Generic-Map-Diff

import scalaz._
import Scalaz._

val m1 = Map(1 -> Set(2))
val m2 = Map(2 -> Set(5))
val m3 = Map(1 -> Set(3))
val tot = m1 |+| m2 |+| m3

tot.keySet -- m1.keySet
m1.keySet  -- tot.keySet

trait DiffProvider[M[_]] {
  def diffSize[A](m1: M[A], m2: M[A]): Int
  def doDiff[A](m1: M[A], m2: M[A]): M[A]
}

object DiffProvider {
  implicit object SetDiffProvider extends DiffProvider[Set] {

    override def diffSize[A](m1: Set[A], m2: Set[A]): Int = doDiff(m1, m2).size

    override def doDiff[A](m1: Set[A], m2: Set[A]): Set[A] = m1.diff(m2)
  }
  
  implicit object ListDiffProvider extends DiffProvider[List] {
    override def diffSize[A](m1: List[A], m2: List[A]): Int = doDiff(m1,m2).size

    override def doDiff[A](m1: List[A], m2: List[A]): List[A] = m1.diff(m2)
  }
}

def diff[K,M[_],E](total: Map[K, M[E]], toRemove: Map[K, M[E]])(implicit diffProvider: DiffProvider[M]): Map[K, M[E]] = {
  total collect {
    case (key, set) if !toRemove.contains(key) => (key, set)
    case (key, set) if toRemove.contains(key) && diffProvider.diffSize(set, toRemove(key)) > 0 => (key, diffProvider.doDiff(set, toRemove(key)))
    // removes keys from which all elements are removed
  }
}
diff(tot, m1 |+| m3)
diff(tot, m1)
diff(tot, m1 |+| m2)
diff(tot, m2)
diff(tot, m2 |+| m3)
diff(tot, m3)

diff(tot, m1 |+| m3) === m2
diff(tot, m1) === (m2 |+| m3)
diff(tot, m1 |+| m2) === m3
diff(tot, m2) === (m1 |+| m3)
diff(tot, m2 |+| m3) === m1
diff(tot, m3) === (m1 |+| m2)

diff(Map(1 -> List(1,2), 2 -> List(1,2,3)), Map(2 -> List(2)))