Should the view of a set behave like a set?

Daniel Sobral wrote:
> Set(1, 2, 3).view.map(_ => 1)
>
> If I print it, check its size, or anything like that, should I expect one element or three elements?

I would certainly expect one element, as in:

scala> Set(1, 2, 3).view.map(_ => 1).force
res0: Iterable[Int] = Set(1)

This is completely surprising to me (although I can see why it behaves the way it does):

scala> Set(1, 2, 3).view.map(_ => 1).size
res1: Int = 3

as is this:

scala> Set(1, 2, 3).view.map(_ => 1).foreach(println)
1
1
1

- Andreas

as from the scaladoc for 2.8.1, the view method for Set is :

*******************
def view : IterableView[A, Set[A]]

Creates a non-strict view of this set.

Creates a non-strict view of this set.

returns a non-strict view of this set.

definition classes: IterableLike → TraversableLike

*******************

then the map method for an iterableView :

*******************
def map [B] (f: (A) ⇒ B) : Iterable[B]

[use case] Builds a new collection by applying a function to all elements of this iterable collection.

[use case]

Builds a new collection by applying a function to all elements of this iterable collection.

B : the element type of the returned collection.

f  : the function to apply to each element.

returns a new iterable collection resulting from applying the given function f to each element of this iterable collection and collecting the results.

attributes: abstract

definition classes: TraversableLike

*******************

As the final return value is of type Iterable[Int], there is no guarantee upon any Set-particularl rule (like here, uniqueness in the Set) ...
Maybe specialization of IterableView methods for the Set case could solve this ?

Alex

2010/12/26 Andreas Flierl <andreas@flierl.eu>

Daniel Sobral wrote:
> Set(1, 2, 3).view.map(_ => 1)
>
> If I print it, check its size, or anything like that, should I expect one element or three elements?

I would certainly expect one element, as in:

scala> Set(1, 2, 3).view.map(_ => 1).force
res0: Iterable[Int] = Set(1)

This is completely surprising to me (although I can see why it behaves the way it does):

scala> Set(1, 2, 3).view.map(_ => 1).size
res1: Int = 3

as is this:

scala> Set(1, 2, 3).view.map(_ => 1).foreach(println)
1
1
1

- Andreas

I'll trade correctness for performance (almost) any day, and when I use sets instead of lighter-weight data structures I'm pretty much always concerned with correctness.  I would expect one element.

On Sat, Dec 25, 2010 at 5:49 PM, Daniel Sobral <dcsobral@gmail.com> wrote:

Consider this code:
Set(1, 2, 3).view.map(_ => 1)
If I print it, check its size, or anything like that, should I expect one element or three elements? I can see that expecting one element would result in a very slow implementation, but...

--
Daniel C. Sobral

I travel to the future all the time.

Then why use view in the first place? ISTM that if you want set-wise
correctness at every step, you shouldn't invoke view, and if you
invoke view, you should invoke force at the point where you need
set-wise correctness.

On Sat, Dec 25, 2010 at 3:45 PM, Erik Engbrecht
wrote:
> I'll trade correctness for performance (almost) any day, and when I use sets
> instead of lighter-weight data structures I'm pretty much always concerned
> with correctness.  I would expect one element.
>
> On Sat, Dec 25, 2010 at 5:49 PM, Daniel Sobral wrote:
>>
>> Consider this code:
>> Set(1, 2, 3).view.map(_ => 1)
>> If I print it, check its size, or anything like that, should I expect one
>> element or three elements? I can see that expecting one element would result
>> in a very slow implementation, but...
>>
>> --
>> Daniel C. Sobral
>>
>> I travel to the future all the time.
>
>

On Saturday December 25 2010, Erik Engbrecht wrote:
> I'll trade correctness for performance (almost) any day, and when I
> use sets instead of lighter-weight data structures I'm pretty much
> always concerned with correctness. I would expect one element.

The first part of that sounds like you're saying you'll trade away
correctness in return for performance. Is that what you mean?

Randall Schulz

From http://www.scala-lang.org/api/current/scala/collection/TraversableViewLi...

"""
A view is a lazy version of some collection. Collection transformers
such as map or filter or ++ do not traverse any elements when applied
on a view. Instead they create a new view which simply records that
fact that the operation needs to be applied. The collection elements
are accessed, and the view operations are applied, when a non-view
result is needed, or when the force method is called on a view.
"""

I guess the question is, when is a non-view result needed? size and
foreach both seem like such times, so it seems that
TraversableViewLike ought to override them.

On Sat, Dec 25, 2010 at 3:20 PM, Alex Repain wrote:
> as from the scaladoc for 2.8.1, the view method for Set is :
>
> *******************
>
> def view : IterableView[A, Set[A]]
>
> Creates a non-strict view of this set.
>
> Creates a non-strict view of this set.
>
> returns a non-strict view of this set.
> definition classes: IterableLike → TraversableLike
>
> *******************
>
> then the map method for an iterableView :
>
> *******************
>
> def map [B] (f: (A) ⇒ B) : Iterable[B]
>
> [use case] Builds a new collection by applying a function to all elements of
> this iterable collection.
>
> [use case]
>
> Builds a new collection by applying a function to all elements of this
> iterable collection.
>
> B : the element type of the returned collection.
>
> f  : the function to apply to each element.
>
> returns a new iterable collection resulting from applying the given function
> f to each element of this iterable collection and collecting the
> results.attributes: abstractdefinition classes: TraversableLike
> *******************
>
> As the final return value is of type Iterable[Int], there is no guarantee
> upon any Set-particularl rule (like here, uniqueness in the Set) ...
> Maybe specialization of IterableView methods for the Set case could solve
> this ?
>
> Alex
>
> 2010/12/26 Andreas Flierl
>>
>> Daniel Sobral wrote:
>> > Set(1, 2, 3).view.map(_ => 1)
>> >
>> > If I print it, check its size, or anything like that, should I expect
>> > one element or three elements?
>>
>> I would certainly expect one element, as in:
>>
>> scala> Set(1, 2, 3).view.map(_ => 1).force
>> res0: Iterable[Int] = Set(1)
>>
>> This is completely surprising to me (although I can see why it behaves the
>> way it does):
>>
>> scala> Set(1, 2, 3).view.map(_ => 1).size
>> res1: Int = 3
>>
>> as is this:
>>
>> scala> Set(1, 2, 3).view.map(_ => 1).foreach(println)
>> 1
>> 1
>> 1
>>
>> - Andreas
>

It seems *to me* that the rest of his sentence makes clear that he
means that he would trade away performance for correctness.

However, it also seems to me that, if TraversableViewLike were to
override size, foreach, and any other method that doesn't return a
collection, there would be no need to trade away either one.

On Sun, Dec 26, 2010 at 12:16 PM, Randall R Schulz wrote:
> On Saturday December 25 2010, Erik Engbrecht wrote:
>> I'll trade correctness for performance (almost) any day, and when I
>> use sets instead of lighter-weight data structures I'm pretty much
>> always concerned with correctness.  I would expect one element.
>
> The first part of that sounds like you're saying you'll trade away
> correctness in return for performance. Is that what you mean?
>
>
> Randall Schulz
>

Actually, since the default implementations work for "normal"
collections for which map never changes the number of elements, I
suppose that SetLike#view should return a specialized IterableView,
must as Alex suggested. There are other specialized IterableViews,
such as SeqView; it's surprising that there's no SetView (in 2.8.1; I
haven't looked at the latest version).

On Sun, Dec 26, 2010 at 12:29 PM, Jim Balter wrote:
> It seems *to me* that the rest of his sentence makes clear that he
> means that  he would trade away performance for correctness.
>
> However, it also seems to me that, if TraversableViewLike were to
> override size, foreach, and any other method that doesn't return a
> collection, there would be no need to trade away either one.
>
>
> On Sun, Dec 26, 2010 at 12:16 PM, Randall R Schulz wrote:
>> On Saturday December 25 2010, Erik Engbrecht wrote:
>>> I'll trade correctness for performance (almost) any day, and when I
>>> use sets instead of lighter-weight data structures I'm pretty much
>>> always concerned with correctness.  I would expect one element.
>>
>> The first part of that sounds like you're saying you'll trade away
>> correctness in return for performance. Is that what you mean?
>>
>>
>> Randall Schulz
>>
>

Whoops.  No.  I mean I'll trade performance for correctness; I prefer correctness.

On Sun, Dec 26, 2010 at 3:16 PM, Randall R Schulz <rschulz@sonic.net> wrote:

On Saturday December 25 2010, Erik Engbrecht wrote:
> I'll trade correctness for performance (almost) any day, and when I
> use sets instead of lighter-weight data structures I'm pretty much
> always concerned with correctness.  I would expect one element.

The first part of that sounds like you're saying you'll trade away
correctness in return for performance. Is that what you mean?


Randall Schulz

Views on maps behavior is a similar way:
Welcome to Scala version 2.8.1.final (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_22).Type in expressions to have them evaluated.Type :help for more information.
scala> val m = Map("ab" -> "ab", "ac" -> "ac", "ba" -> "ba")m: scala.collection.immutable.Map[java.lang.String,java.lang.String] = Map((ab,ab), (ac,ac), (ba,ba))
scala> m.map(t => (t._1.substring(0, 1), t._2))res1: scala.collection.immutable.Map[java.lang.String,java.lang.String] = Map((a,ac), (b,ba))
scala> m.view.map(t => (t._1.substring(0, 1), t._2)) res2: scala.collection.IterableView[(java.lang.String, java.lang.String),Iterable[_]] = IterableViewM(...)
scala> res2.foreach(println _)(a,ab)(a,ac)(b,ba)

On Sat, Dec 25, 2010 at 5:49 PM, Daniel Sobral <dcsobral@gmail.com> wrote:

Consider this code:
Set(1, 2, 3).view.map(_ => 1)
If I print it, check its size, or anything like that, should I expect one element or three elements? I can see that expecting one element would result in a very slow implementation, but...

--
Daniel C. Sobral

I travel to the future all the time.

In the case of Map, even force seems to be broken:

scala> val m = Map("ab" -> "ab", "ac" -> "ac", "ba" -> "ba")
m: scala.collection.immutable.Map[java.lang.String,java.lang.String] =
Map((ab,ab), (ac,ac), (ba,ba))

scala> val mvm = m.view.map{case (k, v) => k.head -> v}
mvm: scala.collection.IterableView[(Char,
java.lang.String),Iterable[_]] = IterableViewM(...)

scala> mvm.force
res0: Iterable[(Char, java.lang.String)] = List((a,ab), (a,ac), (b,ba))

List? Where's my Map?

(A related question: where are the unit tests for the library?)

On Sun, Dec 26, 2010 at 2:07 PM, Erik Engbrecht
wrote:
> Views on maps behavior is a similar way:
> Welcome to Scala version 2.8.1.final (Java HotSpot(TM) 64-Bit Server VM,
> Java 1.6.0_22).
> Type in expressions to have them evaluated.
> Type :help for more information.
> scala> val m = Map("ab" -> "ab", "ac" -> "ac", "ba" -> "ba")
> m: scala.collection.immutable.Map[java.lang.String,java.lang.String] =
> Map((ab,ab), (ac,ac), (ba,ba))
> scala> m.map(t => (t._1.substring(0, 1), t._2))
> res1: scala.collection.immutable.Map[java.lang.String,java.lang.String] =
> Map((a,ac), (b,ba))
> scala> m.view.map(t => (t._1.substring(0, 1), t._2))
> res2: scala.collection.IterableView[(java.lang.String,
> java.lang.String),Iterable[_]] = IterableViewM(...)
> scala> res2.foreach(println _)
> (a,ab)
> (a,ac)
> (b,ba)
>
> On Sat, Dec 25, 2010 at 5:49 PM, Daniel Sobral wrote:
>>
>> Consider this code:
>> Set(1, 2, 3).view.map(_ => 1)
>> If I print it, check its size, or anything like that, should I expect one
>> element or three elements? I can see that expecting one element would result
>> in a very slow implementation, but...
>>
>> --
>> Daniel C. Sobral
>>
>> I travel to the future all the time.
>
>

(A related question: where are the unit tests for the library?)

I think most of them are in:http://lampsvn.epfl.ch/trac/scala/browser/scala/trunk/test/files/run http://lampsvn.epfl.ch/trac/scala/browser/scala/trunk/test/files/jvm http://lampsvn.epfl.ch/trac/scala/browser/scala/trunk/test/files/scalacheck
I seem to recall a "help wanted" sign being posted some time ago regarding the test suite.  I can't recall if that was one of the occasions where lots of people enthusiastically volunteered their effort and then failed to come through (I've been guilty of that more than once) or whether it was just crickets.

I think neither tests nor documentation should be afterthoughts; lots
of volunteers to provide them independent of the code is a somewhat
doomed approach. As you said, correctness beats speed, and that
includes coding speed. Scala has some great test frameworks, and it
would be nice if one of them were applied to the Scala library. I
wonder whether, if I were to contribute to such an effort, it would be
accepted and would be taken up as a model, or if it would just be a
waste of my time or would commit me to make all the test updates when
functionality changes because the coders don't (again, a doomed
approach).

On Sun, Dec 26, 2010 at 3:30 PM, Erik Engbrecht
wrote:
>> (A related question: where are the unit tests for the library?)
>
> I think most of them are in:
> http://lampsvn.epfl.ch/trac/scala/browser/scala/trunk/test/files/run
> http://lampsvn.epfl.ch/trac/scala/browser/scala/trunk/test/files/jvm
> http://lampsvn.epfl.ch/trac/scala/browser/scala/trunk/test/files/scalacheck
> I seem to recall a "help wanted" sign being posted some time ago regarding
> the test suite.  I can't recall if that was one of the occasions where lots
> of people enthusiastically volunteered their effort and then failed to come
> through (I've been guilty of that more than once) or whether it was just
> crickets.
>

My experience has been that the effort required to get a change accepted is roughly proportional to the square of its scope, and anything that represents a design change is likely to be strongly resisted even if what it is replacing is fundamentally broken.  It's not an organized resistance, it's more that anything big is likely to run afoul of at least a couple people's opinions.
In order to get any wholesale changes in you not only need to be prepared to substantially exceed the quality of what it is replacing (see one of Paul's recent emails on the subject) or of existing code in general, and chances are you have to be patient and be prepared to "win friends and influence people."  As far as I can tell this is true even if you are already an active committer.
On the other hand, small patches (especially bug fixes) and properly constructed test cases (especially ones for open tickets) are generally readily accepted.
For contributions to documentation there's actually a tool: http://code.google.com/p/collaborative-scaladoc/
You can look here for what's officially being looked for in terms of assistance with testing: http://www.scala-lang.org/node/292

On Sun, Dec 26, 2010 at 8:04 PM, Jim Balter <Jim@balter.name> wrote:

I think neither tests nor documentation should be afterthoughts; lots
of volunteers to provide them independent of the code is a somewhat
doomed approach. As you said, correctness beats speed, and that
includes coding speed. Scala has some great test frameworks, and it
would be nice if one of them were applied to the Scala library. I
wonder whether, if I were to contribute to such an effort, it would be
accepted and would be taken up as a model, or if it would just be a
waste of my time or would commit me to make all the test updates when
functionality changes because the coders don't (again, a doomed
approach).

I appreciate these comments, and recognize that they're well rooted in
reality. However, while they address part of my question -- would my
changes be accepted -- they don't get to my other issue, which is
about getting other people to change how they operate. If test-driven
programming is not already a project requirement, I'm not sure that
any amount of influence by a contributor would make it one. However,
if tests expose *enough* bugs then perhaps it might.

OTOH, when it comes to thoroughly documenting every public element of
every interface, it should unequivocally be a part of every project's
requirements that every programmer is required to do so. Volunteers
contributing such documentation makes the documentation better (if
it's properly reviewed) but isn't likely to encourage programmers to
do a better job -- in fact they may do worse, counting on those
contributors to provide the documentation while they do the "hard" and
"interesting" work.

On Sun, Dec 26, 2010 at 6:22 PM, Erik Engbrecht
wrote:
> My experience has been that the effort required to get a change accepted is
> roughly proportional to the square of its scope, and anything that
> represents a design change is likely to be strongly resisted even if what it
> is replacing is fundamentally broken.  It's not an organized resistance,
> it's more that anything big is likely to run afoul of at least a couple
> people's opinions.
> In order to get any wholesale changes in you not only need to be prepared to
> substantially exceed the quality of what it is replacing (see one of Paul's
> recent emails on the subject) or of existing code in general, and chances
> are you have to be patient and be prepared to "win friends and influence
> people."  As far as I can tell this is true even if you are already an
> active committer.
> On the other hand, small patches (especially bug fixes) and properly
> constructed test cases (especially ones for open tickets) are generally
> readily accepted.
> For contributions to documentation there's actually a tool:
> http://code.google.com/p/collaborative-scaladoc/
> You can look here for what's officially being looked for in terms of
> assistance with testing:
> http://www.scala-lang.org/node/292
>
> On Sun, Dec 26, 2010 at 8:04 PM, Jim Balter wrote:
>>
>> I think neither tests nor documentation should be afterthoughts; lots
>> of volunteers to provide them independent of the code is a somewhat
>> doomed approach. As you said, correctness beats speed, and that
>> includes coding speed. Scala has some great test frameworks, and it
>> would be nice if one of them were applied to the Scala library. I
>> wonder whether, if I were to contribute to such an effort, it would be
>> accepted and would be taken up as a model, or if it would just be a
>> waste of my time or would commit me to make all the test updates when
>> functionality changes because the coders don't (again, a doomed
>> approach).
>>
>

The proferred explanations are in need of razors. The primary reason
views act the way they do is that nobody has written the set and map
views.

On Sun, Dec 26, 2010 at 11:19 PM, Paul Phillips wrote:
> The proferred explanations are in need of razors.

Mine (eventually) was that there's no SetView.

> The primary reason
> views act the way they do is that nobody has written the set and map
> views.

Until that happens, it would help a lot if there were a note in the
Scaladoc for view mentioning that the implementation is missing or
incomplete for sets and maps. The people commenting in this thread are
probably not the only ones who have encountered this and tried to
understand it. The Unix reference manual instituted a valuable
feature: a BUGS section, recognizing that implementers don't have the
resources to fix everything before releasing code, and that some
things are too expensive to do at all (fixing some "bugs" is
equivalent to solving the Halting Problem). Such documentation is
knowledge transfer: implementers have it, and users can benefit from
it.

And, because these threads tend to focus on things gone wrong, let me
say this: I love Scala and I greatly appreciate all the hard work and
downright brilliance that the designers and implementers have put into
it.

On Mon, Dec 27, 2010 at 9:21 AM, Jim Balter wrote:
> On Sun, Dec 26, 2010 at 11:19 PM, Paul Phillips wrote:
>> The proferred explanations are in need of razors.
>
> Mine (eventually) was that there's no SetView.
>
>> The primary reason
>> views act the way they do is that nobody has written the set and map
>> views.
>
> Until that happens, it would help a lot if there were a note in the
> Scaladoc for view mentioning that the implementation is missing or
> incomplete for sets and maps.

I don't think it was intentional.

Ismael

On Dec 27, 2010, at 3:34 AM, Ismael Juma wrote:

> On Mon, Dec 27, 2010 at 9:21 AM, Jim Balter wrote:
>> On Sun, Dec 26, 2010 at 11:19 PM, Paul Phillips wrote:
>>> The proferred explanations are in need of razors.
>>
>> Mine (eventually) was that there's no SetView.
>>
>>> The primary reason
>>> views act the way they do is that nobody has written the set and map
>>> views.
>>
>> Until that happens, it would help a lot if there were a note in the
>> Scaladoc for view mentioning that the implementation is missing or
>> incomplete for sets and maps.
>
> I don't think it was intentional.
>
> Ismael

That's not at all the impression I got from Paul's comment ... he said that nobody has written the set and map views, not that nobody had realized they needed to be written, in which case the comment about "razors" would seem rather inappropriate. In any case, whether it was "intentional" not, it still seems to me that such a "bug" comment should be added to the description of view until the code is written.

On 27 December 2010 13:46, Jim Balter <jqbalter@gmail.com> wrote:

On Dec 27, 2010, at 3:34 AM, Ismael Juma <mlists@juma.me.uk> wrote:

> On Mon, Dec 27, 2010 at 9:21 AM, Jim Balter <Jim@balter.name> wrote:
>> On Sun, Dec 26, 2010 at 11:19 PM, Paul Phillips <paulp@improving.org> wrote:
>>> The proferred explanations are in need of razors.
>>
>> Mine (eventually) was that there's no SetView.
>>
>>>  The primary reason
>>> views act the way they do is that nobody has written the set and map
>>> views.
>>
>> Until that happens, it would help a lot if there were a note in the
>> Scaladoc for view mentioning that the implementation is missing or
>> incomplete for sets and maps.
>
> I don't think it was intentional.
>
> Ismael

That's not at all the impression I got from Paul's comment ... he said that nobody has written the set and map views, not that nobody had realized they needed to be written, in which case the comment about "razors" would seem rather inappropriate. In any case, whether it was "intentional" not, it still seems to me that such a "bug" comment should be added to the description of view until the code is written.

Paul was referring to razors owned by a certain Mr Occam, giving the explanation that "these specialised views don't exist because they haven't been written yet"
Seems totally appropriate to me...

--
Kevin Wright

gtalk / msn : kev.lee.wright@gmail.comkev.lee.wright@gmail.commail: kevin.wright@scalatechnology.com
vibe / skype: kev.lee.wright
twitter: @thecoda

On Monday December 27 2010, Kevin Wright wrote:
> ...
>
> Paul was referring to razors owned by a certain Mr Occam, ...

_Father_ William of Ockham (spellings have changed over the centuries).
He was a Franciscan Friar. I called him Father Bill.

> Seems totally appropriate to me...

RRS

On Mon, Dec 27, 2010 at 1:46 PM, Jim Balter wrote:
> That's not at all the impression I got from Paul's comment ... he said that nobody has written the set and map views,
> not that nobody had realized they needed to be written

After this thread, it's clear that they're missing. I don't think Paul
was saying that it was known all along that they were missing.
Typically an issue is filed in Trac for things like this and I don't
remember seeing one.

Best,
Ismael

On 27 December 2010 14:29, Randall R Schulz <rschulz@sonic.net> wrote:

On Monday December 27 2010, Kevin Wright wrote:
> ...
>
> Paul was referring to razors owned by a certain Mr Occam, ...

_Father_ William of Ockham (spellings have changed over the centuries).
He was a Franciscan Friar. I called him Father Bill.

Well, I stand corrected!  Father Bill it is...
 

> Seems totally appropriate to me...



RRS

--
Kevin Wright

gtalk / msn : kev.lee.wright@gmail.comkev.lee.wright@gmail.commail: kevin.wright@scalatechnology.com
vibe / skype: kev.lee.wright
twitter: @thecoda

Tickets created:http://lampsvn.epfl.ch/trac/scala/ticket/4116http://lampsvn.epfl.ch/trac/scala/ticket/4117

On Mon, Dec 27, 2010 at 9:39 AM, Ismael Juma <mlists@juma.me.uk> wrote:

On Mon, Dec 27, 2010 at 1:46 PM, Jim Balter <jqbalter@gmail.com> wrote:
> That's not at all the impression I got from Paul's comment ... he said that nobody has written the set and map views,
> not that nobody had realized they needed to be written

After this thread, it's clear that they're missing. I don't think Paul
was saying that it was known all along that they were missing.
Typically an issue is filed in Trac for things like this and I don't
remember seeing one.

Best,
Ismael

On Mon, Dec 27, 2010 at 6:07 AM, Kevin Wright wrote:

> Paul was referring to razors owned by a certain Mr Occam

I know what he was referring to.

> giving the
> explanation that "these specialised views don't exist because they haven't
> been written yet"
> Seems totally appropriate to me...

Well, we all have our opinions. But there are three different classes
of explanation at hand: 1) the supposedly more complex ones that try
to explain why it works as it does on the assumption that it is coded
as intended; 2) the implementers didn't finish coding it and were
aware of what was required; 3) the implementers unintentionally
omitted some code required for it to work properly. OR can't be used
to choose among these; that takes inside knowledge.