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

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

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?

CodePudding user response：

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.