# Variance + Type inference vs. Type checking

5 replies
Johannes Rudolph 2
Joined: 2010-02-12, Hi all,

I just found out about a "pattern" which seems to help when covariance
hinders type inference. I wonder if anyone else has occurred something
similar or if anyone can comment about if that has some deeper
meaning:

Say we have a covariant container and a function which operates on
functions with a parameter of that covariant type:

case class XR[+T](value: T)

def f[T](x: XR[T] => Unit): XR[T] = null

I now would like to be able to infer the type of parameter x from the
return type:

def a: XR[String] = f(x => XR(x.value))

This fails with "Missing parameter type" and the explanation why type
inference doesn't work here is, because covariance of XR and
contravariance of Function1 introduces a degree of freedom for the
type T.

Now, we can make it work simply by introducing an "invariant view" X
of type XR and use it everywhere instead of XR:

case class XR[+T](value: T)
type X[T] = XR[T]

def f[T](x: X[T] => Unit): X[T] = null
def a: X[String] = f(x => XR(x.value))

The advantage of this solution is that type inference still works as
expected and you can still rely on covariance because type checking
seems to be done after replacing the type definitions:

def other: XR[CharSequence] => Unit = null
def b: X[String] = f(other)

Joined: 2010-02-08, Re: Variance + Type inference vs. Type checking

On Tue, Dec 28, 2010 at 1:28 PM, Johannes Rudolph <johannes [dot] rudolph [at] googlemail [dot] com> wrote:
Now, we can make it work simply by introducing an "invariant view" X
of type XR and use it everywhere instead of XR:

case class XR[+T](value: T)
type X[T] = XR[T]
aha! that's an interesting observation!
you're basically "kind casting" the type XR (which has kind * -(+)-> *) to a type of kind * -> *   (where the +/- on the arrow of course indicates the variance of the type constructor).
looking at it this way, you can also use this pattern to introduce stricter bounds on type arguments, since that results in a "kind-safe" upcast
so now we have kind casting, we need[*] kind polymorphism to get rid of them (similarly to how the introduction of generics in Java got rid of a whole class (haha) of casts)
ps: [*] don't worry, I'm mostly speaking from an academic point of view, Scala 2.9 (or any version in the near future) will not have any of these crazy kind-level features, but I believe it could end up in the language "one day" if we can figure out a way to make it so that it actually simplifies the language (by making it more uniform). You could argue that since we can already express type-level functions and kind casts using type aliases, that we might as well support them directly so we can provide better syntax and "kind checking".  (we already do kind inference and kind checking in the compiler internally, albeit in a somewhat obscure way)
Viktor Klang
Joined: 2008-12-17, Re: Variance + Type inference vs. Type checking
Hack the planet!!! :D

On Tue, Dec 28, 2010 at 1:28 PM, Johannes Rudolph <johannes [dot] rudolph [at] googlemail [dot] com> wrote:
Hi all,

I just found out about a "pattern" which seems to help when covariance
hinders type inference. I wonder if anyone else has occurred something
similar or if anyone can comment about if that has some deeper
meaning:

Say we have a covariant container and a function which operates on
functions with a parameter of that covariant type:

case class XR[+T](value: T)

def f[T](x: XR[T] => Unit): XR[T] = null

I now would like to be able to infer the type of parameter x from the
return type:

def a: XR[String] = f(x => XR(x.value))

This fails with "Missing parameter type" and the explanation why type
inference doesn't work here is, because covariance of XR and
contravariance of Function1 introduces a degree of freedom for the
type T.

Now, we can make it work simply by introducing an "invariant view" X
of type XR and use it everywhere instead of XR:

case class XR[+T](value: T)
type X[T] = XR[T]

def f[T](x: X[T] => Unit): X[T] = null
def a: X[String] = f(x => XR(x.value))

The advantage of this solution is that type inference still works as
expected and you can still rely on covariance because type checking
seems to be done after replacing the type definitions:

def other: XR[CharSequence] => Unit = null
def b: X[String] = f(other)

--
Johannes

-----------------------------------------------
Johannes Rudolph
http://virtual-void.net

--
Viktor Klang,
Code Connoisseur
Work:   Scalable Solutions
Code:   github.com/viktorklang

Chris Marshall
Joined: 2009-06-17, RE: Variance + Type inference vs. Type checking
What is the use-case here? I cannot understand what implementation of this function there could possibly be:

> def f[T](x: XR[T] => Unit): XR[T] = error("Erk")

> From: johannes [dot] rudolph [at] googlemail [dot] com
> Subject: [scala-debate] Variance + Type inference vs. Type checking
>
> I just found out about a "pattern" which seems to help when covariance
> hinders type inference...
jibal
Joined: 2010-12-01, Re: Variance + Type inference vs. Type checking

Surely you can imagine implementations of

def f[T](): XR[T]

or

def f[T](x: Any => Unit): XR[T]

so why not

def f[T](x: XR[T] => Unit): XR[T]

? As I understand Johanne's post, the relevance of that specific
parameter type for x is that it defeats inference of f's return type.

On Wed, Dec 29, 2010 at 3:48 AM, Chris Marshall wrote:
> What is the use-case here? I cannot understand what implementation of this
> function there could possibly be:
>
>> def f[T](x: XR[T] => Unit): XR[T] = error("Erk")
>
>> From: johannes [dot] rudolph [at] googlemail [dot] com
>> Subject: [scala-debate] Variance + Type inference vs. Type checking
>>
>> I just found out about a "pattern" which seems to help when covariance
>> hinders type inference...
>

jibal
Joined: 2010-12-01, Re: Variance + Type inference vs. Type checking

Although, come to think of it, since the object of type T must be
manufactured out of thin air, any useful implementation does seem out
of reach. I do wonder if there's some mixup in Johanne's types:

def f[T](x: X[T] => Unit): X[T] = null
def a: X[String] = f(x => XR(x.value))

f's parameter x returns Unit but is being called with a function that
returns XR[T].

On Wed, Dec 29, 2010 at 3:53 PM, Jim Balter wrote:
> Surely you can imagine implementations of
>
> def f[T](): XR[T]
>
> or
>
> def f[T](x: Any => Unit): XR[T]
>
> so why not
>
> def f[T](x: XR[T] => Unit): XR[T]
>
> ?  As I understand Johanne's post,  the relevance of that specific
> parameter type for x is that it defeats inference of f's return type.
>
>
> On Wed, Dec 29, 2010 at 3:48 AM, Chris Marshall wrote:
>> What is the use-case here? I cannot understand what implementation of this
>> function there could possibly be:
>>
>>> def f[T](x: XR[T] => Unit): XR[T] = error("Erk")
>>
>>> From: johannes [dot] rudolph [at] googlemail [dot] com
>>> Subject: [scala-debate] Variance + Type inference vs. Type checking
>>>
>>> I just found out about a "pattern" which seems to help when covariance
>>> hinders type inference...
>>
>

Copyright © 2012 École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland