Revised collections

The attachment is not the pdf :)

On Sep 25, 2009, at 19:54, martin odersky wrote:

> I just checked in a fairly large refactoring of the collections
> framework. Essentially, quite a few classes have been moved out the
> the collections.generic package and into the regular packages. This
> affects all the Template classes (which are now uniformly renamed to
> "...Like" classes), the builders, the views, and the proxies.
>
> The observation was that these were classes that occasionally were
> useful for clients of collection libraries. We wanted to keep in
> generic only those classes that were definitely only used by
> collection implementers, never by collection clients.
>
> Also, hashCode is uniformly implemented, following the discussion on
> this list some weeks ago.
>
> An updated whitepaper pdf is attached.
>
> Cheers
>

Here comes the right pdf.

Sorry

Martin~

Is there a good way to provide typo corrections for the document?

Matt

On Fri, Sep 25, 2009 at 1:09 PM, martin odersky <martin.odersky@epfl.ch> wrote:

Here comes the right pdf.

Sorry

Hi Matt,

I include the source; if you wish do it directly there.

Thanks a lot!

All~

The attached patch contains a bunch of small corrections.  Also worth considering are the following larger changes:

xs slice (from, to) A collection consisting of elements in some index range
of xs.

I assume the range is [from, to) but that should probably be spelled out.  Possibly just calling out the definition of "index range" more carefully (it is defined implicitly on page 7, but is used earlier).

xs sameElements ys A test whether xs and ys contain the same elements in
the same order

Should probably mention that the ordering constraint doesn't apply to unordered collections.

xs indexOf x The index of the first element in xs equal to x. (several variants
exist).

Should spell out whether this means `element.equals(x)`, `element Java== x`, or `element scala== x`.


Matt



On Fri, Sep 25, 2009 at 1:52 PM, martin odersky <martin.odersky@epfl.ch> wrote:

Hi Matt,

I include the source; if you wish do it directly there.

Thanks a lot!

// original post is from [scala-internals]

On Friday 25 September 2009 23:55:09 Matt Fowles wrote:
> The attached patch contains a bunch of small corrections.

I have tried (after patching):

$ texi2html collections.src
** empty document

Sorry, have not worked with sych documents earlier. Please, point me how to
covert to html.

Thanks Matt, the patched version is online. Please read below, however.

Matt Fowles wrote:
> xs sameElements ys A test whether xs and ys contain the same elements in
>> the same order
>
> Should probably mention that the ordering constraint doesn't apply to
> unordered collections.
>

This is a good point, and it shouldn't. However, as of r18812:

scala> val o=Set(1,4,7,2)
scala> val u=Set(7,1,4,2)
scala> o equals u
res0: Boolean = true
scala> o sameElements u
res1: Boolean = false

I suppose that order should never matter in an unordered set, and that two
unordered set should be equal iff they contain the same elements, but that
does not seem to be the case; I find that a bit surprising. Equality and
co. are tricky, however, so I'll leave the matter to our collection
experts, as well as your next observation:

> xs indexOf x The index of the first element in xs equal to x. (several
>> variants
>> exist).
>
> Should spell out whether this means `element.equals(x)`, `element Java== x`,
> or `element scala== x`.
>

Toni

On Thu, Oct 1, 2009 at 3:27 PM, Antonio Cunei wrote:
> Thanks Matt, the patched version is online. Please read below, however.
>
> Matt Fowles wrote:
>>
>> xs sameElements ys A test whether xs and ys contain the same elements in
>>>
>>> the same order
>>
>> Should probably mention that the ordering constraint doesn't apply to
>> unordered collections.
>>
>
> This is a good point, and it shouldn't. However, as of r18812:
>
> scala> val o=Set(1,4,7,2)
> scala> val u=Set(7,1,4,2)
> scala> o equals u
> res0: Boolean = true
> scala> o sameElements u
> res1: Boolean = false
>
> I suppose that order should never matter in an unordered set, and that two
> unordered set should be equal iff they contain the same elements, but that
> does not seem to be the case; I find that a bit surprising. Equality and co.
> are tricky, however, so I'll leave the matter to our collection experts, as
> well as your next observation:
>
>> xs indexOf x The index of the first element in xs equal to x. (several
>>>
>>> variants
>>> exist).
>>
>> Should spell out whether this means `element.equals(x)`, `element Java==
>> x`,
>> or `element scala== x`.
>>
>
> Toni
>

What's the contract on comparing a Set and a SortedSet?
Given that SortedSet is a subclass of Set, it looks like we have an
LSP violation here!

Perhaps a better solution would be to make sameElements an illegal
operation when either the LHS or RHS is an (unordered) set? I just
can't see a clean way of doing this without resorting to a runtime
check.

Maybe sameElements should be moved to Seq. The way it is, its contract
seems to be: Take the iterators of the two operands and compare
whether they yield the same elements. For a set or a map, the order of
elements in the iterator might not be defined, but that in itself is
not a problem. Also, one need to be careful not to have too much
duplication between equals and sameElements. If they do the same
thing, why have both?

Cheers

Having the "same elements" and being equal are clearly different things. And the most obvious difference is that having the same elements says nothing about how those elements are ordered.   To me, a method "sameElements" which does anything other than unordered set comparision doesn't make sense.

On Thu, Oct 1, 2009 at 1:08 PM, martin odersky <martin.odersky@epfl.ch> wrote:

Maybe sameElements should be moved to Seq. The way it is, its contract
seems to be: Take the iterators of the two operands and compare
whether they yield the same elements. For a set or a map, the order of
elements in the iterator might not be defined, but that in itself is
not a problem. Also, one need to be careful not to have too much
duplication between equals and sameElements. If they do the same
thing, why have both?

Cheers

 -- Martin

--
Daniel C. Sobral

Something I learned in academia: there are three kinds of academic reviews: review by name, review by reference and review by value.

On Thu, Oct 01, 2009 at 06:08:23PM +0200, martin odersky wrote:
> Maybe sameElements should be moved to Seq.

I was just going to say the same thing.

On Thu, Oct 01, 2009 at 01:49:47PM -0300, Daniel Sobral wrote:
> Having the "same elements" and being equal are clearly different
> things. And the most obvious difference is that having the same
> elements says nothing about how those elements are ordered.

If you do something crazy like infer the meaning of the method from its
name, sure. However sameElements has long meant "same elements in same
order" and the ship has sailed. So moving it to Seq is better.

So everyone appreciates that "everything old is new again", pretty much
anytime anything ever comes up it has already been battled in the past.

http://lampsvn.epfl.ch/trac/scala/ticket/888
"Iterable.sameElements is wrong"
"Method should be called sameElementsInSameOrder and defined in Seq trait."

closed: wontfix by, um, me, but not because I didn't want to

http://lampsvn.epfl.ch/trac/scala/ticket/1384
"s == null should generate a warning?"

closed: wontfix by martin
(And I agree with Sean's position, whoa that feels weird)

On Thu, Oct 1, 2009 at 6:49 PM, Daniel Sobral wrote:
> Having the "same elements" and being equal are clearly different things. And
> the most obvious difference is that having the same elements says nothing
> about how those elements are ordered.
>
> To me, a method "sameElements" which does anything other than unordered set
> comparision doesn't make sense.
>
not multi-set comparison? It's slippery. In fact, I'm starting to
understand why it's called sameElements: `iterator' used to be called
`elements`. So the contract is really that the elements returned form
the iterator are the same. Anyway, it seems like we should deprecate
`sameElements' and maybe introduce a `sameIterator' method with the
same functionality, or else move `sameElements' to Seq (but then I
don't see why have it and also `=='? The only difference seemed to be
that with sameElements I could compare a set and a seq, whereas
compared with == that would always return false).

Cheers

On Thu, Oct 01, 2009 at 07:21:00PM +0200, martin odersky wrote:
> (but then I don't see why have it and also `=='? The only difference
> seemed to be that with sameElements I could compare a set and a seq,
> whereas compared with == that would always return false).

a) == can be refined by collections (ours, or peoples' custom ones) to
be tighter while allow sameElements to remain true.

b) If history is any guide, we still haven't thought of or dealt with
all the equality issues, and having separate methods provides a valuable
layer of indirection and future flexibility.