Type bounds for higher-kinded types

Question
1

Is it possible to somehow provide a type bound for a higher-kinded type, something like F[A] <: G[A] for each A? After all, the higher-kinded types allow such relations, for example: Some and Option, List and Seq.

Or is it enough in practice for this relationship to hold for some particular type, for example F[Any] <: G[Any], and that would implicitly mean the former?

Here is the example that puzzles me: Scastie - An interactive playground for Scala.

trait Bind[F[_]]:
  extension [A](fa: F[A])
    def myMap[B](f: A => B): F[B]
    def myFlatMap[B](f: A => F[B]): F[B]

given Bind[Option] with
  extension [A](fa: Option[A])
    def myMap[B](f: A => B): Option[B] = fa.map(f)
    def myFlatMap[B](f: A => Option[B]): Option[B] = fa.flatMap(f)

def tuple[F[_]: Bind, A, B](fa: F[A], fb: F[B]): F[(A, B)] =
  fa.myFlatMap(a => fb.myMap((a, _)))

def tuple2[F[Any] <: G[Any], G[_]: Bind, A, B](fa: F[A], fb: F[B]): G[(A, B)] =
  fa.myFlatMap(a => fb.myMap((a, _)))

tuple[Option, Int, String](Some(1), Some("aaa"))
tuple2(Some(1), Some("aaa"))
//tuple(Some(1), Some("aaa"))

Somehow, the tuple2 compiles and even produces the expected result in the case of two Some-values, whereas tuple throws a compile error “No given instance of type Bind[Some] was found”.

And it even does not matter which type I use: Any, A, B, or anything else, really. I can even use G[Any]: Bind and it will still work!

2

Your local grug here trying to think through this…

  1. Scala has what are essentially single generic definitions for higher minded types - so there is only one generic shape for F[Int], F[String] etc. Contrast this with C++ way back in the day, where a template instantiation could have any shape it wanted to via specialisations, partial or otherwise. (Yes, there are specialisations in Scala too, but I think they are constrained to respect the type signature shape of the core generic construct).

  2. So if F[X] <: G[X] for some X, it is for all Xs.
    (Incidentally, how can one express this in Scala 3?
    Scala 2.* had syntax for this - my best guess without a Scala environment to try this out on is to use a type lambda to connect F, G and X…)

I presume you started off trying to write that code with an existential to tie F and G together and stumbled across that way if doing it…

I’ll wait for the heavy mob to cook up some counterexample to my claim in point #2 using multiple inheritance of traits with some method that takes a specific X. :smile:

Incidentally, I didn’t know about the technique of defining extensions in givens - it seems to pare down type classes right down to the essentials, as you don’t need the syntax enhancing wrapper anymore. Nice.

1 Like
3

It’s in the docs as the “default idiomatic way” of doing type classes.

1 Like
4

@drybalka

Try

def tuple2[F[t] <: G[t], G[_] : Bind, A, B](fa: F[A], fb: F[B]): G[(A, B)] =
  fa.myFlatMap(a => fb.myMap((a, _)))
1 Like
5

@sageserpent-open

  1. So if F[X] <: G[X] for some X , it is for all X s.

That’s not true:

  class Parent
  class Child extends Parent

  type F[X] = X match
    case Int => Child
    case _ => Parent

  type G[X] = X match
    case Int => Parent
    case _ => Child

  implicitly[F[Int] <:< G[Int]]
  implicitly[G[String] <:< F[String]]
1 Like
6

@drybalka Now about why F[Any] <: G[Any] works.

Any in def tuple2[F[Any] <: G[Any]... is not scala.Any. You introduced a type parameter and denoted it Any. It doesn’t matter how to denote a type parameter. So def tuple2[F[Any] <: G[Any]... was actually def tuple2[F[t] <: G[t]...

1 Like
7

@DmytroMitin

I thought someone would be able to find a counterexample. Congratulations! Now you’ve got me thinking whether my claim would even hold for class / trait types…

So if I understand your previous response correctly, the use of X as a free variable in a generic specifier like [F[X]] introduces an existential type with a named type parameter? I guess you don’t need an underscore to denote an existential type, then. I may be confusing an existential type with a straight definition of a higher kinded type…

If so, then this seems to answer my question from the quoted text. Is this just a Scala 3 thing? I remember writing forSome type X in Scala 2 existentials to name a shared type variable, seems like this is the replacement technique…

EDIT:

I had to try this out:

type Oddity1[F[_] <: Seq[Double]] = F[Int]
type Oddity2[F[Double] <: Seq[Double]] = F[Int]


val odd1: Oddity1[List] = ???
val odd2: Oddity2[List] = ???

Both type aliases check out OK, but I notice IntelliJ takes Double in Oddity1 to be good old scala.Double. This makes sense, it’s just a type bound, there is no reason for the type bound to introduce type variables in its own right.

In Oddity2, Double is a type variable.

Note that odd1 fails type-checking (which makes sense) whereas odd2 is fine.

I’m still curious as to whether this was introduced in Scala 3 as a replacement for forAll, or has it been there all the time in Scala 2.*?

No, it seems it’s always been there. I was reminded that the syntax for existentials is being prised away from higher-kinded type definitions, came across this again: Wildcard Arguments in Types.

You learn something every day.