Scala Type Inference Challenge (or Giving up on recursive types)

moving to scala-internals

---------- Forwarded message ----------
From: "Josh Suereth" <joshua.suereth@gmail.com>
Date: Jun 23, 2011 11:38 PM
Subject: Scala Type Inference Challenge (or Giving up on recursive types)
To: <scala-language@googlegroups.com>, "scala-user" <scala-user@googlegroups.com>

Ok, so we all know that Scala's type inference has issues with higher kinded types.   The workaround of course is to delay inference of types using implicit type constraints.
So, naively, I tried to implement a +: extractor for LinearSeqLike that would extract head :: tail portions of a collection.   Here's my first cut:
object +: {    def unapply[T, Coll <: LinearSeqLike[T, Coll]](t : Coll) : Option[(T, Coll)] =      if (t.isEmpty) None      else Some(t.head -> t.tail) // TODO - Try to remove cast. }
However this fails:
scala> List(1,2,3,4) match { case x +: xs => xs }<console>:16: error: inferred type arguments [Nothing,Coll] do not conform to method unapply's type parameter bounds [T,Coll <: scala.collection.LinearSeqLike[T,Coll]]        List(1,2,3,4) match { case x +: xs => xs }

NOW what do you do with cyclical type constraints, e.g.  trait LinearSeqLike[T, Repr <: LinearSeq[T, Repr]].   That is, How can I define a method that works against LinearSeqLike and preserves the type Repr as much as possible.
Well, so far I'm clueless.   I've tried doing anything possible to delay inference or to find a way to infer the type Repr piecemeal.   Unfortunately, the cyclical reference *mandates* the method signature.   Why haven't I run into this issue yet?
Oh, that's because SeqLike is defined as trait SeqLike[T,Repr]  (No bounds on Repr).  So we can use the inference trick.

Note:  This is all with Scala 2.9.0.1.   
Because I don't have the knowledge (and I'm pretty sure Adrian really really wanted to solve the type inference magikz required here), I've instead created a patch to LinearSeq that reverts to using Casts rather than the type-system such that the classic <:< inference trick can work here as well.
Yes this is duct-tape over a band-aide, with some skin filed off so it'll fit the glove.  Let me know what you think (i.e. is this a worthwhile fix or can we expect better type inference for higher kinded types?)



diff --git a/src/library/scala/collection/LinearSeqLike.scala b/src/library/scala/collection/LinearSeqLike.scalaindex 3f4d6cd..b00625d 100644 --- a/src/library/scala/collection/LinearSeqLike.scala+++ b/src/library/scala/collection/LinearSeqLike.scala@@ -41,7 +41,7 @@ import scala.util.control.Breaks._  *  @tparam A    the element type of the $coll   *  @tparam Repr the type of the actual $coll containing the elements.  */-trait LinearSeqLike[+A, +Repr <: LinearSeqLike[A, Repr]] extends SeqLike[A, Repr] { self: Repr =>+trait LinearSeqLike[+A, +Repr] extends SeqLike[A, Repr] { self: Repr =>     override protected[this] def thisCollection: LinearSeq[A] = this.asInstanceOf[LinearSeq[A]]   override protected[this] def toCollection(repr: Repr): LinearSeq[A] = repr.asInstanceOf[LinearSeq[A]] @@ -52,7 +52,7 @@ trait LinearSeqLike[+A, +Repr <: LinearSeqLike[A, Repr]] extends SeqLike[A, Repr     def hasNext: Boolean = !these.isEmpty     def next: A =        if (hasNext) { -        val result = these.head; these = these.tail; result+        val result = these.head; these = these.tail.asInstanceOf[LinearSeqLike[A,Repr] with Repr]; result       } else Iterator.empty.next       /** Have to clear `these` so the iterator is exhausted like@@ -60,7 +60,7 @@ trait LinearSeqLike[+A, +Repr <: LinearSeqLike[A, Repr]] extends SeqLike[A, Repr      */      override def toList: List[A] = {       val xs = these.toList-      these = newBuilder.result+      these = newBuilder.result.asInstanceOf[LinearSeqLike[A,Repr] with Repr]       xs      }   }

On 24.06.2011, at 15:04, Josh Suereth wrote:

object +: {

    def unapply[T, Coll <: LinearSeqLike[T, Coll]](t : Coll) : Option[(T, Coll)] =      if (t.isEmpty) None      else Some(t.head -> t.tail) // TODO - Try to remove cast. }
However this fails:
scala> List(1,2,3,4) match { case x +: xs => xs }<console>:16: error: inferred type arguments [Nothing,Coll] do not conform to method unapply's type parameter bounds [T,Coll <: scala.collection.LinearSeqLike[T,Coll]]        List(1,2,3,4) match { case x +: xs => xs }

NOW what do you do with cyclical type constraints, e.g.  trait LinearSeqLike[T, Repr <: LinearSeq[T, Repr]].   That is, How can I define a method that works against LinearSeqLike and preserves the type Repr as much as possible.

To make it work you can change the signature of unapply to
  def unapply[A,C[X] <: LinearSeqLike[X,C[X]]](xs: C[A]): Option[(A,C[A])]
I don't really know what the difference is for the type inferencer though.

Moritz

Yes, I want to avoid enforcing that Col be higher kinded.   That change makes it work but does *not* allow a type like object LowerKindedType extends LinearSeq[Int] {}   to be passed to the method without using a type lambda.

This just doesn't work well:
(+:).unapply[Int, ({ type Dummy[A] = Foo})#Dummy](LowerKindedType)


On Fri, Jun 24, 2011 at 9:57 AM, Moritz Uhlig <moritz.uhlig@jsolution.de> wrote:

On 24.06.2011, at 15:04, Josh Suereth wrote:

object +: {

    def unapply[T, Coll <: LinearSeqLike[T, Coll]](t : Coll) : Option[(T, Coll)] =      if (t.isEmpty) None      else Some(t.head -> t.tail) // TODO - Try to remove cast. }
However this fails:
scala> List(1,2,3,4) match { case x +: xs => xs }<console>:16: error: inferred type arguments [Nothing,Coll] do not conform to method unapply's type parameter bounds [T,Coll <: scala.collection.LinearSeqLike[T,Coll]]        List(1,2,3,4) match { case x +: xs => xs }

NOW what do you do with cyclical type constraints, e.g.  trait LinearSeqLike[T, Repr <: LinearSeq[T, Repr]].   That is, How can I define a method that works against LinearSeqLike and preserves the type Repr as much as possible.

To make it work you can change the signature of unapply to
  def unapply[A,C[X] <: LinearSeqLike[X,C[X]]](xs: C[A]): Option[(A,C[A])]
I don't really know what the difference is for the type inferencer though.

Moritz

On Fri, Jun 24, 2011 at 5:38 AM, Josh Suereth <joshua.suereth@gmail.com> wrote:

Ok, so we all know that Scala's type inference has issues with higher kinded types.   The workaround of course is to delay inference of types using implicit type constraints.
So, naively, I tried to implement a +: extractor for LinearSeqLike that would extract head :: tail portions of a collection.   Here's my first cut:
object +: {    def unapply[T, Coll <: LinearSeqLike[T, Coll]](t : Coll) : Option[(T, Coll)] =      if (t.isEmpty) None      else Some(t.head -> t.tail) // TODO - Try to remove cast. }

sorry, there are no higher-kinded types involved here, it's f-bounded polymorphism that is to blame  (type inference just cannot deal with the evil, evil cycles it creates)
it's okay, I won't take it personally this time -- in fact, let me prove my benevolence by fixing your problem
scala> object +: {     |     def unapply[T, Coll <: LinearSeqLike[T, Coll]](t : Coll with LinearSeqLike[T, Coll]) : Option[(T, Coll)] =      |       if (t.isEmpty) None     |       else Some(t.head -> t.tail) // TODO - Try to remove cast.     | }defined module $plus$colon
scala>  +:.unapply(List(1,2,3,4)) res3: Option[(Int, List[Int])] = Some((1,List(2, 3, 4)))
scala>  List(1,2,3,4) match { case x +: xs => xs }res4: List[Int] = List(2, 3, 4)

intersection types ftw
adriaan
ps: this is a shameless plug, but I'm on a bit of a crusade against the word "higher-kinded", as it's rarely used correctly anyway -- I've tried to explain in detail here: http://stackoverflow.com/questions/6246719/#6427289

On Fri, Jun 24, 2011 at 5:38 AM, Josh Suereth <joshua.suereth@gmail.com> wrote:

Ok, so we all know that Scala's type inference has issues with higher kinded types.   The workaround of course is to delay inference of types using implicit type constraints.
So, naively, I tried to implement a +: extractor for LinearSeqLike that would extract head :: tail portions of a collection.   Here's my first cut:
object +: {    def unapply[T, Coll <: LinearSeqLike[T, Coll]](t : Coll) : Option[(T, Coll)] =      if (t.isEmpty) None      else Some(t.head -> t.tail) // TODO - Try to remove cast. }

sorry, there are no higher-kinded types involved here, it's f-bounded polymorphism that is to blame  (type inference just cannot deal with the evil, evil cycles it creates)
it's okay, I won't take it personally this time -- in fact, let me prove my benevolence by fixing your problem
scala> object +: {     |     def unapply[T, Coll <: LinearSeqLike[T, Coll]](t : Coll with LinearSeqLike[T, Coll]) : Option[(T, Coll)] =      |       if (t.isEmpty) None     |       else Some(t.head -> t.tail) // TODO - Try to remove cast.     | }defined module $plus$colon
scala>  +:.unapply(List(1,2,3,4)) res3: Option[(Int, List[Int])] = Some((1,List(2, 3, 4)))
scala>  List(1,2,3,4) match { case x +: xs => xs }res4: List[Int] = List(2, 3, 4)

intersection types ftw
adriaan
ps: this is a shameless plug, but I'm on a bit of a crusade against the word "higher-kinded", as it's rarely used correctly anyway -- I've tried to explain in detail here: http://stackoverflow.com/questions/6246719/#6427289

to clarify: Coll is a proper type parameter, it is not a type constructor parameter, and certainly not a higher-kinded type parameter
this follows straight from its definition, which has the same shape as T (i.e., Coll does not take any type parameters, just like T). The only difference with T, is that Coll is bounded (by a proper type!)
you can also tell from the type argument that is inferred for Coll in my fixed example: `List[Int]`, which is a perfectly respectable proper type, just like Int
another way to see Coll is not higher-kinded is to observe that there are values of this type, which is never the case for a higher-kinded type -- only proper types classify values
hope this clarifies matters a bit :-)
cheersadriaan

On Fri, Jun 24, 2011 at 5:24 PM, Adriaan Moors <adriaan.moors@epfl.ch> wrote:

On Fri, Jun 24, 2011 at 5:38 AM, Josh Suereth <joshua.suereth@gmail.com> wrote:

Ok, so we all know that Scala's type inference has issues with higher kinded types.   The workaround of course is to delay inference of types using implicit type constraints.
So, naively, I tried to implement a +: extractor for LinearSeqLike that would extract head :: tail portions of a collection.   Here's my first cut:
object +: {    def unapply[T, Coll <: LinearSeqLike[T, Coll]](t : Coll) : Option[(T, Coll)] =      if (t.isEmpty) None      else Some(t.head -> t.tail) // TODO - Try to remove cast. }

sorry, there are no higher-kinded types involved here, it's f-bounded polymorphism that is to blame  (type inference just cannot deal with the evil, evil cycles it creates)
it's okay, I won't take it personally this time -- in fact, let me prove my benevolence by fixing your problem
scala> object +: {     |     def unapply[T, Coll <: LinearSeqLike[T, Coll]](t : Coll with LinearSeqLike[T, Coll]) : Option[(T, Coll)] =      |       if (t.isEmpty) None     |       else Some(t.head -> t.tail) // TODO - Try to remove cast.     | }defined module $plus$colon
scala>  +:.unapply(List(1,2,3,4)) res3: Option[(Int, List[Int])] = Some((1,List(2, 3, 4)))
scala>  List(1,2,3,4) match { case x +: xs => xs }res4: List[Int] = List(2, 3, 4)

intersection types ftw
adriaan
ps: this is a shameless plug, but I'm on a bit of a crusade against the word "higher-kinded", as it's rarely used correctly anyway -- I've tried to explain in detail here: http://stackoverflow.com/questions/6246719/#6427289

to clarify: Coll is a proper type parameter, it is not a type constructor parameter, and certainly not a higher-kinded type parameter
this follows straight from its definition, which has the same shape as T (i.e., Coll does not take any type parameters, just like T). The only difference with T, is that Coll is bounded (by a proper type!)
you can also tell from the type argument that is inferred for Coll in my fixed example: `List[Int]`, which is a perfectly respectable proper type, just like Int
another way to see Coll is not higher-kinded is to observe that there are values of this type, which is never the case for a higher-kinded type -- only proper types classify values
hope this clarifies matters a bit :-)
cheersadriaan

On Fri, Jun 24, 2011 at 5:24 PM, Adriaan Moors <adriaan.moors@epfl.ch> wrote:

On Fri, Jun 24, 2011 at 5:38 AM, Josh Suereth <joshua.suereth@gmail.com> wrote:

Ok, so we all know that Scala's type inference has issues with higher kinded types.   The workaround of course is to delay inference of types using implicit type constraints.
So, naively, I tried to implement a +: extractor for LinearSeqLike that would extract head :: tail portions of a collection.   Here's my first cut:
object +: {    def unapply[T, Coll <: LinearSeqLike[T, Coll]](t : Coll) : Option[(T, Coll)] =      if (t.isEmpty) None      else Some(t.head -> t.tail) // TODO - Try to remove cast. }

sorry, there are no higher-kinded types involved here, it's f-bounded polymorphism that is to blame  (type inference just cannot deal with the evil, evil cycles it creates)
it's okay, I won't take it personally this time -- in fact, let me prove my benevolence by fixing your problem
scala> object +: {     |     def unapply[T, Coll <: LinearSeqLike[T, Coll]](t : Coll with LinearSeqLike[T, Coll]) : Option[(T, Coll)] =      |       if (t.isEmpty) None     |       else Some(t.head -> t.tail) // TODO - Try to remove cast.     | }defined module $plus$colon
scala>  +:.unapply(List(1,2,3,4)) res3: Option[(Int, List[Int])] = Some((1,List(2, 3, 4)))
scala>  List(1,2,3,4) match { case x +: xs => xs }res4: List[Int] = List(2, 3, 4)

intersection types ftw
adriaan
ps: this is a shameless plug, but I'm on a bit of a crusade against the word "higher-kinded", as it's rarely used correctly anyway -- I've tried to explain in detail here: http://stackoverflow.com/questions/6246719/#6427289

Thanks for solving the problem!   I'll have to remember to use with more often.  Plus, any time in the future I use the word higher-kinded, assume I'm talking about people who are nice and tall.
- Josh


On Fri, Jun 24, 2011 at 11:31 AM, Adriaan Moors <adriaan.moors@epfl.ch> wrote:

to clarify: Coll is a proper type parameter, it is not a type constructor parameter, and certainly not a higher-kinded type parameter
this follows straight from its definition, which has the same shape as T (i.e., Coll does not take any type parameters, just like T). The only difference with T, is that Coll is bounded (by a proper type!)
you can also tell from the type argument that is inferred for Coll in my fixed example: `List[Int]`, which is a perfectly respectable proper type, just like Int
another way to see Coll is not higher-kinded is to observe that there are values of this type, which is never the case for a higher-kinded type -- only proper types classify values
hope this clarifies matters a bit :-)
cheersadriaan

On Fri, Jun 24, 2011 at 5:24 PM, Adriaan Moors <adriaan.moors@epfl.ch> wrote:

On Fri, Jun 24, 2011 at 5:38 AM, Josh Suereth <joshua.suereth@gmail.com> wrote:

Ok, so we all know that Scala's type inference has issues with higher kinded types.   The workaround of course is to delay inference of types using implicit type constraints.
So, naively, I tried to implement a +: extractor for LinearSeqLike that would extract head :: tail portions of a collection.   Here's my first cut:
object +: {    def unapply[T, Coll <: LinearSeqLike[T, Coll]](t : Coll) : Option[(T, Coll)] =      if (t.isEmpty) None      else Some(t.head -> t.tail) // TODO - Try to remove cast. }

sorry, there are no higher-kinded types involved here, it's f-bounded polymorphism that is to blame  (type inference just cannot deal with the evil, evil cycles it creates)
it's okay, I won't take it personally this time -- in fact, let me prove my benevolence by fixing your problem
scala> object +: {     |     def unapply[T, Coll <: LinearSeqLike[T, Coll]](t : Coll with LinearSeqLike[T, Coll]) : Option[(T, Coll)] =      |       if (t.isEmpty) None     |       else Some(t.head -> t.tail) // TODO - Try to remove cast.     | }defined module $plus$colon
scala>  +:.unapply(List(1,2,3,4)) res3: Option[(Int, List[Int])] = Some((1,List(2, 3, 4)))
scala>  List(1,2,3,4) match { case x +: xs => xs }res4: List[Int] = List(2, 3, 4)

intersection types ftw
adriaan
ps: this is a shameless plug, but I'm on a bit of a crusade against the word "higher-kinded", as it's rarely used correctly anyway -- I've tried to explain in detail here: http://stackoverflow.com/questions/6246719/#6427289

Thanks for solving the problem!   I'll have to remember to use with more often.  Plus, any time in the future I use the word higher-kinded, assume I'm talking about people who are nice and tall.
- Josh


On Fri, Jun 24, 2011 at 11:31 AM, Adriaan Moors <adriaan.moors@epfl.ch> wrote:

to clarify: Coll is a proper type parameter, it is not a type constructor parameter, and certainly not a higher-kinded type parameter
this follows straight from its definition, which has the same shape as T (i.e., Coll does not take any type parameters, just like T). The only difference with T, is that Coll is bounded (by a proper type!)
you can also tell from the type argument that is inferred for Coll in my fixed example: `List[Int]`, which is a perfectly respectable proper type, just like Int
another way to see Coll is not higher-kinded is to observe that there are values of this type, which is never the case for a higher-kinded type -- only proper types classify values
hope this clarifies matters a bit :-)
cheersadriaan

On Fri, Jun 24, 2011 at 5:24 PM, Adriaan Moors <adriaan.moors@epfl.ch> wrote:

On Fri, Jun 24, 2011 at 5:38 AM, Josh Suereth <joshua.suereth@gmail.com> wrote:

Ok, so we all know that Scala's type inference has issues with higher kinded types.   The workaround of course is to delay inference of types using implicit type constraints.
So, naively, I tried to implement a +: extractor for LinearSeqLike that would extract head :: tail portions of a collection.   Here's my first cut:
object +: {    def unapply[T, Coll <: LinearSeqLike[T, Coll]](t : Coll) : Option[(T, Coll)] =      if (t.isEmpty) None      else Some(t.head -> t.tail) // TODO - Try to remove cast. }

sorry, there are no higher-kinded types involved here, it's f-bounded polymorphism that is to blame  (type inference just cannot deal with the evil, evil cycles it creates)
it's okay, I won't take it personally this time -- in fact, let me prove my benevolence by fixing your problem
scala> object +: {     |     def unapply[T, Coll <: LinearSeqLike[T, Coll]](t : Coll with LinearSeqLike[T, Coll]) : Option[(T, Coll)] =      |       if (t.isEmpty) None     |       else Some(t.head -> t.tail) // TODO - Try to remove cast.     | }defined module $plus$colon
scala>  +:.unapply(List(1,2,3,4)) res3: Option[(Int, List[Int])] = Some((1,List(2, 3, 4)))
scala>  List(1,2,3,4) match { case x +: xs => xs }res4: List[Int] = List(2, 3, 4)

intersection types ftw
adriaan
ps: this is a shameless plug, but I'm on a bit of a crusade against the word "higher-kinded", as it's rarely used correctly anyway -- I've tried to explain in detail here: http://stackoverflow.com/questions/6246719/#6427289

I ran into a similar problem before trying to mix LinearSeqOptimized into a class. Thanks very much for posting the solution! However, now that I see it I'm afraid I still don't understand. Why can't the compiler infer that the argument to unapply (List[T]) derives from LinearSeq[T, Coll] and therefore conforms to the type parameter bounds? In other words, why is it necessary to add 'with LinearSeqLike[T, Coll]'? To my untrained eyes, this appears completely redundant. How would I know to add this?

-jeff