look ma, I'm generic

[Paul Phillips]

Maybe this is just a day at the beach for some of you fancy type programmers.

One invert function:

- works on sequential collections, parallel collections, Iterators,
Arrays, Strings, etc.
- preserves Stream laziness (something not presently accomplished by
e.g. zipped)
- is installed with an implicit conversion which takes only three
type parameters (for Tuple3) and no implicit parameters
(this being important in Predef for implicit search performance reasons)

The one change I had to make to the collections (and it should be
immaterial unless you need it) to achieve this lovely sameness of
implementation is to add this interface:

trait Container[+A, +CC[X] <: GenTraversableOnce[X]] extends Any
with GenTraversableOnce[A]

Because there is so far as I can tell no common parent to Iterator and
Traversable which preserves the shape of the container.

I just called it "Container". It doesn't have to be that, but please
for god's sake don't suggest I should call it
"GenTraversableOnceLike". Let's have something sanely named at the
very top of the hierarchy to which we can program when we're not
overly concerned with the distinctions among the many different ways
of bunching stuff.

Feedback solicited. (Silence is endorsement.) The total patch is quite
small, see for yourself.

https://github.com/paulp/scala/compare/master...topic%2Finvert


scala> (Iterator(1), Iterator("a"), Iterator(Array(1))).invert
res0: Iterator[(Int, String, Array[Int])] = non-empty iterator

scala> (Array(1), Array("a"), Array(Array(1))).invert
res1: Array[(Int, String, Array[Int])] = Array((1,a,Array(1)))

scala> (List(1), List("a"), List(Array(1))).invert
res2: List[(Int, String, Array[Int])] = List((1,a,Array(1)))

scala> (Seq(1), List("a"), Vector(Array(1))).invert
res3: Seq[(Int, String, Array[Int])] = List((1,a,Array(1)))

scala> (Vector(1), List("a"), Seq(Array(1))).invert
res4: scala.collection.immutable.Vector[(Int, String, Array[Int])] =
Vector((1,a,Array(1)))

scala> (Stream from 1, Stream from 2, Stream from 3).invert
res5: scala.collection.immutable.Stream[(Int, Int, Int)] = Stream((1,2,3), ?)

scala> ("abc", "def", "ghi").invert
res6: scala.collection.immutable.IndexedSeq[(Char, Char, Char)] =
Vector((a,d,g), (b,e,h), (c,f,i))

scala> (1 to 10 par, 1 to 10 par, 1 to 10 par).invert
warning: there were 3 feature warnings; re-run with -feature for details
res7: scala.collection.parallel.immutable.ParSeq[(Int, Int, Int)] =
ParVector((1,1,1), (2,2,2), (3,3,3), (4,4,4), (5,5,5), (6,6,6),
(7,7,7), (8,8,8), (9,9,9), (10,10,10))

[Simon Ochsenreither]

Container sounds very ... C++ like (nothing wrong with that).

Depending on the things you want to cover ... what about Collection?

PS: Any news about the idea to reduce the number of traits in the collection hierarchy?

Thinking a bit about it, I pretty much like Collection. It will be familiar to Java people. This would fix one of the long-standing concerns that almost no one knows or can figure out which common collection type should be used.

[David Hall]

Think about all the confused emails and posts on StackOverflow when
Java converts find out that Iterator <: Collection...

[Paul Phillips]

On Wed, May 2, 2012 at 11:12 AM, Simon Ochsenreither
<simon.och...@googlemail.com> wrote:

> Depending on the things you want to cover ... what about Collection?

That's fine with me, I thought of that one too. I thought maybe the
deprecated one was still floating around, but it's gone, so I don't
see a problem with it.

> This would fix one of the long-standing concerns that almost no one knows or can figure out which common collection type should be used.

Yes, it would be nice if people weren't always (understandably, it's
confusing and there are unnecessary penalties for trying to be
general) selecting overly specific types.

[Paul Phillips]

On Wed, May 2, 2012 at 11:15 AM, David Hall <dl...@cs.berkeley.edu> wrote:
> Think about all the confused emails and posts on StackOverflow when
> Java converts find out that Iterator <: Collection...

Okay, let's just call it Stuff.

trait Stuff[+A, +CC[X] <: Stuff[X, CC]]

I'm only half kidding. Ready for some five-character standard names,
I am. They don't make them like you guys anymore, Seq Set and Map.

[√iktor Ҡlang]

Bag

--
Viktor Klang

Akka Tech Lead

Typesafe - The software stack for applications that scale

Twitter: @viktorklang

[Alex Repain]

In which package is it ? I'm pretty sure I have some code with

import scala.collection.somePackage._

trait Collection[X]

somewhere, for learning purpose. But others may be doing that in real-life applications... Not the worst compatibility broker, but...

2012/5/2 Paul Phillips <pa...@improving.org>

[Daniel Sobral]

On Wed, May 2, 2012 at 3:31 PM, Paul Phillips <pa...@improving.org> wrote:
> On Wed, May 2, 2012 at 11:15 AM, David Hall <dl...@cs.berkeley.edu> wrote:
>> Think about all the confused emails and posts on StackOverflow when
>> Java converts find out that Iterator <: Collection...
>
> Okay, let's just call it Stuff.

Hah! No. Please. :-)

>  trait Stuff[+A, +CC[X] <: Stuff[X, CC]]

One problem with with the above is that only collections with a single
type parameter can match it. So Map will never match (becomes
Iterable), nor BitSet (becomes Set). OTOH, your patch doesn't drag
Stuff down to every class -- just define it at the top-most level, so
I presume this isn't relevant to the issues you are trying to deal
with, but I thought I might as well raise the issue anyway, just in
case.

If that's not a problem, I'm happy with it (I'm happy with anything
that makes it possible for the user to interact with collections in
any other way than calling methods on them).

>
> I'm only half kidding.  Ready for some five-character standard names,
> I am.  They don't make them like you guys anymore, Seq Set and Map.

--
Daniel C. Sobral

I travel to the future all the time.

[Brian Smith]

On 2 May 2012 19:31, Paul Phillips <pa...@improving.org> wrote:

I'm only half kidding.  Ready for some five-character standard names,
I am.  They don't make them like you guys anymore, Seq Set and Map.

Bag? :)

[Paul Phillips]

On Wed, May 2, 2012 at 11:35 AM, Daniel Sobral <dcso...@gmail.com> wrote:
> One problem with with the above is that only collections with a single
> type parameter can match it. So Map will never match (becomes
> Iterable), nor BitSet (becomes Set). OTOH, your patch doesn't drag
> Stuff down to every class -- just define it at the top-most level, so
> I presume this isn't relevant to the issues you are trying to deal
> with, but I thought I might as well raise the issue anyway, just in
> case.

Any attempt to address arity-genericity with our current language
capabilities would rapidly defeat my ambition of having something
standard, pithily named, and simpler than anything which yet exists.
We already have plenty of complicated ways for people to do things.
I'm more than happy with squashing Map down to Iterable and BitSet
down to Set.

[richard emberson]

Poly

trait Poly[+A, +CC[X] <: Poly[X, CC]]

At least its short

--
Quis custodiet ipsos custodes

[Ryan Hendrickson]

At risk of being stoned by people who want, y'know, things to compile *quickly*, I'll point out that I think there's a More Generic Thing here than just collections.

+1 point from me if invert can do this:

scala> ((a: String) => a.length, (a: String) => a + "!").invert
res0: String => (Int, String) = <function1>

+5 points from me if invert can do this:

scala> ((a: String) => a.length, (b: Option[Double]) => b getOrElse Double.NaN).invert
res0: ((String, Option[Double])) => (Int, Double) = <function1>

+10 points from me if invert does the above for any arrow, not just Function1, using that arrow's definition of (&&&) and (***)

+all of the points from me if invert captures the whole idea that certain pairs of type constructors of arbitrary but fixed arity F[_, _, ...], G[_, _, ...] can be ‘transposed’ in a general way to yield a function for any A, B, ..., M, N, ... of type

F[G[A, B, ...], G[M, N, ...], ...] => G[F[A, M, ...], F[B, N, ...], ...]

(And here's the point where one of the Scalaz guys pop up and tell me they have this already. :-) Please do, if so!)

----------------------------------------

This message is intended exclusively for the individual(s) or entity to
which it is addressed. It may contain information that is proprietary,
privileged or confidential or otherwise legally exempt from disclosure.
If you are not the named addressee, you are not authorized to read,
print, retain, copy or disseminate this message or any part of it.
If you have received this message in error, please notify the sender
immediately by e-mail and delete all copies of the message.

[Simon Ochsenreither]

Now I just wonder where it should be placed ... scala.collection.Collection looks a bit unfortunate. I guess we would need to Collection to Predef in this case ...

[Paul Phillips]

I wouldn't try to do it with the same function - I don't aspire to
that level of genericity anyway. But it's easy enough to go at least
to +5 (which I realize you must know.) And significantly further, I'm
sure, but one has to be steeled for battle.

class F1Ops[T1, T2](x: (T1, T2)) {
def merge[In, R1, R2](implicit w1: T1 => In => R1, w2: T2 => In =>
R2): In => (R1, R2) =
(p: In) => (x._1(p), x._2(p))

def join[In1, In2, R1, R2](implicit w1: T1 => In1 => R1, w2: T2 =>
In2 => R2): (In1, In2) => (R1, R2) =
(p1: In1, p2: In2) => (x._1(p1), x._2(p2))
}
implicit def addF1Ops[T1 <: Function1[_,_], T2 <: Function1[_,_]](x:
(T1, T2)) = new F1Ops(x)

scala> ((a: String) => a.length, (a: String) => a + "!").merge apply "abc"
res1: (Int, String) = (3,abc!)

scala> ((a: String) => a.length, (b: Option[Double]) => b getOrElse

Double.NaN).join apply (("abc", Some(5.5f)))
res2: (Int, Double) = (3,5.5)

[Tony Morris]

On 03/05/12 05:13, Ryan Hendrickson wrote:
> At risk of being stoned by people who want, y'know, things to compile *quickly*, I'll point out that I think there's a More Generic Thing here than just collections.
>
> +1 point from me if invert can do this:
>
> scala> ((a: String) => a.length, (a: String) => a + "!").invert
> res0: String => (Int, String) = <function1>

Costate/State

> +5 points from me if invert can do this:
>
> scala> ((a: String) => a.length, (b: Option[Double]) => b getOrElse Double.NaN).invert
> res0: ((String, Option[Double])) => (Int, Double) = <function1>

Don't understand.

> +10 points from me if invert does the above for any arrow, not just Function1, using that arrow's definition of (&&&) and (***)

My guess was you were writing *** though not sure. There are things with
*** that are not arrows by the way.

> +all of the points from me if invert captures the whole idea that certain pairs of type constructors of arbitrary but fixed arity F[_, _, ...], G[_, _, ...] can be ‘transposed’ in a general way to yield a function for any A, B, ..., M, N, ... of type
>
> F[G[A, B, ...], G[M, N, ...], ...] => G[F[A, M, ...], F[B, N, ...], ...]

Isn't this just writing it at the type-level? The type system is
turing-complete

> (And here's the point where one of the Scalaz guys pop up and tell me they have this already. :-) Please do, if so!)

Probably. The *** method is derived from any instance of the Split
type-class, which is not fully generalised.

trait Split[=>:[_, _]] extends Category[=>:] { self =>
def split[A, B, C, D](f: A =>: B, g: C =>: D): (A, C) =>: (B, D)

--
Tony Morris
http://tmorris.net/

[martin odersky]

I vote against. Consistency in naming is hugely important for any library and in particular for collections. Container breaks that consistency because it uses a different name than all the other classes that fulfill conceptually the same role. It's also a potential misnomer, because containment implies persistence, so it's a stretch to say that an iterator contains its elements.

Most importantly, we have so many fires to fight right now, that it would be a welcome relief not to have to change the root classes of collections. The only change to collections I would consider at the present stage is a reduction in the number of base classes, not an augmentation. Yes, there is a tiny loss of genericity but I personally would not care too much about that. 

Cheers

 - Martin

--
Martin Odersky
Prof., EPFL and Chairman, Typesafe
PSED, 1015 Lausanne, Switzerland
Tel. EPFL: +41 21 693 6863
Tel. Typesafe: +41 21 691 4967

[Stefan Wagner]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Am 02.05.2012 21:13, schrieb Ryan Hendrickson:

> This message is intended exclusively for the individual(s) or entity to
> which it is addressed. It may contain information that is proprietary,
> privileged or confidential or otherwise legally exempt from disclosure.
> If you are not the named addressee, you are not authorized to read,
> print, retain, copy or disseminate this message or any part of it.
> If you have received this message in error, please notify the sender
> immediately by e-mail and delete all copies of the message.

Please, if you don't want me to read a message - don't send it.

How shall I know before reading, that I shall not read it, when you send
it to me, and the disclaimer is at the end?

I don't accept this disclaimer - not for this mail, not for any future
mail. Tell you lawyers.

Notice, that in my legal scope, you can't define such a contract from
one side.


- --

Tschööö--->...Stefan
- ---------------------------
Don't visit my homepage at:
http://home.arcor-online.net/hirnstrom
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAk+id6kACgkQQeATqGpDnRpvvgCghCtJZx6BDlonewt/zStEQ1XA
Tk0AoIVEN6kQkN6jBlBiQm+9aVUzYFca
=1Vxm
-----END PGP SIGNATURE-----

[Justin du coeur]

On Thu, May 3, 2012 at 8:18 AM, Stefan Wagner <hirn...@arcor.de> wrote:

Please, if you don't want me to read a message - don't send it.

Note that this is common (especially American) legal boilerplate.  Some people can't even control it: their corporate mail systems attach it to any email they send, whether they like it or not.

Stupid, yes, but usually not something the sender is including by their own will.  It's usually the fault of corporate lawyers...

[Roland Kuhn]

On May 3, 2012, at 14:18 , Stefan Wagner wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Am 02.05.2012 21:13, schrieb Ryan Hendrickson:
>
>> This message is intended exclusively for the individual(s) or entity to
>> which it is addressed. It may contain information that is proprietary,
>> privileged or confidential or otherwise legally exempt from disclosure.
>> If you are not the named addressee, you are not authorized to read,
>> print, retain, copy or disseminate this message or any part of it.
>> If you have received this message in error, please notify the sender
>> immediately by e-mail and delete all copies of the message.
>
> Please, if you don't want me to read a message - don't send it.
>
> How shall I know before reading, that I shall not read it, when you send
> it to me, and the disclaimer is at the end?
>
> I don't accept this disclaimer - not for this mail, not for any future
> mail. Tell you lawyers.
>
> Notice, that in my legal scope, you can't define such a contract from
> one side.
>

That particular horse died of vicious violence many times over.

Regards,

Roland Kuhn
Typesafe – The software stack for applications that scale.
twitter: @rolandkuhn

PS: at least the disclaimer is in a position where it is easily ignored.

[Paul Phillips]

It's incredibly rude to hijack my thread to air your grievances about
something unrelated. Please, this is "scala-language" and it's plenty
difficult keeping people focused as it is.

[Stefan Wagner]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Am 02.05.2012 21:13, schrieb Ryan Hendrickson:

> This message is intended exclusively for the individual(s) or entity to
> which it is addressed. It may contain information that is proprietary,
> privileged or confidential or otherwise legally exempt from disclosure.
> If you are not the named addressee, you are not authorized to read,
> print, retain, copy or disseminate this message or any part of it.
> If you have received this message in error, please notify the sender
> immediately by e-mail and delete all copies of the message.

Please, if you don't want me to read a message - don't send it.

How shall I know before reading, that I shall not read it, when you send
it to me, and the disclaimer is at the end?

I don't accept this disclaimer - not for this mail, not for any future
mail. Tell you lawyers.

Notice, that in my legal scope, you can't define such a contract from
one side.


- --

Tschööö--->...Stefan
- ---------------------------
Don't visit my homepage at:
http://home.arcor-online.net/hirnstrom
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAk+irAwACgkQQeATqGpDnRqPGACfaxk1kK0lyaK4efSLvsI+MYSd
TjAAn1DdQEhP2SgAHTJmdVSwTXHoHVoW
=4fiP
-----END PGP SIGNATURE-----

[Josh Suereth]

Hey look, a Container[T] naming bike shed.

What's that doing in a thread about lawyers?

[Shelby]

On May 3, 2:28 am, Paul Phillips <pa...@improving.org> wrote:

> On Wed, May 2, 2012 at 11:12 AM, Simon Ochsenreither <simon.ochsenreit...@googlemail.com> wrote:
> > This would fix one of the long-standing concerns that almost no one knows or can figure out which common collection type should be used.
>
> Yes, it would be nice if people weren't always (understandably, it's
> confusing and there are unnecessary penalties for trying to be
> general) selecting overly specific types.

I am thinking the problem is that the interface names are too general,
and thus end up as conflated gibberish, e.g. "GenTraversableOnceLike".

I would vote for naming the interface "Invert". Orthogonality is
important.

But why not a more general fold operation and interface named
"Foldable"?

I understand a fold can create a new copy of the abstraction it is
folding over. Foldable could contain a fold method and an invert
method. The invert method calls the fold method. Then subtypes only
have to implement the fold method.

Also, a Traversable combines a Functor.map and Foldable.fold in a
single pass of the iteration:

Applicative programming with effects, McBride & Paterson
The Essence of the Iterator Pattern, Gibbons & Oliveira

[Shelby]

On May 4, 2:40 pm, Shelby <she...@coolpage.com> wrote:
> I would vote for naming the interface "Invert". Orthogonality is
> important.

Typo: make that "Invertible".