[scala] Implicit Priorirty with Contravariant Type

[Jason Zaugg]

In Scalaz, we have instances of the FoldRight type class for Iterable
and Stream. The Stream instance handles infinite streams lazily.

However, when requesting an implicit of FoldRight[Stream], I get
FoldRight[Iterable]. This example demonstrates the problem:
http://gist.github.com/260886.

We could make FoldRight invariant to solve this, but then would have
to write boilerplate for all know subtypes of Iterable, just to
specialise for Stream.

1. Why is FoldRight[Iterable] preferred to FoldRight[Stream]?
Intuitively, FoldRight[Stream] is more specific.
2. Is there any trick to make FoldRight[Iterable] lower in priority to
FoldRight[Stream]? The usual trick to place a conversion in a super
class only makes them of equal priority.

I'm using 2.8.0 Beta RC4.

Thanks,

-jason

[Jason Zaugg]

Here is a distilled example: http://gist.github.com/260934

The compiler prefers the implicit that returns FoldRight[Iterable]
because FoldRight[Iterable] <:< FoldRight[Stream], as checked in
Infer.isAsSpecificValueType(). This makes sense to me now, even if it
doesn't help in this situation.

After looking at the selection algorithm in Infer.scala, I don't see
any way force prioritization of FoldRight[Stream]. About all I could
suggest is an annotation to provide further control over implicit
prioritisation, ie to add (1, 0, or -1) to the calculated priority
based on the subclass and specificity rules.

-jason

On Mon, Dec 21, 2009 at 11:01 AM, Jason Zaugg <[hidden email]> wrote:

> 1. Why is FoldRight[Iterable] preferred to FoldRight[Stream]?
> Intuitively, FoldRight[Stream] is more specific.
> 2. Is there any trick to make FoldRight[Iterable] lower in priority to
> FoldRight[Stream]? The usual trick to place a conversion in a super
> class only makes them of equal priority.
>
> I'm using 2.8.0 Beta RC4.
>
> Thanks,
>
> -jason
>

[Jason Zaugg]

I'll end this little discussion with myself by abandoning
contravariance and sharing some links -- a wontfix ticket describing
this very quandry [1], the attempt to make Ordering contravariant in X
similarly derailed, and a hopeful plea that one day this may all work
differently [3]

Nuttycom said it best: "What I find surprising about this is that
specificity is conflated with the direction of the variance. At least
to my mind, variance is associated with substitutability, whereas
specificity is a unidirectional relation in the direction of
covariance.

The concepts aren't totally orthogonal; it's more like there should be
a distinction between subclassing (where subclasses are always more
specific) and subtyping, where an instance of a subtype is always
substitutable for an instance of the supertype."

[1] http://lampsvn.epfl.ch/trac/scala/ticket/2509
[2] http://old.nabble.com/Contravariant-Ordering-T-,-java.util.Comparator,-and--uncheckedVariance-td25979631.html
[3] http://article.gmane.org/gmane.comp.lang.scala.internals/2464

On Mon, Dec 21, 2009 at 2:03 PM, Jason Zaugg <[hidden email]> wrote:

> Here is a distilled example: http://gist.github.com/260934
>
> The compiler prefers the implicit that returns FoldRight[Iterable]
> because FoldRight[Iterable] <:< FoldRight[Stream], as checked in
> Infer.isAsSpecificValueType(). This makes sense to me now, even if it
> doesn't help in this situation.
>
> After looking at the selection algorithm in Infer.scala, I don't see
> any way force prioritization of FoldRight[Stream]. About all I could
> suggest is an annotation to provide further control over implicit
> prioritisation, ie to add (1, 0, or -1) to the calculated priority
> based on the subclass and specificity rules.
>
> -jason
>
> On Mon, Dec 21, 2009 at 11:01 AM, Jason Zaugg <[hidden email]> wrote:
>> 1. Why is FoldRight[Iterable] preferred to FoldRight[Stream]?
>> Intuitively, FoldRight[Stream] is more specific.
>> 2. Is there any trick to make FoldRight[Iterable] lower in priority to
>> FoldRight[Stream]? The usual trick to place a conversion in a super
>> class only makes them of equal priority.
>>
>> I'm using 2.8.0 Beta RC4.
>>
>> Thanks,
>>
>> -jason
>>
>