Regression in match types combined with type lambda

[WojciechMazur]

Based on forum post: https://users.scala-lang.org/t/scala-3-how-do-we-make-a-lambda-type-conform-to-a-subtype/9805

Compiler version

3.3.1
Last good release: 3.3.1-RC1-bin-20230514-b0ccf40-NIGHTLY
First bad release: 3.3.1-RC1-bin-20230515-22b2259-NIGHTLY
Bisect points to d1d6c2e

Minimized code

import scala.util.NotGiven

type HasName1 = [n] =>> [x] =>> x match {
    case n => true
    case _ => false
  }
@main def Test = {
  summon[HasName1["foo"]["foo"] =:= true]
  summon[NotGiven[HasName1["foo"]["bar"] =:= true]]
  summon[Tuple.Filter[(1, "foo", 2, "bar"), HasName1["foo"]] =:= Tuple1["foo"]] // error
}

Output

-- [E057] Type Mismatch Error: /Users/wmazur/projects/dotty/bisect/main.scala:10:44 
10 |  summon[Tuple.Filter[(1, "foo", 2, "bar"), HasName1["foo"]] =:= Tuple1["foo"]]
   |                                            ^
   |Type argument HasName1[("foo" : String)] does not conform to upper bound [_] =>> Boolean
   |
   |Note: a match type could not be fully reduced:
   |
   |  trying to reduce  HasName1[("foo" : String)]
   |
   | longer explanation available when compiling with `-explain`
1 error found

Expectation

Should comile (probably)

[WojciechMazur]

Not sure to whom it should be assigned. Maybe @dwijnand (merged the PR) or @odersky (supervision?)?

[odersky]

Maybe @sjrd could take a look.

[EugeneFlesselle]

I believe this is as expected given the current subtyping rules for match types.
Unless an upper bound is declared, the unreduced match type is not determined to be <: Boolean.

type HasFoo[X] <: Boolean = X match {
  case "foo" => true
  case _ => false
}
type HasBar[X] = X match {
  case "bar" => true
  case _ => false
}

type F1 = Tuple.Filter[(1, "foo", 2, "bar"), HasFoo] // Ok
type F2 = Tuple.Filter[(1, "foo", 2, "bar"), HasBar] // Error

[hmf]

@EugeneFlesselle I was the one who originally posted the question in scala-users discourse. I am aware that the "standard" match type above works and agree with you. However, I am using a type lambda that takes in a type parameter. So my question is, how do I add the upper bound in this case? I have tried the obvious, but that does not seem to work.

TIA

[EugeneFlesselle]

@hmf Unfortunately, upper bounds are simply not supported for type lambdas. In fact, I think they can only appear in an alias for a match type, as they can be necessary when defining recursive match types.

So in this case you are forced to use type aliases, ending up with something like:

type HasName2[N] = [M] =>> HasName3[N, M]
type HasName3[N, M] <: Boolean = M match
  case N => true
  case M => false

summon[Tuple.Filter[(1, "foo", 2, "bar"), HasName2["foo"]] =:= Tuple1["foo"]] // Ok

[EugeneFlesselle]

It's also debatable whether the parameter P of Tuple.Filter needed such an upper bound to begin with. You could also define:

type Filter1[T <: Tuple, P[_]] = T match
  case EmptyTuple => EmptyTuple
  case h *: t => P[h] match
    case true => h *: Filter1[t, P]
    case false => Filter1[t, P]

summon[Filter1[(1, "foo", 2, "bar"), HasName1["foo"]] =:= Tuple1["foo"]] // Ok

[hmf]

@EugeneFlesselle Thanks for the information. Your type alias solution is ok for me. As for the Tuple.Filter upper bound, personally I think it is ok too.