CODEWITHSUNDEEP
scalapolymorphismimplicit
kmh
kmh

Reputation: 1586

nested polymorphism in scala

I need an implicit class with a method that lets me merge any immutable map types (<: Map) that may have duplicate keys & polymorphic values. I can't figure out to get the implicit class to use nested polymorphic types and work implicitly (something like A <: Map[_, B], B <: Combinable[B]).

I can get it to work on all Map types... or on polymorphic values... but not both. I can't figure out how to combine into one implicit class without the error that it can't find the method in the implicit class.

So for example...

trait Combinable[A] {
  this: A =>

  def combine(that: A): A

  def combine(that: Option[A]): A = that match {
    case Some(a) => this combine a
    case None => this
  }
}

So let's say I have a class...

case class Meta(???) extends Combinable[Meta] {
  def combine(that: Meta): Meta = ???
}

Now if I have a standard immutable Map, it's a cinch... works great.

implicit class CombinableMaps[A <: Combinable[A]](val m1: Map[String, A]) {
  def mergeMaps(m2: Map[String, A]): Map[String, A] = {  
    m1 ++
    m2.map { case (k,v) => k -> (v combine m1.get(k)) }
  }.asInstanceOf[Map[String, A]]
}

But what if I want it to also work on TreeMaps and SortedMaps and whatever else?

implicit class CombinableMaps[B <: Combinable[B], A <: Map[String,B]](val m1: A) {
  def mergeMaps(m2: A): A = {  
    m1 ++
    m2.map { case (k,v) => k -> (v combine m1.get(k)) }
  }.asInstanceOf[A]
}

This compiles without an error, but when I try using the mergeMap method it throws error: value mergeMaps is not a member of Map[String,Meta].

I tried a variation where B was a type passed to A like A[B]... again, compiled (if I imported scala.language.higherKinds) but didn't get applied.

Is this kind of nested polymorphism allowed? I can't even figure out what term to search for.

Thanks in advance.

Upvotes: 0

Views: 204

Answers (2)

Dmytro Mitin
Dmytro Mitin

Reputation: 51658

Besides @francoisr's proposal where your approach with F-bounded polymorphism (B <: Combinable[B]) is proposed to be replaced with ad hoc polymorphism (Combinable becomes a type class), you can also try to replace bounds with implicit constraints. Try to replace

implicit class CombinableMaps[B <: Combinable[B], A <: Map[String, B]](val m1: A) {
  def mergeMaps(m2: A): A = {  
    m1 ++
    m2.map { case (k,v) => k -> (v combine m1.get(k)) }
  }.asInstanceOf[A]
}

with

implicit class CombinableMaps[A, B](val m1: A)(implicit
  ev: A <:< Map[String, B],
  ev1: B <:< Combinable[B]
) {
  def mergeMaps(m2: A): A = {
    m1 ++
      m2.map { case (k,v) => k -> (v combine m1.get(k)) }
  }.asInstanceOf[A]
}

or just

implicit class CombinableMaps[A, B <: Combinable[B]](val m1: A)(implicit
  ev: A <:< Map[String,B]
) {
  def mergeMaps(m2: A): A = {
    m1 ++
      m2.map { case (k,v) => k -> (v combine m1.get(k)) }
  }.asInstanceOf[A]
}

Then Map("a" -> Meta(1), "b" -> Meta(2)).mergeMaps(Map("c" -> Meta(3), "d" -> Meta(4))) compiles [scastie]

Also I propose to remove this ugly asInstanceOf[A] [scastie]

import scala.collection.immutable.MapOps

implicit class CombinableMaps[A, B <: Combinable[B], 
                              CC[K,+V] <: MapOps[K, V, CC, _]](val m1: A)(implicit
  ev0: A => CC[String, B],
  ev2: CC[String, B] => A,
) {
  def mergeMaps(m2: A): A = {
    m1 ++
      m2.map { case (k,v) => k -> (v combine m1.get(k)) }
  }
}

or just

implicit class CombinableMaps[B <: Combinable[B], 
                              CC[K,+V] <: MapOps[K, V, CC, _]
                             ](val m1: CC[String, B]){
  def mergeMaps(m2: CC[String, B]): CC[String, B] = {
    m1 ++
      m2.map { case (k,v) => k -> (v combine m1.get(k)) }
  }
}

Upvotes: 3

francoisr
francoisr

Reputation: 4585

The key to solving your issue is to not try to infer A immediately. Even something as simple will trip the type inference:

class Foo[B, A <: Map[String, B]](val a: A)
new Foo(Map("foo" -> 42))

inferred type arguments [Nothing,scala.collection.immutable.Map[String,Int]] do not conform to value 's type parameter bounds [B,A <: Map[String,B]]

type mismatch;
 found   : scala.collection.immutable.Map[String,Int]
 required: A

This is because type inference works in "layers": it resolves both A and B before it can inspect the "insides" of A. The solution is to define A differently:

class Foo[B, A[X] <: Map[String, X]](val a: A[B])
new Foo(Map("foo" -> 42))

Let's look at your problem now. Your Combinable trait would typically be replaced by a type class so that you don't have to extend Combinable on every type A you would need to combine. You can just implicitly provide the Combinable implicitly for every type you need it. This is entirely optional, you could choose to stick with your trait if you prefer that.

trait Combinable[A] {
  def combine(first: A, second: A): A
  def combine(first: A, second: Option[A]): A = second match {
    case Some(a) => combine(first, a)
    case None => first
  }
}

case class Meta(x: Int)
object Meta {
  implicit val combinableInstance: Combinable[Meta] = (first, second) => Meta(first.x + second.x)
}


implicit class CombinableMaps[B : Combinable, A[X] <: Map[String,X]](val m1: A[B]) {
  def mergeMaps(m2: A[B]): A[B] = {  
    m1 ++
    m2.map { case (k,v) => k -> implicitly[Combinable[B]].combine(v,m1.get(k)) }
  }.asInstanceOf[A[B]]
}

import collection.immutable.TreeMap
val m = TreeMap("foo" -> Meta(42), "bar" -> Meta(43))
val m2 = TreeMap("bar" -> Meta(43))
val m3: TreeMap[String,Meta] = m.mergeMaps(m2)

Upvotes: 4

Related Questions