Variance + Type inference vs. Type checking

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Variance + Type inference vs. Type checking

Johannes Rudolph-2
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
Reply | Threaded
Open this post in threaded view
|

Re: Variance + Type inference vs. Type checking

Adriaan Moors-4

On Tue, Dec 28, 2010 at 1:28 PM, Johannes Rudolph <[hidden email]> 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)

cheers
adriaan

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)
Reply | Threaded
Open this post in threaded view
|

Re: Variance + Type inference vs. Type checking

Viktor Klang
In reply to this post by Johannes Rudolph-2
Hack the planet!!! :D

On Tue, Dec 28, 2010 at 1:28 PM, Johannes Rudolph <[hidden email]> 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
Follow: twitter.com/viktorklang
Read:   klangism.tumblr.com

Reply | Threaded
Open this post in threaded view
|

RE: Variance + Type inference vs. Type checking

Chris Marshall
In reply to this post by Johannes Rudolph-2
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: [hidden email]
> 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...
Reply | Threaded
Open this post in threaded view
|

Re: Variance + Type inference vs. Type checking

Jim Balter-2
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 <[hidden email]> 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: [hidden email]
>> 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...
>
Reply | Threaded
Open this post in threaded view
|

Re: Variance + Type inference vs. Type checking

Jim Balter-2
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 <[hidden email]> 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 <[hidden email]> 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: [hidden email]
>>> 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...
>>
>