2.8 collections

[Martin Odersky]

I have finished a first implementation of 2.8 collections. I'd like to
submit this as a SIP, so that it can be discussed and improved. For
practical reasons, the current design is already intregrated in trunk.
But this should not stop it from being discussed seriously.

Personally, I will let collections rest for the next two weeks or so,
because I need all my bandwidth for the Eclipse IDE overhoal.

Thanks

 -- Martin

[Michael Nascimento]

On page 6, Figure 4, xs takeRight n is mentioned twice. Its second
occurence should be replaced by another method call.

Regards,
Michael Nascimento Santos
https://genesis.dev.java.net/
https://jsr-310.dev.java.net/

On Mon, May 18, 2009 at 3:24 PM, martin odersky <[hidden email]> wrote:

> I have finished a first implementation of 2.8 collections. I'd like to
> submit this as a SIP, so that it can be discussed and improved. For
> practical reasons, the current design is already intregrated in trunk.
> But this should not stop it from being discussed seriously.
>
> Personally, I will let collections rest for the next two weeks or so,
> because I need all my bandwidth for the Eclipse IDE overhoal.
>
> Thanks
>
>  -- Martin
>

[Ben Jackman-2]

I had a few thoughts concerning some things on page 15, It's kind of long so I posted it to my blog, generally I am concerned about the mutable collections throwing UnsupportedOperationException when their hashCode method is called. (It violates the equals/hashCode contract and could be a nasty gotcha)

http://scalide.blogspot.com/2009/05/hashcode-equals-in-scala-28-collections.html

Martin Odersky wrote

I have finished a first implementation of 2.8 collections. I'd like to
submit this as a SIP, so that it can be discussed and improved. For
practical reasons, the current design is already intregrated in trunk.
But this should not stop it from being discussed seriously.

Personally, I will let collections rest for the next two weeks or so,
because I need all my bandwidth for the Eclipse IDE overhoal.

Thanks

 -- Martin

 

[Michael Nascimento]

On Mon, May 18, 2009 at 11:24 PM, Ben Jackman
<[hidden email]> wrote:
>
> I had a few thoughts concerning some things on page 15, It's kind of long so
> I posted it to my blog, generally I am concerned about the mutable
> collections throwing UnsupportedOperationException when their hashCode
> method is called. (It violates the equals/hashCode contract and could be a
> nasty gotcha)
>
> http://scalide.blogspot.com/2009/05/hashcode-equals-in-scala-28-collections.html

In general, I agree with it. Making hashCode throw an exception breaks
the equals/hashCode contract and sounds like a bad idea.

Regards,
Michael

[Landei]

Michael Nascimento wrote

On Mon, May 18, 2009 at 11:24 PM, Ben Jackman
<[e-mail]> wrote:
>
> I had a few thoughts concerning some things on page 15, It's kind of long so
> I posted it to my blog, generally I am concerned about the mutable
> collections throwing UnsupportedOperationException when their hashCode
> method is called. (It violates the equals/hashCode contract and could be a
> nasty gotcha)
>
> http://scalide.blogspot.com/2009/05/hashcode-equals-in-scala-28-collections.html

In general, I agree with it. Making hashCode throw an exception breaks
the equals/hashCode contract and sounds like a bad idea.

Regards,
Michael

+1

Except from that, it's a true piece of art.

Cheers,
Daniel

[Jesper Nordenberg]

Ben Jackman wrote:
> I had a few thoughts concerning some things on page 15, It's kind of long so
> I posted it to my blog, generally I am concerned about the mutable
> collections throwing UnsupportedOperationException when their hashCode
> method is called. (It violates the equals/hashCode contract and could be a
> nasty gotcha)

Agreed, this is a bad idea. Mutable collections are perfectly usable as
hash table keys provided their equals() implementation uses an object
identity check (the default Object.equals() implementation). I'd much
prefer an addition of a separate "equalElements" or similar method that
checks for momentary element equality.

What's the rationale behind the current implementation of mutable
collections equals()?

/Jesper Nordenberg

[David MacIver]

For what it's worth, I think throwing UnsupportedOperationException on
hashCode would be a mistake, as would reverting back to identity
equality semantics for mutable collections.

Having a consistent equality and hashCode between mutable and
immutable collections makes it that much easier to use the
collection.* classes without having to worry about whether your
implementation is mutable or immutable (something which seems to be a
goal in the 2.8 redesign).

Further, having a working hashCode to go with the equality is both
required by the contract of hashCode and extremely useful. There are
many cases where it's perfectly safe to use a mutable collection as a
hash key (either because you know you're not mutating the keys or
because the hash is completely transient - e.g. for providing
efficient uniqueness filtering on a collection).

Sacrificing these use cases for conceptual purity (which I don't think
the UnsupportedOperationException approach achieves anyway) seems
undesirable.

[Dimitris Andreou]

I see these two methods on sets:

xs put x : Adds element x to xs and returns whether x was previously
contained in the set.
xs remove x : Removes element x from xs and returns whether x was
previously contained in the set.

The semantics of the return values is the opposite of the analogous
methods of java.util.Collection#{add, remove}, is this intentional?
This is bound to create some confusion...

Dimitris

2009/5/18 martin odersky <[hidden email]>:

> I have finished a first implementation of 2.8 collections. I'd like to
> submit this as a SIP, so that it can be discussed and improved. For
> practical reasons, the current design is already intregrated in trunk.
> But this should not stop it from being discussed seriously.
>
> Personally, I will let collections rest for the next two weeks or so,
> because I need all my bandwidth for the Eclipse IDE overhoal.
>
> Thanks
>
>  -- Martin
>

[Martin Odersky]

On Tue, May 19, 2009 at 12:42 PM, Jim Andreou <[hidden email]> wrote:

> I see these two methods on sets:
>
> xs put x : Adds element x to xs and returns whether x was previously
> contained in the set.
> xs remove x : Removes element x from xs and returns whether x was
> previously contained in the set.
>
> The semantics of the return values is the opposite of the analogous
> methods of java.util.Collection#{add, remove}, is this intentional?
> This is bound to create some confusion...

Not true. Remove is the same as for Java. Put is the same as for
Java's map put, if you equate true with "object returned" -- this
equation holds for remove in any case. Put is different from Set.add
in Java, but then their names are different, too.

Cheers

 -- Martin

[Dimitris Andreou]

Oh, thanks for the clarification, I missed that the mismatch was only
between put and add, not remove.

Still, wouldn't an "add" be more intuitive (for Java programmers) than
a put with inverted return value?

Btw, reading this code (JavaConversions.scala):

  case class JSetWrapper[A](underlying : ju.Set[A]) extends
mutable.Set[A] with generic.MutableSetTemplate[A, JSetWrapper[A]] {
   ...
    override def put(elem: A): Boolean = underlying.add(elem)

I would expect to see a negation there. Right? Or did I miss something again?

2009/5/19 martin odersky <[hidden email]>:

> On Tue, May 19, 2009 at 12:42 PM, Jim Andreou <[hidden email]> wrote:
>> I see these two methods on sets:
>>
>> xs put x : Adds element x to xs and returns whether x was previously
>> contained in the set.
>> xs remove x : Removes element x from xs and returns whether x was
>> previously contained in the set.
>>
>> The semantics of the return values is the opposite of the analogous
>> methods of java.util.Collection#{add, remove}, is this intentional?
>> This is bound to create some confusion...
>
> Not true. Remove is the same as for Java. Put is the same as for
> Java's map put, if you equate true with "object returned" -- this
> equation holds for remove in any case. Put is different from Set.add
> in Java, but then their names are different, too.
>
> Cheers
>
>  -- Martin
>

[Martin Odersky]

On Tue, May 19, 2009 at 2:37 PM, Jim Andreou <[hidden email]> wrote:

> Oh, thanks for the clarification, I missed that the mismatch was only
> between put and add, not remove.
>
> Still, wouldn't an "add" be more intuitive (for Java programmers) than
> a put with inverted return value?
>
> Btw, reading this code (JavaConversions.scala):
>
>  case class JSetWrapper[A](underlying : ju.Set[A]) extends
> mutable.Set[A] with generic.MutableSetTemplate[A, JSetWrapper[A]] {
>   ...
>    override def put(elem: A): Boolean = underlying.add(elem)
>
> I would expect to see a negation there. Right? Or did I miss something again?
>

Yes, well spotted. We need to negate that. We might want to add the
add, also. I am not sure
yet.

Thanks

 -- Martin

[Kieron.Wilkinson]

Fantastic work Martin,

One extremely minor correction:
Page 8 paragraph 2: "(We are waiting for *the* integration of some more
refined implementations of immutable vectors into the library)."

One comment:
I'm not sure I understand the value of the WeakHashSet and WeakHashMap
implementations, but perhaps that is just because I have never found a
problem that is well solved using a java.util.WeakHashMap (I've never had
to do canonical mappings as suggested by the WeakReference Javadocs). I
personally find soft referenced collections far more useful (for caching),
and so I'll ask - would it be a better to instead provide something more
configurable, something like Google Collection's MapMaker which, among
other things, generates a ConcurrentMap with flexible reachability of
values, weak or soft?

Or maybe these classes really are useful and there are plenty of use cases
that I'm just not aware of?
 
Kieron




From:
martin odersky <[hidden email]>
To:
"[hidden email]" <[hidden email]>,
[hidden email]
Date:
18/05/09 19:24
Subject:
[scala-debate] 2.8 collections
Sent by:
[hidden email]



I have finished a first implementation of 2.8 collections. I'd like to
submit this as a SIP, so that it can be discussed and improved. For
practical reasons, the current design is already intregrated in trunk.
But this should not stop it from being discussed seriously.

Personally, I will let collections rest for the next two weeks or so,
because I need all my bandwidth for the Eclipse IDE overhoal.

Thanks

 -- Martin
[attachment "collections.pdf" deleted by Kieron
Wilkinson/CorpUK/BNYMellon]



This message may contain confidential and privileged information and is intended solely for the use of the named addressee. Access, copying or re-use of the e-mail or any information contained therein by any other person is not authorised. If you are not the intended recipient please notify us immediately by returning the e-mail to the originator and then immediately delete this message. Although we attempt to sweep e-mail and attachments for viruses, we do not guarantee that either are virus-free and accept no liability for any damage sustained as a result of viruses.

Please refer to http://www.bnymellon.com/disclaimer/piml.html for certain disclosures.

[Kris Nuttycombe-3]

A proposal for an additional method on mutable maps:

I find that one fairly common use case with mutable maps is to update
a value as a function of the previous value for a key and some
information from the scope in which the update is being performed. A
function with the following signature could be a useful addition to
the standard library:

def updated(k: K, default: V)(f: V => V): Map[K,V]

This operation can be performed in a somewhat clunky fashion using
getOrElseUpdate, but at least personally I find this usage pattern
common enough to justify inclusion in the standard library. I use it
frequently to perform "bucketed" reduce operations using foldLeft.

Kris


On Mon, May 18, 2009 at 12:24 PM, martin odersky <[hidden email]> wrote:

> I have finished a first implementation of 2.8 collections. I'd like to
> submit this as a SIP, so that it can be discussed and improved. For
> practical reasons, the current design is already intregrated in trunk.
> But this should not stop it from being discussed seriously.
>
> Personally, I will let collections rest for the next two weeks or so,
> because I need all my bandwidth for the Eclipse IDE overhoal.
>
> Thanks
>
>  -- Martin
>

[Erkki Lindpere-2]

+1

David MacIver wrote:

> For what it's worth, I think throwing UnsupportedOperationException on
> hashCode would be a mistake, as would reverting back to identity
> equality semantics for mutable collections.
>
> Having a consistent equality and hashCode between mutable and
> immutable collections makes it that much easier to use the
> collection.* classes without having to worry about whether your
> implementation is mutable or immutable (something which seems to be a
> goal in the 2.8 redesign).
>
> Further, having a working hashCode to go with the equality is both
> required by the contract of hashCode and extremely useful. There are
> many cases where it's perfectly safe to use a mutable collection as a
> hash key (either because you know you're not mutating the keys or
> because the hash is completely transient - e.g. for providing
> efficient uniqueness filtering on a collection).
>
> Sacrificing these use cases for conceptual purity (which I don't think
> the UnsupportedOperationException approach achieves anyway) seems
> undesirable.
>
>  

[Martin Odersky]

On Tue, May 19, 2009 at 2:49 PM, martin odersky <[hidden email]> wrote:

> On Tue, May 19, 2009 at 2:37 PM, Jim Andreou <[hidden email]> wrote:
>> Oh, thanks for the clarification, I missed that the mismatch was only
>> between put and add, not remove.
>>
>> Still, wouldn't an "add" be more intuitive (for Java programmers) than
>> a put with inverted return value?
>>
>> Btw, reading this code (JavaConversions.scala):
>>
>>  case class JSetWrapper[A](underlying : ju.Set[A]) extends
>> mutable.Set[A] with generic.MutableSetTemplate[A, JSetWrapper[A]] {
>>   ...
>>    override def put(elem: A): Boolean = underlying.add(elem)
>>
>> I would expect to see a negation there. Right? Or did I miss something again?
>>
> Yes, well spotted. We need to negate that. We might want to add the
> add, also. I am not sure
> yet.

In fact, we just decided we'll change Set.put for Set.add, with the
swap in return value.

Thanks again

 -- Martin

[Martin Odersky]

On Tue, May 19, 2009 at 5:06 PM,  <[hidden email]> wrote:

> Fantastic work Martin,
>
> One extremely minor correction:
> Page 8 paragraph 2: "(We are waiting for *the* integration of some more
> refined implementations of immutable vectors into the library)."
>
> One comment:
> I'm not sure I understand the value of the WeakHashSet and WeakHashMap
> implementations, but perhaps that is just because I have never found a
> problem that is well solved using a java.util.WeakHashMap (I've never had
> to do canonical mappings as suggested by the WeakReference Javadocs). I
> personally find soft referenced collections far more useful (for caching),
> and so I'll ask - would it be a better to instead provide something more
> configurable, something like Google Collection's MapMaker which, among
> other things, generates a ConcurrentMap with flexible reachability of
> values, weak or soft?
>

I am not enough of an expert on this, unfortunately. I someone wants
to contribute better soft referenced collections, great!

Cheers

 -- Martin

[Paul Ford]

Martin Odersky wrote

I have finished a first implementation of 2.8 collections. ...

A few minor typos in "Scala 2.8 Collections", May 18, 2009:

page 6, section 3.2, para 2: word "used" probably  missing from "less-often methods"

page 6, figure 4: second "takeRight" should be "takeLeft"

page 8, fig 6: "xs +: buf" should be "xs ++: buff"

page 8, par 3 "inserAll" should be "insertAll"

page 13, fig 10: missing closing paren in "ms += (k -> v"

page 24, fig 18: "imscamutable" should be "immutable"

[Paul Ford]

Martin Odersky wrote

I have finished a first implementation of 2.8 collections. ...

Gave the document a quick read. It seems to address and correct suprising semantics for the current collection operators. Behavior that I ran into, and was stumped by, within the first few hours of experimenting in earnest with Scala.

The specific surprising behavior was inconsistent semantics of the ++ operator depending on whether the the target was a mutable or immutable Set. I wrote a couple of precondition contracts on a pair of Set parameters asserting that they partitioned a third set. Much to my surprise and consternation "require(set1 ++ set2 == set3)" created an unexpected side effect on set1 when set1 was mutable, and no side effect at all (as intended and expected) when set1 was immutable.

It appears in the 2.8 collections that operators with a collection result (such as +, ++, -, --) do not have side effects regardless of whether the target object is mutable or immutable. Side effects are explicit and intentional when the operator is of the form +=, ++=, +: etc.

Is my understanding of the change in the 2.8 semantics correct?

[Kieron.Wilkinson]

On Tue, May 19, 2009 at 5:06 PM,  <[hidden email]>
wrote:
> I'm not sure I understand the value of the WeakHashSet and WeakHashMap
> implementations, but perhaps that is just because I have never found a
> problem that is well solved using a java.util.WeakHashMap (I've never
had
> to do canonical mappings as suggested by the WeakReference Javadocs). I
> personally find soft referenced collections far more useful (for
caching),
> and so I'll ask - would it be a better to instead provide something more
> configurable, something like Google Collection's MapMaker which, among
> other things, generates a ConcurrentMap with flexible reachability of
> values, weak or soft?

On Tue, May 19, 2009 at 5:12 PM, martin odersky <[hidden email]>
wrote:
> I am not enough of an expert on this, unfortunately. I someone wants
> to contribute better soft referenced collections, great!

Sadly, neither am I. I'd be happy to have a go, but being a beginner in
Scala, I fully expect whatever I produced would be far from idiomatic.
Obviously this is a good excuse to get better at both :)

Kieron


This message may contain confidential and privileged information and is intended solely for the use of the named addressee. Access, copying or re-use of the e-mail or any information contained therein by any other person is not authorised. If you are not the intended recipient please notify us immediately by returning the e-mail to the originator and then immediately delete this message. Although we attempt to sweep e-mail and attachments for viruses, we do not guarantee that either are virus-free and accept no liability for any damage sustained as a result of viruses.

Please refer to http://www.bnymellon.com/disclaimer/piml.html for certain disclosures.

[Kieron.Wilkinson]

Does the Option class fit into these new collections?

I tend to think of an Option as a bounded (0..1) immutable collection. Is
that wrong? It currently doesn't fit into the hierarchy, but assuming it
should be thought of as a collection, I wonder whether it shouldn't at
least be Transversable... I think all the methods make sense, though at
first glance some don't look particularly useful in the context of an
option (e.g. partition). I guess there are problems though, like what ++
would return - certainly not an Option!

I suppose it not being part of the collection hierarchy just struck me as
slightly inconsistent, but I guess the structural typing in Scala removes
the need for it. So, perhaps I just argued myself out of this... :-)

Kieron




From:
martin odersky <[hidden email]>
To:
"[hidden email]" <[hidden email]>,
[hidden email]
Date:
18/05/09 19:24
Subject:
[scala-debate] 2.8 collections
Sent by:
[hidden email]



I have finished a first implementation of 2.8 collections. I'd like to
submit this as a SIP, so that it can be discussed and improved. For
practical reasons, the current design is already intregrated in trunk.
But this should not stop it from being discussed seriously.

Personally, I will let collections rest for the next two weeks or so,
because I need all my bandwidth for the Eclipse IDE overhoal.

Thanks

 -- Martin



This message may contain confidential and privileged information and is intended solely for the use of the named addressee. Access, copying or re-use of the e-mail or any information contained therein by any other person is not authorised. If you are not the intended recipient please notify us immediately by returning the e-mail to the originator and then immediately delete this message. Although we attempt to sweep e-mail and attachments for viruses, we do not guarantee that either are virus-free and accept no liability for any damage sustained as a result of viruses.

Please refer to http://www.bnymellon.com/disclaimer/piml.html for certain disclosures.