rethinking map2 and friends

Hi,
I haven't fully thought it through yet, but it seems like this only solves the namespace problem, not the code duplication one.Aside from namespace management, I don't immediately see the use of having an object to represent `(xs, ..., zs).zipped`.
Re: code duplication, I guess arity-polymorphic versions of map and friends are out of reach, so maybe that's not a criterion to judge alternatives by.
I'll give it some more thought over the next couple of days
cheers,adriaan

On Sat, Nov 7, 2009 at 11:49 AM, martin odersky <martin.odersky@epfl.ch> wrote:

I think Paul has a point: Adding map2, map3, map4, foreach2. foreach3,
foreach4, exists2, exists3, exists4, forall3, forall4, etc, etc, etc
to TraversableLike will be a pain in the neck. A huge number of new
methods and we will still have to impose fairly arbitrary arity
restrictions -- we certainly can't go up to 22!

It strikes me there might be a better solution. How about ONE new
method for each Tuple class up to reasonable arity?

 (xs, ys). zipped    // zipped view of traversable xs and iterable ys.

The zipped method could be followed by map, foreach, forall, etc. For instance:

 (xs, ys).zipped.map(_ * _).sum   // scalar product

The result of zipped would be an instance of class Zipped, which is in
essence a short-lived view
of a collection of tuples -- short-lived in the sense that all its
operations yield regular collections, not views.
[A good question is what to do if the left collection is a view in
itself. Can we arrange things so that
in that case zipped returns also a full (i.e. sticky) view? But the
answer to that question can probably wait a while.]
Here's an outline of an implementation of class Zipped for pairs:

class Zipped[LeftElem, RightElem, LeftRepr <:
TraversableLike[LeftElem, LeftRepr]]
                      (left: LeftRepr, right: Iterable[RightElem]) {

  def map[B, To](f: (LeftElem, RightElem) => B)(implicit cbf:
CanBuildFrom[LeftRepr, B, To]: To =
       val b = cbf(left)
       val yi = right.iterator
       for (x <- left)
          if (yi.hasNext) b += f(x, yi.next)
      b.result
  }

  def foreach ...
  ...
}

Zipped could be an inner class of Tuple2, Tuple3, Tuple4 (not sure we
need to go further than that).

Ideally, Zipped would itself be a TraversableLike of Tuples. Right
now, this would imply that higher-order operations like map take unary
functions over n-tuples rather than n-ary functions over the elements.
That makes it more awkward to express operations like scalar product
and carries a performance penalty. I still have on our list of things
to do a unification of n-ary functions and tupled functions. Once that
is achieved the problem would go away. So I propose to let Zipped not
inherit from TraversableLike right now, in order to have the nice
usage patterns with n-ary functions. We can always add that later,
once we have done our homework on tupled functons.

What do you think. Adriaan, you were going to do the modifications to
tupled operations. Are you happy to try out to this scheme instead?

Cheers

On Sun, Nov 8, 2009 at 7:36 PM, Adriaan Moors
wrote:
> Hi,
> I haven't fully thought it through yet, but it seems like this only solves
> the namespace problem, not the code duplication one.

Right. I don't see a way to solve the code duplication problem. But at
least we won't have 100's of additonal methods in TraversableLike;
they'd be spread out a little bit better over the TupleN.Zipped
classes.

> Aside from namespace management, I don't immediately see the use of having
> an object to represent `(xs, ..., zs).zipped`.

It will be a useful object when it's a collection.

Cheers

On Sun, Nov 08, 2009 at 07:36:31PM +0100, Adriaan Moors wrote:
> Re: code duplication, I guess arity-polymorphic versions of map and
> friends are out of reach, so maybe that's not a criterion to judge
> alternatives by.

Small diversion: the issue of abstracting over arity has been jabbing
pokier and pokier sticks into my side, and I have long meant to ask:
what is it that makes this especially difficult? Is there some theory I
need to understand? My problem is that my uneducated mind still frames
higher order types as a sort of fancy template expansion, inaccurate as
I'm sure that is; and from that perspective one thinks "I know how to
write a method which can generate the source for arity-2, arity-3,
arity-N on demand, so why can't I explain that to the compiler?"

I have been reading your thesis (slowly, as I have to take side trips to
learn jargon and the occasional branch of mathematics) and arity is the
first thing that sprang to mind when I read: "However, it seems that we
keep discovering the need for abstracting over things that we formerly
did not consider."

Hi,
I'm running into type inference limitations/bugs with my implementation of Zipped (attached).
Here's a sample interaction:
Welcome to Scala version 2.8.0.r0-b20091109145811 (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_15).
scala> MyTuple2(List(1,2,3), List("a", "b", "c")).zipped map {(a, b) => a+b} <console>:5: error: could not find implicit value for parameter w2: <:<[List[java.lang.String],Iterable[El2]]        MyTuple2(List(1,2,3), List("a", "b", "c")).zipped map {(a, b) => a+b}                                                   ^
scala> MyTuple2(List(1,2,3), List("a", "b", "c")).zipped[List[Int], Int, String] map {(a, b) => a+b} res1: List[java.lang.String] = List(1a, 2b, 3c)
ideas anyone?
adriaan

On Mon, Nov 09, 2009 at 03:43:36PM +0100, Adriaan Moors wrote:
> :5: error: could not find implicit value for parameter w2:
> <:<[List[java.lang.String],Iterable[El2]]

Iterable[El2] ? Historically the problem in these situations is that it
substitutes Nothing, but here it looks like it's substituting nothing,
which must be a bu... wait, you're asking us? Nothing could possibly
frighten me more!

(Yes, Nothing is a bottomless well of comedy gold.)

On Mon, Nov 9, 2009 at 4:11 PM, Paul Phillips <paulp@improving.org> wrote:

On Mon, Nov 09, 2009 at 03:43:36PM +0100, Adriaan Moors wrote:
> <console>:5: error: could not find implicit value for parameter w2:
> <:<[List[java.lang.String],Iterable[El2]]

Iterable[El2] ? Historically the problem in these situations is that it
substitutes Nothing, but here it looks like it's substituting nothing,
which must be a bu... wait, you're asking us? Nothing could possibly
frighten me more!

well, I have a hunch of what might be going awry (hope that brings you some comfort in these trying times!)I was in a bit of a rush, so I was hoping someone else might have a trick up their sleeve or spot my mistake, ...
adriaan

in line with my earlier thinking aloud -- my (unvoiced) suspicion that there's some kind of incremental substitution needed, seems to be confirmed by a rewrite that compiles (below)
should we solve implicits/infer types in clusters? i.e., w1 determines Repr1 and El2, and w2 determines El2 -- if they can be inferred independently, we should be able to infer them when they appear together, right?
adriaan

import scala.collection.TraversableLikeimport scala.collection.Traversableimport scala.collection.generic.CanBuildFrom
object Test {   val p = MyTuple2(List(1,2,3), List("a", "b", "c"))  p.zipped1.zipped2 //map {(a, b) => a+b}}
case class MyTuple2[+T1, +T2](_1:T1, _2:T2) { def zipped1[Repr1, El1](implicit w1: T1 <:< TraversableLike[El1, Repr1]) = new Zipped1[Repr1, El1](_1)
  class Zipped1[+Repr1, +El1](coll1: TraversableLike[El1, Repr1]) {    def zipped2[El2](implicit w2: T2 <:< Iterable[El2]): Zipped[Repr1, El1, El2] = new Zipped[Repr1, El1, El2](coll1, _2) }   //   class Zipped[+Repr1, +El1, +El2](coll1: TraversableLike[El1, Repr1], coll2: Iterable[El2]) {    
On Mon, Nov 9, 2009 at 4:42 PM, Adriaan Moors <adriaan.moors@cs.kuleuven.be> wrote:

On Mon, Nov 9, 2009 at 4:11 PM, Paul Phillips <paulp@improving.org> wrote:

On Mon, Nov 09, 2009 at 03:43:36PM +0100, Adriaan Moors wrote:
> <console>:5: error: could not find implicit value for parameter w2:
> <:<[List[java.lang.String],Iterable[El2]]

Iterable[El2] ? Historically the problem in these situations is that it
substitutes Nothing, but here it looks like it's substituting nothing,
which must be a bu... wait, you're asking us? Nothing could possibly
frighten me more!

well, I have a hunch of what might be going awry (hope that brings you some comfort in these trying times!)I was in a bit of a rush, so I was hoping someone else might have a trick up their sleeve or spot my mistake, ...
adriaan

ok, had to fix a couple of bugs in implicit resolution/type inference first, but now we have a zippable Tuple2  -- other arities to come, tomorrow, after I had dinner etc
Martin, please review http://lampsvn.epfl.ch/trac/scala/changeset/19471/scala/trunk

Showcase:
Welcome to Scala version 2.8.0.r0-b20091109210229 (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_15).Type in expressions to have them evaluated. Type :help for more information.
scala> (List(1,2,3), List("a", "b", "c")).zipped filter {(i, s) => i < 2 || s == "c"}res0: (List[Int], List[java.lang.String]) = (List(1, 3),List(a, c))

cheersadriaan
On Mon, Nov 9, 2009 at 5:48 PM, Adriaan Moors <adriaan.moors@cs.kuleuven.be> wrote:

in line with my earlier thinking aloud -- my (unvoiced) suspicion that there's some kind of incremental substitution needed, seems to be confirmed by a rewrite that compiles (below)
should we solve implicits/infer types in clusters? i.e., w1 determines Repr1 and El2, and w2 determines El2 -- if they can be inferred independently, we should be able to infer them when they appear together, right?
adriaan

import scala.collection.TraversableLikeimport scala.collection.Traversableimport scala.collection.generic.CanBuildFrom
object Test {   val p = MyTuple2(List(1,2,3), List("a", "b", "c"))  p.zipped1.zipped2 //map {(a, b) => a+b}}
case class MyTuple2[+T1, +T2](_1:T1, _2:T2) { def zipped1[Repr1, El1](implicit w1: T1 <:< TraversableLike[El1, Repr1]) = new Zipped1[Repr1, El1](_1)
  class Zipped1[+Repr1, +El1](coll1: TraversableLike[El1, Repr1]) {    def zipped2[El2](implicit w2: T2 <:< Iterable[El2]): Zipped[Repr1, El1, El2] = new Zipped[Repr1, El1, El2](coll1, _2) }   //   class Zipped[+Repr1, +El1, +El2](coll1: TraversableLike[El1, Repr1], coll2: Iterable[El2]) {    
On Mon, Nov 9, 2009 at 4:42 PM, Adriaan Moors <adriaan.moors@cs.kuleuven.be> wrote:

On Mon, Nov 9, 2009 at 4:11 PM, Paul Phillips <paulp@improving.org> wrote:

On Mon, Nov 09, 2009 at 03:43:36PM +0100, Adriaan Moors wrote:
> <console>:5: error: could not find implicit value for parameter w2:
> <:<[List[java.lang.String],Iterable[El2]]

Iterable[El2] ? Historically the problem in these situations is that it
substitutes Nothing, but here it looks like it's substituting nothing,
which must be a bu... wait, you're asking us? Nothing could possibly
frighten me more!

well, I have a hunch of what might be going awry (hope that brings you some comfort in these trying times!)I was in a bit of a rush, so I was hoping someone else might have a trick up their sleeve or spot my mistake, ...
adriaan

Nice job! Quite an eventful day here in scalaland.

thanks, except i broke the build a little, it seems -- looking into it :-/
adriaan

On Mon, Nov 9, 2009 at 9:24 PM, Paul Phillips <paulp@improving.org> wrote:

Nice job! Quite an eventful day here in scalaland.

--
Paul Phillips      | It is hard to believe that a man is
Moral Alien        | telling the truth when you know that you
Empiricist         | would lie if you were in his place.
all hip pupils!    |     -- H. L. Mencken


Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm

Hi Adriaan,

The changes look all good to me. We need to add a comment to
adjustTypeParams to reflect the new behavior (I have already taken
care of it in my checkout).

Cheers