Re: map2/map3

It might well be that you are right. I'll have to investigate wqhen I
have a bit more time.

Using the following definitions:

class IterableOps
  [CC[+B] <: Iterable[B] with IterableTemplate[B, CC[B]], A1, A2]
  (tuple: (CC[A1], Iterable[A2]))

implicit def tupleOfIterableWrapper
  [CC[+B] <: Iterable[B] with IterableTemplate[B, CC[B]], A1, A2]
  (tuple: (CC[A1], Iterable[A2]))
    = new IterableOps[CC, A1, A2](tuple)

I get the following:

scala> val t = (List(1, 2, 3), List(6, 5, 4))
t: (List[Int], List[Int]) = (List(1, 2, 3), List(6, 5, 4))

scala> tupleOfIterableWrapper[List, Int, Int](t)
res3: IterableOps[List, Int, Int] = IterableOps@2365fe

scala> tupleOfIterableWrapper(t)
<console>:17: error: inferred kinds of the type arguments (List[Int],A1,Int) do not conform to the expected kinds of the type parameters (type CC,type A1,type A2).
List[Int]'s type parameters do not match type CC's expected parameters: class List has one type parameter, but type CC has one
       tupleOfIterableWrapper(t)
       ^
<console>:17: error: type mismatch;
 found   : (List[Int], List[Int])
 required: (List[A1], Iterable[Int])
       tupleOfIterableWrapper(t)
       ^

The error message of "class List has one type parameter, but type CC has one" certainly seems suspicious there...

- Colin

On Tue, May 19, 2009 at 11:10:44AM -0500, Colin Bullock wrote:
> :17: error: type mismatch;
> found : (List[Int], List[Int])
> required: (List[A1], Iterable[Int])
> tupleOfIterableWrapper(t)
> ^

Indeed, this is the error I faced off against about fifty times
yesterday (one can choose between a required "List[A1]" and a required
"List[Nothing]" by fiddling with variance.)

> The error message of "class List has *one* type parameter, but type CC
> has * one*" certainly seems suspicious there...

I figured it was the new math.

On Tue, May 19, 2009 at 6:22 PM, Paul Phillips wrote:
> On Tue, May 19, 2009 at 11:10:44AM -0500, Colin Bullock wrote:
>> :17: error: type mismatch;
>>  found   : (List[Int], List[Int])
>>  required: (List[A1], Iterable[Int])
>>        tupleOfIterableWrapper(t)
>>        ^
>
> Indeed, this is the error I faced off against about fifty times
> yesterday (one can choose between a required "List[A1]" and a required
> "List[Nothing]" by fiddling with variance.)
>
>> The error message of "class List has *one* type parameter, but type CC
>> has * one*" certainly seems suspicious there...
>
> I figured it was the new math.
>
I think that's one of the known problems with inference for hk types.
But I am thinkingof some possible improvements there thta I'd try out
first, before coming back to the Tuple2.map issue.

Cheers

On Tue, May 19, 2009 at 07:50:56PM +0200, martin odersky wrote:
> I think that's one of the known problems with inference for hk types.
> But I am thinkingof some possible improvements there thta I'd try out
> first, before coming back to the Tuple2.map issue.

I notice a little tardily that the existing implicits along these lines
seem to have all the same issues going.

scala> import collection.Traversable._
import collection.Traversable._

scala> List((1,2),(3,4),(5,6)) unzip
:8: error: value unzip is not a member of List[(Int, Int)]
List((1,2),(3,4),(5,6)) unzip
^

scala> pairTraversableWrapper(List((1,2),(3,4),(5,6)))
:8: error: inferred type arguments [List[(Int, Int)],A1,A2] do not conform to method pairTraversableWrapper's type parameter bounds [This <: Traversable[(A1, A2)],A1,A2]
pairTraversableWrapper(List((1,2),(3,4),(5,6)))
^

scala> pairTraversableWrapper[List[(Int,Int)],Int,Int](List((1,2),(3,4),(5,6)))
res3: collection.Traversable.PairTraversableOps[List[(Int, Int)],Int,Int] = scala.collection.Traversable$PairTraversableOps@c75ad4

scala> import collection.immutable.List._
import collection.immutable.List._

scala> res3 unzip
:12: error: no implicit argument matching parameter type scala.collection.generic.BuilderFactory[Int,That2,List[(Int, Int)]] was found.
res3 unzip
^

scala> res3.unzip[List[Int], List[Int]]
res5: (List[Int], List[Int]) = (List(1, 3, 5),List(2, 4, 6))

I think that's one of the known problems with inference for hk types.

I'm currently working on implementing type constructor inference -- still a little jetlagged, but I hope to have a proof of concept very soon.
cheersadriaan  

Hi,
My first prototype for tcpoly inference is available at http://github.com/adriaanm/scala/tree/tcpolyinfer
More test cases (or bug reports/fixes ;-)) greatly appreciated!
Behold:
Welcome to Scala version 2.8.0.r0-b20090602175319 (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_07). Type in expressions to have them evaluated. Type :help for more information.
scala> def test[CC[+X] <: Iterable[X], A](xs: CC[A]): CC[A] = xs test: [CC[+X] <: Iterable[X],A](xs: CC[A])CC[A]
scala> val xs = test(List(1,2)) // List type constructor omitted  xs: List[Int] = List(1, 2)  // TADA
scala> val xs2: List[Int] = test(List(1,2)) xs2: List[Int] = List(1, 2)

scala> import scala.collection.generic._  import scala.collection.generic._
scala> 
scala> class IterableOps[CC[+B] <: Iterable[B] with IterableTemplate[B, CC[B]], A1, A2](tuple: (CC[A1], Iterable[A2])) defined class IterableOps
scala>   def tupleOfIterableWrapper[CC[+B] <: Iterable[B] with IterableTemplate[B, CC[B]], A1, A2](tuple: (CC[A1], Iterable[A2])) = new IterableOps[CC, A1, A2](tuple) tupleOfIterableWrapper: [CC[+B] <: Iterable[B] with scala.collection.generic.IterableTemplate[B,CC[B]],A1,A2](tuple: (CC[A1], Iterable[A2]))IterableOps[CC,A1,A2]
scala> 
scala>   tupleOfIterableWrapper((List(1, 2, 3), List(6, 5, 4))) res0: IterableOps[List,Int,Int] = IterableOps@439b2c10
cheers,adriaan
On Wed, May 27, 2009 at 2:32 PM, Adriaan Moors <adriaan.moors@cs.kuleuven.be> wrote:

I think that's one of the known problems with inference for hk types.

I'm currently working on implementing type constructor inference -- still a little jetlagged, but I hope to have a proof of concept very soon.
cheersadriaan  

On Wed, Jun 03, 2009 at 10:25:15AM +0200, Adriaan Moors wrote:
> My first prototype for tcpoly inference is available at
> http://github.com/adriaanm/scala/tree/tcpolyinfer

Awesome! I look forward to put it through the paces. Can you comment on
your overall feeling about it, i.e. do you think it's close to something
which could enter the mainline, or does "prototype" imply long distance?

On Wed, Jun 3, 2009 at 1:59 PM, Paul Phillips <paulp@improving.org> wrote:

On Wed, Jun 03, 2009 at 10:25:15AM +0200, Adriaan Moors wrote:
> My first prototype for tcpoly inference is available at
> http://github.com/adriaanm/scala/tree/tcpolyinfer

Awesome! I look forward to put it through the paces.  Can you comment on
your overall feeling about it, i.e. do you think it's close to something
which could enter the mainline, or does "prototype" imply long distance?

I think it could enter trunk soon. Currently working on cleaning up the code, adding docs, and trying more examples. The patch in itself is fairly small, so I'm hopeful :-)  
adriaan 

This is just great Adriaan!!!
Of all people I can think, Tony will probably be the happiest with this development.
CKKL

On Wed, Jun 3, 2009 at 20:00, Adriaan Moors <adriaan.moors@cs.kuleuven.be> wrote:

On Wed, Jun 3, 2009 at 1:59 PM, Paul Phillips <paulp@improving.org> wrote:

On Wed, Jun 03, 2009 at 10:25:15AM +0200, Adriaan Moors wrote:
> My first prototype for tcpoly inference is available at
> http://github.com/adriaanm/scala/tree/tcpolyinfer

Awesome! I look forward to put it through the paces.  Can you comment on
your overall feeling about it, i.e. do you think it's close to something
which could enter the mainline, or does "prototype" imply long distance?

I think it could enter trunk soon. Currently working on cleaning up the code, adding docs, and trying more examples. The patch in itself is fairly small, so I'm hopeful :-)  
adriaan 

--
 __~O
-\ <,       Christos KK Loverdos
(*)/ (*)      http://ckkloverdos.com

On Wednesday June 3 2009, Christos KK Loverdos wrote:
> On Wed, Jun 3, 2009 at 20:00, Adriaan Moors wrote:
> > On Wed, Jun 3, 2009 at 1:59 PM, Paul Phillips wrote:
> >> On Wed, Jun 03, 2009 at 10:25:15AM +0200, Adriaan Moors wrote:
> >> > My first prototype for tcpoly inference is available at
> >> > http://github.com/adriaanm/scala/tree/tcpolyinfer
> >>
> >> Awesome! I look forward to put it through the paces. Can you
> >> comment on your overall feeling about it, i.e. do you think it's
> >> close to something which could enter the mainline, or does
> >> "prototype" imply long distance?
> >
> > I think it could enter trunk soon. Currently working on cleaning up
> > the code, adding docs, and trying more examples.
> > The patch in itself is fairly small, so I'm hopeful :-)
> >
> > adriaan
>
> This is just great Adriaan!!!
> Of all people I can think, Tony will probably be the happiest with this development.
>
> CKKL

[01:29:26] seems like Adriaan Moors is ahead of the curve regarding VCS when compared to the EPFL guys
[01:30:18] regarding VCS? what does that mean?
[01:30:56] dibblego: he posted the prototype of type constructor inference.. and he used github for it
[01:31:06] ah
[01:31:14] wait, type constructor inference?
[01:31:29] dibblego: yes, scala-internals
[01:31:43] map2/map3 thread
[01:31:51] I didn't think that was ever on the agenda
[01:31:54] dibblego: I thought you might be interested ;)
[01:32:00] cheers :)

(Times are PDT == GMT - 0700)

RRS

First, some bad news: 

scala> pairTraversableWrapper(List((1,2),(3,4),(5,6)))
<console>:8: error: inferred type arguments [List[(Int, Int)],A1,A2] do not conform to method pairTraversableWrapper's type parameter bounds [This <: Traversable[(A1, A2)],A1,A2]
      pairTraversableWrapper(List((1,2),(3,4),(5,6)))
      ^

I don't think we (I) can (will/want to/...) solve this kind of type inference problem, as it requires the type checker to unify something like ?CC[(?A, ?B)] with the type List[(Int, Int)]. 
Somehow, the algorithm would need to "break apart" that type (essentially function application at the type level) to recover the arguments to which this function was applied. It's kind of like guessing 1 and 2 (or 0 and 3, or 42 and -39, or...) from the constraint 3 == A + B, except it's much worse (given subtyping, abstract types, ...). At least, that's how I understand type inference at the moment...
The good news:
Welcome to Scala version 2.8.0.r0-b20090605174254 (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_07). Type in expressions to have them evaluated.Type :help for more information.
scala> List((1,2),(3,4),(5,6)) unzip res0: (List[Int], List[Int]) = (List(1, 3, 5),List(2, 4, 6))
Here's how I propose to implement unzip:
trait TraversableClass[+A, +CC[X] <: Traversable[X]] {// ...   def genericBuilder[B]: Builder[B, CC[B]] = companion.newBuilder[B]
     // @M TODO: redundant...  def foreach[U](f: A => U): Unit        implicit def subtype_witness[T <: U, U](x: T): U = x  // @M TODO: move to Predef?   def unzip[X, Y](implicit c: A => (X, Y)): (CC[X], CC[Y]) = {     val b1 = genericBuilder[X]    val b2 = genericBuilder[Y]     foreach { case (x1: X, x2: Y) =>      b1 += x1       b2 += x2    }     (b1.result, b2.result)      } }
I'm sure the design can be improved, but I highlighted the essence. (See the flatten example on pp. 52--53, Section 3.6.4, of my thesis for details.)
cheers,adriaan

Good news everybody! I spoke to soon in my message on Friday. Colin's approach works in my tcpolyinfer prototype:
Welcome to Scala version 2.8.0.r0-b20090605174254 (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_07). Type in expressions to have them evaluated.Type :help for more information.
scala> import scala.collection.generic._ import scala.collection.generic._
scala> class IterableOps[CC[+B] <: Iterable[B] with IterableTemplate[B, CC[B]], A1, A2](tuple: (CC[A1], Iterable[A2]))
defined class IterableOps
scala> implicit def tupleOfIterableWrapper[CC[+B] <: Iterable[B] with IterableTemplate[B, CC[B]], A1, A2](tuple: (CC[A1], Iterable[A2]))       |     = new IterableOps[CC, A1, A2](tuple)tupleOfIterableWrapper: [CC[+B] <: Iterable[B] with scala.collection.generic.IterableTemplate[B,CC[B]],A1,A2](tuple: (CC[A1], Iterable[A2]))IterableOps[CC,A1,A2]
scala> val t = (List(1, 2, 3), List(6, 5, 4)) t: (List[Int], List[Int]) = (List(1, 2, 3),List(6, 5, 4))

scala>  tupleOfIterableWrapper(t) res0: IterableOps[List,Int,Int] = IterableOps@87409cf

That said, I still kind of prefer my approach, which encodes generalised constraints using a universal implicit that serves as a witness for an arbitrary subtyping constraint. I think the optimiser should be able to eliminate this implicit witness (since it's just the constrained polymorphic identity function), so that we get generalised constraints for free in Scala (without the pretty syntax, though)
cheers,adriaan
On Tue, May 19, 2009 at 6:10 PM, Colin Bullock <cmbullock@gmail.com> wrote:

Using the following definitions:

class IterableOps
  [CC[+B] <: Iterable[B] with IterableTemplate[B, CC[B]], A1, A2]
  (tuple: (CC[A1], Iterable[A2]))

implicit def tupleOfIterableWrapper
  [CC[+B] <: Iterable[B] with IterableTemplate[B, CC[B]], A1, A2]
  (tuple: (CC[A1], Iterable[A2]))
    = new IterableOps[CC, A1, A2](tuple)

I get the following:

scala> val t = (List(1, 2, 3), List(6, 5, 4))
t: (List[Int], List[Int]) = (List(1, 2, 3), List(6, 5, 4))

scala> tupleOfIterableWrapper[List, Int, Int](t)
res3: IterableOps[List, Int, Int] = IterableOps@2365fe

scala> tupleOfIterableWrapper(t)
<console>:17: error: inferred kinds of the type arguments (List[Int],A1,Int) do not conform to the expected kinds of the type parameters (type CC,type A1,type A2).
List[Int]'s type parameters do not match type CC's expected parameters: class List has one type parameter, but type CC has one
       tupleOfIterableWrapper(t)
       ^
<console>:17: error: type mismatch;
 found   : (List[Int], List[Int])
 required: (List[A1], Iterable[Int])
       tupleOfIterableWrapper(t)
       ^

The error message of "class List has one type parameter, but type CC has one" certainly seems suspicious there...

- Colin

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm for more information.

On Fri, Jun 5, 2009 at 6:02 PM, Adriaan
Moors wrote:
> First, some bad news:
>
>>
>> scala> pairTraversableWrapper(List((1,2),(3,4),(5,6)))
>> :8: error: inferred type arguments [List[(Int, Int)],A1,A2] do
>> not conform to method pairTraversableWrapper's type parameter bounds [This
>> <: Traversable[(A1, A2)],A1,A2]
>>       pairTraversableWrapper(List((1,2),(3,4),(5,6)))
>>       ^
>
> I don't think we (I) can (will/want to/...) solve this kind of type
> inference problem, as it requires the type checker to unify something like
> ?CC[(?A, ?B)] with the type List[(Int, Int)].
> Somehow, the algorithm would need to "break apart" that type (essentially
> function application at the type level) to recover the arguments to which
> this function was applied. It's kind of like guessing 1 and 2 (or 0 and 3,
> or 42 and -39, or...) from the constraint 3 == A + B, except it's much worse
> (given subtyping, abstract types, ...).
> At least, that's how I understand type inference at the moment...
> The good news:
> Welcome to Scala version 2.8.0.r0-b20090605174254 (Java HotSpot(TM) 64-Bit
> Server VM, Java 1.6.0_07).
> Type in expressions to have them evaluated.
> Type :help for more information.
> scala> List((1,2),(3,4),(5,6)) unzip
> res0: (List[Int], List[Int]) = (List(1, 3, 5),List(2, 4, 6))
> Here's how I propose to implement unzip:
> trait TraversableClass[+A, +CC[X] <: Traversable[X]] {
> // ...
>   def genericBuilder[B]: Builder[B, CC[B]] = companion.newBuilder[B]
>
>   // @M TODO: redundant...
>   def foreach[U](f: A => U): Unit
>
>   implicit def subtype_witness[T <: U, U](x: T): U = x  // @M TODO: move to
> Predef?
>   def unzip[X, Y](implicit c: A => (X, Y)): (CC[X], CC[Y]) = {
>     val b1 = genericBuilder[X]
>     val b2 = genericBuilder[Y]
>     foreach { case (x1: X, x2: Y) =>
>       b1 += x1
>       b2 += x2
>     }
>     (b1.result, b2.result)
>   }
> }
> I'm sure the design can be improved, but I highlighted the essence. (See the
> flatten example on pp. 52--53, Section 3.6.4, of my thesis for details.)
> cheers,

Yes, that looks like the way to go. One small remark: You don't need
subtypeWitness; the identity implicit is already defined in Predef.

I verified that unzip and flatten compile that way. The next challenge will be
Tuple2.map and friends.

Cheers