Implicit type class for updating maps
Using CanBuildFrom will help you here. What you need is an implicit CanBuildFrom[M[K, T], (K, T), M[K, T]] in scope, which will be provided by the standard library if it is possible to construct instances of the correct types.

import scala.collection.generic.CanBuildFrom

implicit def mapUpdatedFunctor[M[KT, TT] &lt;: Map[KT, TT], K, T]
  (implicit cbf: CanBuildFrom[M[K, T], (K, T), M[K, T]]) = {
  new UpdatedFunctor[M[K, T], K, T] {
    override def upd(a: M[K, T], k: K, t: T): M[K, T] = {
      val builder = cbf()
      builder ++= a.updated(k, t)
      builder.result()
    }
  }
}

scala&gt; m.upd("A", "2")
res1: scala.collection.immutable.Map[String,String] = Map(A -&gt; 2)

scala&gt; sm.upd("A", "2")
res3: scala.collection.immutable.SortedMap[String,String] = Map(A -&gt; 2)


I actually answered a similar question recently using Maps and updated on SO.