Imported From: https://issues.scala-lang.org/browse/SI-5075?orig=1
Reporter: @Blaisorblade
Affected Versions: 2.9.1, 2.9.2
See #2712
Attachments:

• BugReport.scala (created on Oct 14, 2011 7:49:06 PM UTC, 1307 bytes)

@retronym said:
The problem is with type argument inference, rather than with unification. AFAIK, scalac never infers a partially applied type constructor, even if it is handed to it on a plate, as in your example.

So probably a duplicate of #2712, although Adriaan will be the final arbiter of that.

trait TypeWithHKParam[D[_]]

def function[D[_]](t: TypeWithHKParam[D]) = 1

function(null: TypeWithHKParam[Option]) //okay 

//Does not compile
function(null: TypeWithHKParam[({type l[a] = (Int, a)})#l])

Very nicely reported bug, BTW.

@Blaisorblade said:
Thanks for the prompt answer, it's impressive.
I still hope that this subcase can be handled more easily, since here, unlike in #2712, Scalac does not have to synthesize a type function, but it is handed to it on a plate and it must just be kind-checked and the kind compared with the desired one.

@adriaanm said:
this is not easy to do (in general, no point in solving this for some ad-hoc cases), so classifying as an improvement

seems unlikely to progress in Scala 2

Hold your horses ... this is actually fixed I would guess by the SI-2712 fix.

I think you're being a bit too free with "unlikely to progress in Scala 2".

PR adding a test confirming the fix here: scala/scala#6366.

Fixing 2712 does not fix this, because "Scalac does not have to synthesize a type function, but it is handed to it on a plate and it must just be kind-checked and the kind compared with the desired one" as @Blaisorblade says, which is not what happens with -Ypartial-unification.

You can see this by using #Flip (type Flip[B] = T[B, A]) instead of #Apply in scala/scala#6336.

scala> val param: TypeWithHigherKindParam[PartialApply1Of2[Tuple2, Int]#Apply] = null
param: TypeWithHigherKindParam[[B](Int, B)] = null

scala> function(param)
res2: Int = 1

scala> val param: TypeWithHigherKindParam[PartialApply1Of2[Tuple2, Int]#Flip] = null
param: TypeWithHigherKindParam[[B](B, Int)] = null

scala> function(param)
<console>:14: error: no type parameters for method function: (t: TypeWithHigherKindParam[D])Int exist so that it can be applied to arguments (TypeWithHigherKindParam[[B](B, Int)])
 --- because ---
argument expression's type is not compatible with formal parameter type;
 found   : TypeWithHigherKindParam[[B](B, Int)]
 required: TypeWithHigherKindParam[?D]

       function(param)
       ^
<console>:14: error: type mismatch;
 found   : TypeWithHigherKindParam[[B](B, Int)]
 required: TypeWithHigherKindParam[D]
       function(param)
                ^

scala> function[PartialApply1Of2[Tuple2, Int]#Flip](param)
res4: Int = 1

What's more annoying is that inference here would rely on not dealiasing too much, while other inference issues would be fixed by dealiasing more. Which is impossible to balance.
I was also unhappy at how the SI-2712 fix relied on aliasing for control. Wonder if the Flip example could be fixed by additional indirection through additional aliases?

It'd be more principled to use some newtype type constructor, like in Haskell:

trait PartialApply1Of2[T[_, _], A] {
  class Apply[B](unwrap: T[A, B]) extends AnyVal
  class Flip[B](unwrap: T[B, A]) extends AnyVal
}

so that any amount of dealiasing couldn't change the result of type inference—the user has to explicitly coerce between the newtype and its implementation. It's as if you had aliases and a way of telling when the typechecker should unfold the alias (and replace it by its definition) and refold it (and replace the definition by the alias).

That would demand better value types—maybe opaque types could handle this? But since the typechecker can see the implementation of an opaque type (supposedly), it's not obvious they could be used to control inference.
Value classes seem more clearly/directly applicable, especially if extended through JVM support, but that doesn't have a clear timeline.

Overall, compared to Haskell, it's cool that you can write out type lambdas and pass them explicitly (and we should retain that possibility), but we know that inferring them robustly in general doesn't work. Partial-unification approaches the Haskell approach but still infers type lambdas, unlike Haskell, causing this problem.
I'm happy people are using it successfully now, but that will break if we start adding expectations.

@Blaisorblade I agree on all points. I don't know Dotty very well, but it looks to me that type aliases there are type lambdas under the hood. How does it deal with the conflicting needs to expand / not expand for the sake of unification?

Also I am really excited to have newtypes or whatever we choose to call them in Scala, but in this specific case we don't ever need a value of that type. Workaround today:

trait PartialApply1Of2[T[_, _], A] {
  type Apply[B] >: T[A, B] <: T[A, B]
  type Flip[B] >: T[B, A] <: T[B, A]
}

@joroKr21

I don't know Dotty very well, but it looks to me that type aliases there are type lambdas under the hood.

Type aliases are still aliases — it's just that some aliases are to lambdas, so type Apply[B] = T[A, B] becomes type Apply = [B]T[A, B]. That doesn't mean Apply must be dealiased eagerly — even in Dotty eager dealiasing can trigger cycles.

Also I am really excited to have newtypes or whatever we choose to call them in Scala, but in this specific case we don't ever need a value of that type.

Well, the function call would just use the type, but at some point the code does manipulate actual instances of the type (in non-minimized applications).

It's fun this workaround might work, but at least in DOT (and I suspect in Dotty) type T >: A <: A and type T = A are the same thing.

Type aliases are still aliases — it's just that some aliases are to lambdas, so type Apply[B] = T[A, B] becomes type Apply = [B]T[A, B]. That doesn't mean Apply must be dealiased eagerly — even in Dotty eager dealiasing can trigger cycles.

That's definitely an improvement. In Scala 2 there is existentialAbstraction which does dealias eagerly and is used in a few places, including (I guess) for type projections and thus in the poor man's type lambda encoding.

Well, the function call would just use the type, but at some point the code does manipulate actual instances of the type (in non-minimized applications).

Ah, I was under the impression that you would only use it as a type lambda.

It's fun this workaround might work, but at least in DOT (and I suspect in Dotty) type T >: A <: A and type T = A are the same thing.

Bug or feature 🤔

Caveat: I'm still a PL guy who understands DOT and is learning the real thing, so expect mistakes.

Bug or feature 🤔

Makes sense for the theory, couldn't point to any downside, if it knows the difference when talking to the user?