Understanding the use of path dependent types to emulate existentially quantified types

Question

I've been following along with this blog post, trying to understand how to emulate existentially quantified types using path-dependent types in Scala 3: https://dev.to/raquo/existential-crisis-implementing-mapk-in-scala-3-2fo1

And then I made the following example.

First we define monoids:

trait Monoid[A]:
  val id: A
  def combine(l: A, r: A): A

object StringMonoid extends Monoid[String]:
  val id = ""
  def combine(l: String, r: String) = l + r

object AdditiveIntMonoid extends Monoid[Int]:
  val id = 0
  def combine(l: Int, r: Int) = l + r

object MultiplicativeIntMonoid extends Monoid[Int]:
  val id = 1
  def combine(l: Int, r: Int) = r * r

Now suppose I want to write code that can take a set of monoids that may not all have the same underlying type. For example

def ids(ms: Monoid*) =        // This won't compile because Monoid with no argument 
  for { m <- ms } yield m.id           //  is not a type

or

def asList(pairs: ((E, Monoid[E]) for any E)*) =   // This is also not valid scala
  pairs.toList

I can, with some work, achieve the behavior I want by following the pattern in the blog.

First define a type with a path-dependent inner type to emulate forSome:

type any[F[_]] = {
  type Member;
  type Ops = F[Member]
}

and a couple of poorly named implicit conversions to help me make instances of the relevant types:

given any_algebra[F[_], A]: Conversion[F[A], any[F]#Ops] = _.asInstanceOf[any[F]#Ops]
given any_algebra_with_member[F[_], A]: Conversion[(A, F[A]), (any[F]#Member, any[F]#Ops)] =
    _.asInstanceOf[(any[F]#Member, any[F]#Ops)]

And now I can write

def ids(ms: List[any[Monoid]#Ops]) =
  for { m <- ms } yield m.id

def all[F[_]](fs: any[F]#Ops*) = fs.toList

val ms = all(StringMonoid, MultiplicativeIntMonoid, AdditiveIntMonoid, StringMonoid)

val units = ids(all(AdditiveIntMonoid, StringMonoid, MultiplicativeIntMonoid))

def many[F[_]](pairs: (any[F]#Member, any[F]#Ops)*) = pairs.toList

val mms = many(
  7 -> AdditiveIntMonoid,
  3 -> MultiplicativeIntMonoid,
  "foo" -> StringMonoid,
  "bar" -> StringMonoid
)

and it all works. I cannot write

val ms = all(StringMonoid, "hello", AdditiveIntMonoid, StringMonoid)

because "hello" is not a Monoid, or

val mms = many(
  "foo" -> StringMonoid,
  3 -> StringMonoid
)

because 3 is not a string.

My question is why this last part works as I want it to. Why can't I write many(3 -> StringMonoid)? In def many[F[_]](pairs: (any[F]#Member, any[F]#Ops)*), what constrains both appearances of any[F] within the tuple type to refer to the same type? Where (in the Scala language specification or anywhere else) should I start reading to be able to understand this from first principles?

Answer 1

It's because you have this implicit conversion

Conversion[(A, F[A]), (any[F]#Member, any[F]#Ops)]

many accepts tuples of (any[F]#Member, any[F]#Ops). So when you supply the tuple "foo" -> StringMonoid the compiler uses that implicit conversion to convert it to a tuple of the requested type. But that conversion only works for tuples that conform to the shape of (A, F[A]). I.e. the A in both members has to be the same type. But when you supply 3 -> StringMonoid the left A is Int and the right A is String, so the implicit conversion will not work.

The compiler may still try to make it work by inferring A = Any, but Monoid[String] is not a subtype of Monoid[Any] because it is invariant. So that won't work either.