Views and modularity

[Eric Tanter]

Hi there,

Both "Programming in Scala (2nd ed)" and "Scala for the Impatient" use the same example (modulo irrelevant details) to motivate the use of views:

Given a collection, say v: Vector[Int]

v map (_ + 1) map (_ * 2)

We can use views to fuse the two transformations and avoid the intermediate result:

(v.view map (_ + 1) map (_ * 2)).force

Then, both books note that the example is a bit artificial, because if we know both functions we can simply call map directly with a composed function.

PiS: "But quite often, successive transformations of a data structure are done in different program modules."

SftI: "However, if a collection is processed in different parts of a program, you can pass along a view that accumulates the modifications"


So I'm trying to write that same example in a "more real" setting in which the two transformations are indeed separate functions, developed independently of the decision to use a view. Say:

def f1(x: Seq[Int]) = x map (_ + 1)
def f2(x: Seq[Int]) = x map (_ * 2)

Now we can write either:

val res = f2(f1(v))

or:

val res = f2(f1(v.view)).force

All seems good, except for the fact that the latter code does not type check: the result of `f2(f1(v.view))' has static type Seq[Int], which does not understand `force'.

This leads to two questions:

1) There seems to be no other way than using a coercion of some sort.

f2(f1(v.view)) match {
case x : SeqView[Int, Vector[_]] => x.force
}

or

f2(f1(v.view)).asInstanceOf[SeqView[Int,Vector[_]]].force

both work, but are fairly heavyweight/ugly.

Any better suggestions?

A fully polymorphic forcer would be better to avoid having writing specific coercions each time...


2) But more simply: why isn't `force' defined on all sequences, assuming it does nothing (evaluates to `this') in all strict sequences?

I'm not sure what the problem would be with such a design, and it would clearly solve the problem above, making it really convenient to apply views in this modular multiple-tranformations setting.

As a point of comparison, in Racket `(force v)' forces the evaluation of `v' if it is a promise (and keeps it for future `force's), or just returns `v' if `v' is not a promise.

Thanks!

-- Éric

[Simon Schäfer]

On 09/08/2013 01:06 AM, Eric Tanter wrote:
> 2) But more simply: why isn't `force' defined on all sequences, assuming it does nothing (evaluates to `this') in all strict sequences?

Maybe because views are crap. Use Stream or Iterator instead.

[Eric Tanter]

How would Streams or Iterators help in the motivating example?

(if you want to play the game, you can't change the signature of f1 and f2 -- which are perfectly reasonable to start with)

-- Éric

> --
> You received this message because you are subscribed to the Google Groups "scala-language" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to scala-languag...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.

[Simon Schäfer]

On 09/08/2013 02:47 AM, Eric Tanter wrote:
> How would Streams or Iterators help in the motivating example?
>
> (if you want to play the game, you can't change the signature of f1 and f2 -- which are perfectly reasonable to start with)

If you can't change the signature of your methods, then just use i.e.
.toList instead of .force to force evaluation.

[Eric Tanter]

All the toX methods are forcing evaluation, indeed. So that solves the motivating example.

Thanks!

-- Éric

[Vlad Patryshev]

Simon,

This is interesting (not that I disagree); can you elaborate? I've been always debating whether to use them.

Thanks,
-Vlad

--
You received this message because you are subscribed to the Google Groups "scala-language" group.

To unsubscribe from this group and stop receiving emails from it, send an email to scala-language+unsubscribe@googlegroups.com.

[Roman Janusz]

This issue has a discussion about this: https://issues.scala-lang.org/browse/SI-4332
One of Paul's comments is particularly explicit about overall state of views.

W dniu niedziela, 8 września 2013 04:57:33 UTC+2 użytkownik Vlad Patryshev napisał:

Simon,

This is interesting (not that I disagree); can you elaborate? I've been always debating whether to use them.

Thanks,
-Vlad

On Sat, Sep 7, 2013 at 5:35 PM, Simon Schäfer <ma...@antoras.de> wrote:

On 09/08/2013 01:06 AM, Eric Tanter wrote:

2) But more simply: why isn't `force' defined on all sequences, assuming it does nothing (evaluates to `this') in all strict sequences?

Maybe because views are crap. Use Stream or Iterator instead.

--
You received this message because you are subscribed to the Google Groups "scala-language" group.

To unsubscribe from this group and stop receiving emails from it, send an email to scala-languag...@googlegroups.com.

[Simon Schäfer]

On 09/08/2013 04:00 AM, Eric Tanter wrote:
> All the toX methods are forcing evaluation, indeed. So that solves the motivating example.

No, not all toX m

[Simon Schäfer]

Sorry for the broken message. Original:

No, not all toX methods force evaluation. toSeq for example lets the
view as it is, but there is to[Seq].

[Eric Tanter]

Thanks Simon for the correction.

And thanks Roman for the pointer to the discussion about views. Very informative. There was a pointer to another thread in there (https://groups.google.com/forum/#!topic/scala-debate/M8s8FmASL8Y) that goes at more length about the issues with views and what to do about it.

I hadn't realized views were such a controversial feature, at least in their current design/implementation. So my original question was just scratching the surface.

Since the protagonists of these past discussions are out there, what happened to the idea of moving views out of the standard library?

-- Éric


On Sep 8, 2013, at 8:00 AM, Simon Schäfer <ma...@antoras.de> wrote:

[Paul Phillips]

I decided to stop wasting my effort on scala, that's what happened. Views are yet another fine example of why I'm moving on. 

[Oliver Ruebenacker]

     Hello,

On Sun, Sep 8, 2013 at 11:10 AM, Paul Phillips <pa...@improving.org> wrote:

I decided to stop wasting my effort on scala, that's what happened. Views are yet another fine example of why I'm moving on. 

  What happened?

     Best,

     Oliver
 

--

Oliver Ruebenacker
IT Project Lead at PanGenX (http://www.pangenx.com)

Be always grateful, but never satisfied.

[Alex Cruise]

FWIW, I think Java 8's Streams, which are essentially the same as our views, are going to be a big deal.  One way they dodged our bullet is to make it explicit that some operations (like foreach) are "terminal", and others like (like map, filter) are "non-terminal". 

A Stream is not a List, but you can get from collection to stream and back explicitly.  e.g. myList.stream().filter(p).map(f).collect(Collectors.toList());

Yes, it's a bit ugly, but it looks like they will actually deliver working stream fusion in a few months. 

-0xe1a

[Paul Phillips]

On Mon, Sep 9, 2013 at 11:43 AM, Alex Cruise <al...@cluonflux.com> wrote:

FWIW, I think Java 8's Streams, which are essentially the same as our views [...] it looks like they will actually deliver working stream fusion in a few months.

What is your vantage such that they appear essentially the same? Are you Felix Baumgartner?

[Alex Cruise]

Just to make sure we're on the same sportsmetaphor, I'm talking about JDK8's java.util.stream.Stream, not java.io.{Input,Output}Stream. :)

For me at least, the main purpose of views is that they let you apply a chain of map/filter/flatMap/etc. without having to build intermediate collections that will be instant garbage.  If there's some other reason to use Scala views, I'd love to hear it. In any case, the java.util.stream package summary is pretty good, and shows (to me at least) that they're intended for the same kinds of use cases.

-0xe1a

[Paul Phillips]

On Mon, Sep 9, 2013 at 2:33 PM, Alex Cruise <al...@cluonflux.com> wrote:

intended for the same kinds of use cases.

I don't doubt that they're INTENDED for the same kinds of use cases, but intentions only take you so far.

There is no other reason to use scala views; there is not even that reason.

[Jason Zaugg]

What we've done a really bad job at documenting is that fusing those sort of operations together can be done with much less fragile machinery via `xs.iterator.map(f).map(g).toList`.

Views try to capture a richer set of operations, so `xs.view.drop(1).reverse` captures those operations until `force` or `toList` is called. The intermediate data structures are pretty hairy.

Furthermore, it's hard to reason about what properties of the original collection should be preserved through the view. 

Compare:

  scala> var x = 0

  x: Int = 0

  scala> Set(1, 2).map(x => 1).map(_ => {x += 1; x})

  res14: scala.collection.immutable.Set[Int] = Set(1)

With:

  scala> var x = 0

  x: Int = 0

  scala> Set(1, 2).view.map(x => 1).map(_ => {x += 1; x}).force

  res15: Iterable[Int] = Set(1, 2)

Thats a bug, IMO, and shows that you can't fuse operations for sets in general. (You can if you know the functions satisfy `f(x) == f(y) if x == y`). So making people convert to an iterator (or stream, or java.Stream) is actually a good means to be explicit about what sort of collection properties you have during the intermediate steps.

The best way forward for views would be:

  1) people using them try converting to `.iterator` where possible

  2) where not possible, let us know what your use case is

  3) accomodate those use cases in a new, simpler view library

  4) we deprecate the views in the collections, pointing people to said new library, and possibly distributing it as a module of Scala.

-jason

[Paul Phillips]

On Mon, Sep 9, 2013 at 2:59 PM, Jason Zaugg <jza...@gmail.com> wrote:

Thats a bug, IMO, and shows that you can't fuse operations for sets in general.

As a side note, "map" shouldn't even exist on sets. It is a never-ending parade of invisible bugs. It should be an invariant of "map" that you get the same number of things out that you put in. If someone wanted some funky maplike thing which may or may not make pieces of the resulting collection vanish into the ether, they should call it funkyMap or setMap or something. Leave poor map alone.

I will always fondly remember the bug where Set's hashCode was calculated something like 

  xs.map(_.##).sum

Hey, where are my sets disappearing to, sometimes?

[Simon Schäfer]

In any case, the java.util.stream package summary is pretty good, and shows (to me at least) that they're intended for the same kinds of use cases.

They do not address the same use cases. jus.Stream are highly mutable, more like an iterator than a view.

[Kevin Wright]

I'm sure that's been proposed multiple times over the years. It would be good if now is the time it finally happens, given recent pushes towards cleaning up Tech debt.

Speaking as someone who was playing with Scala+android+proguard before it was even considered possible, I can also testify that this would clean out a *lot* of classloading baggage as well. What's not to like?

> -jason

[Jason Zaugg]

On Tue, Sep 10, 2013 at 12:18 AM, Paul Phillips <pa...@improving.org> wrote:

On Mon, Sep 9, 2013 at 2:59 PM, Jason Zaugg <jza...@gmail.com> wrote:

Thats a bug, IMO, and shows that you can't fuse operations for sets in general.

As a side note, "map" shouldn't even exist on sets. It is a never-ending parade of invisible bugs. It should be an invariant of "map" that you get the same number of things out that you put in. If someone wanted some funky maplike thing which may or may not make pieces of the resulting collection vanish into the ether, they should call it funkyMap or setMap or something. Leave poor map alone.

I've logged many an hour tracking down nasty bugs that stemmed from the highly related:

scala> List(1 -> 2, 1 -> 3).toMap

res16: scala.collection.immutable.Map[Int,Int] = Map(1 -> 3)

-jason

[Kevin Wright]

On 9 Sep 2013 23:18, "Paul Phillips" <pa...@improving.org> wrote:
>
>
> On Mon, Sep 9, 2013 at 2:59 PM, Jason Zaugg <jza...@gmail.com> wrote:
>>
>> Thats a bug, IMO, and shows that you can't fuse operations for sets in general.
>
>
> As a side note, "map" shouldn't even exist on sets. It is a never-ending parade of invisible bugs. It should be an invariant of "map" that you get the same number of things out that you put in. If someone wanted some funky maplike thing which may or may not make pieces of the resulting collection vanish into the ether, they should call it funkyMap or setMap or something. Leave poor map alone.
>

The same can also be said of the Map type (& derivatives). So this particular rabbit hole goes a whole lot deeper...

> I will always fondly remember the bug where Set's hashCode was calculated something like 
>
>   xs.map(_.##).sum
>
> Hey, where are my sets disappearing to, sometimes?
>

[Paul Phillips]

On Mon, Sep 9, 2013 at 3:29 PM, Jason Zaugg <jza...@gmail.com> wrote:

I've logged many an hour tracking down nasty bugs that stemmed from the highly related:

scala> List(1 -> 2, 1 -> 3).toMap

res16: scala.collection.immutable.Map[Int,Int] = Map(1 -> 3)

One of the things I observed when I redesigned collections according to my own sensibilities was that there is no call for "Map" be a peer to Sets and Sequences. A Map is a Set with an apply method. I found this to be better in every way. There's no reason tuples need to pollute the type parameter hierarchy, for instance (among many non-orthogonalities Maps bring into the collections with their two type parameters.) You can work with the keys - we know how to get from keys to values.

[Bardur Arantsson]

On 2013-09-10 00:26, Simon Sch�fer wrote:
>
>> In any case, the java.util.stream package summary

>> <http://download.java.net/jdk8/docs/api/java/util/stream/package-summary.html>

>> is pretty good, and shows (to me at least) that they're intended for
>> the same kinds of use cases.
> They do not address the same use cases. jus.Stream are highly mutable,
> more like an iterator than a view.
>

"Be immutable" is not a use case.

[√iktor Ҡlang]

No, but it might be a reuse case

On Sep 10, 2013 4:01 AM, "Bardur Arantsson" <sp...@scientician.net> wrote:

[martin odersky]

On Mon, Sep 9, 2013 at 11:59 PM, Jason Zaugg <jza...@gmail.com> wrote:

On Mon, Sep 9, 2013 at 11:33 PM, Alex Cruise <al...@cluonflux.com> wrote:

On Mon, Sep 9, 2013 at 12:02 PM, Paul Phillips <pa...@improving.org> wrote:

On Mon, Sep 9, 2013 at 11:43 AM, Alex Cruise <al...@cluonflux.com> wrote:

FWIW, I think Java 8's Streams, which are essentially the same as our views [...] it looks like they will actually deliver working stream fusion in a few months.

What is your vantage such that they appear essentially the same? Are you Felix Baumgartner?

Just to make sure we're on the same sportsmetaphor, I'm talking about JDK8's java.util.stream.Stream, not java.io.{Input,Output}Stream. :)

For me at least, the main purpose of views is that they let you apply a chain of map/filter/flatMap/etc. without having to build intermediate collections that will be instant garbage.  If there's some other reason to use Scala views, I'd love to hear it. In any case, the java.util.stream package summary is pretty good, and shows (to me at least) that they're intended for the same kinds of use cases.

What we've done a really bad job at documenting is that fusing those sort of operations together can be done with much less fragile machinery via `xs.iterator.map(f).map(g).toList`.

Views try to capture a richer set of operations, so `xs.view.drop(1).reverse` captures those operations until `force` or `toList` is called. The intermediate data structures are pretty hairy.

Furthermore, it's hard to reason about what properties of the original collection should be preserved through the view. 

Compare:

  scala> var x = 0

  x: Int = 0

  scala> Set(1, 2).map(x => 1).map(_ => {x += 1; x})

  res14: scala.collection.immutable.Set[Int] = Set(1)

With:

  scala> var x = 0

  x: Int = 0

  scala> Set(1, 2).view.map(x => 1).map(_ => {x += 1; x}).force

  res15: Iterable[Int] = Set(1, 2)

Thats a bug, IMO, and shows that you can't fuse operations for sets in general. (You can if you know the functions satisfy `f(x) == f(y) if x == y`). So making people convert to an iterator (or stream, or java.Stream) is actually a good means to be explicit about what sort of collection properties you have during the intermediate steps.

I fail to see how it is a bug. Views _prescribe_ that operations should be fused. They _demand_ a change of order of operations. If you mix change of order of operations with side effects you will get different results. 

 

The best way forward for views would be:

  1) people using them try converting to `.iterator` where possible

  2) where not possible, let us know what your use case is

  3) accomodate those use cases in a new, simpler view library

  4) we deprecate the views in the collections, pointing people to said new library, and possibly distributing it as a module of Scala.

Note that this is the exact opposite of what Java 8 is doing. Java 8 makes collections lazy (views) by default. We seem to say that we only want strict collections. Can someone clarify the reasons why strict collections are better for Scala whereas lazy ones are better for Java? If anything, laziness plays badly with state (as you showed above), so that should make views more attractive for a more functional oriented language like Scala than a more imperative one like Java. Something does not make sense here.

It's not that we should leave things as they are. Views are (1) underdocumented (2) overly complicated in their implementation and (3) have too many side effect on other parts of the collections. In particular it would probably be better if forcing was always to an explicit type. So you'd have to write ".toList", ".toSet", ".toIndexedSet" instead of the generic "force" (again following Java 8 here). 

Going to iterators instead of views does not always work. For instance, consider, on an indexed seq:

  xs.view.slice(x, y).map(f)

You can do 

  xs.iterator.slice(x, y).map(f)

but then slice takes linear instead of constant time. You can also do

  xs.slice(x, y).iterator.map(f)

but that creates an intermediate data structure.

Cheers

 - Martin

 

-jason

--
You received this message because you are subscribed to the Google Groups "scala-language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-languag...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

--

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

[martin odersky]

I disagree completely. There's nothing more natural than mapping a function over a set. If you want to maintain same length you need a multi-set, not a set. One could argue that it would be nice to have better support for multi-sets in the Scala library. But arguing that map should not exist on sets is ... weird.

Cheers

 - Martin

-- 

You received this message because you are subscribed to the Google Groups "scala-language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-languag...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

--

[Bardur Arantsson]

On 2013-09-10 10:16, martin odersky wrote:
> Going to iterators instead of views does not always work. For instance,
> consider, on an indexed seq:
>
> xs.view.slice(x, y).map(f)
>
> You can do
>
> xs.iterator.slice(x, y).map(f)
>
> but then slice takes linear instead of constant time. You can also do
>
> xs.slice(x, y).iterator.map(f)
>
> but that creates an intermediate data structure.
>

AFAICT, this problem only occurs because Java/Scala's iterator concept
is quite anemic.

It would be solved quite simply by the addition of the concept of
random-access iterators with constant time "advance-n-steps" as seen in
e.g. C++. The details are, of course, left as an exercise for the
interested reader.

(That's not to say that the iterator concept itself is necessarily all
that good. For example, there's was some movement in the C++ community
towards using ranges which are a sort of generalization of slices
involving iterator *pairs*. However, this was quite intimately tied to
the design of iterators in C++ and I'm not sure how much sense it would
make in the JVM world.)

Regards,

[Bardur Arantsson]

On 2013-09-10 10:47, Bardur Arantsson wrote:
> (That's not to say that the iterator concept itself is necessarily all
> that good. For example, there's was some movement in the C++ community
> towards using ranges which are a sort of generalization of slices
> involving iterator *pairs*. However, this was quite intimately tied to
> the design of iterators in C++ and I'm not sure how much sense it would
> make in the JVM world.)

Oh, and here's a link to an article descibing

http://www.informit.com/articles/printerfriendly.aspx?p=1407357

this in some detail.

Regards,

[Francois]

On 10/09/2013 10:16, martin odersky wrote:
>
> [....]

>
> Note that this is the exact opposite of what Java 8 is doing. Java 8
> makes collections lazy (views) by default. We seem to say that we only
> want strict collections. Can someone clarify the reasons why strict
> collections are better for Scala whereas lazy ones are better for
> Java? If anything, laziness plays badly with state (as you showed
> above), so that should make views more attractive for a more
> functional oriented language like Scala than a more imperative one
> like Java. Something does not make sense here.
>
> It's not that we should leave things as they are. Views are (1)
> underdocumented (2) overly complicated in their implementation and (3)
> have too many side effect on other parts of the collections. In
> particular it would probably be better if forcing was always to an
> explicit type. So you'd have to write ".toList", ".toSet",
> ".toIndexedSet" instead of the generic "force" (again following Java 8
> here).
>

It's a problem of default behaviour, choice, risk and alternatives.


As of today, I don't know anybody who 1/ tried view for production
project 2/ and keeped them, even if the encounter strange and nasty,
subtil bugs on the way, 3/ with quick and robust patch deliverd by Scala
dev.

Now, there is all these subtils (or less subtils) bug because a lot less
people used view, and view bugs seems to be less prioritaries or harder
to correct. At least, from a user point of view, view means "to much
risk for the bucks".

So, perhaps if ALL scala collection were lazy, with ALL user forced to
use them, and ALL bug on lazy collection being a bug in Scala collection
with no alternative, that would work. But with the actuall state of
things, I don't see who would pay for the price of using view (either
user or Scala developer). Even less if iterators allow to manage most of
the use cases with much less risks.

Here, the difference with Java is clear: in Java, if you want to take
advantage of functionnal programmation on collection (and of course, you
do - hell, it's one of the best selling point for Scala), you will have
to use lazy structure, no alternative. So bugs will be find and ironned,
eventually.

To sum up: view are buggy because lazy structure are hard, they are not
well tested because alternative (standard collection) are better and
less risky.
I don't see what would make it change without massive political
implication of Scala product owner (well, the team choosing what Scala
should look like in the futur).

Cheers,

--
Francois ARMAND
http://rudder-project.org
http://www.normation.com

[Johannes Rudolph]

On Tue, Sep 10, 2013 at 10:18 AM, martin odersky <martin....@epfl.ch> wrote:

On Tue, Sep 10, 2013 at 12:18 AM, Paul Phillips <pa...@improving.org> wrote:

On Mon, Sep 9, 2013 at 2:59 PM, Jason Zaugg <jza...@gmail.com> wrote:

Thats a bug, IMO, and shows that you can't fuse operations for sets in general.

As a side note, "map" shouldn't even exist on sets. It is a never-ending parade of invisible bugs. It should be an invariant of "map" that you get the same number of things out that you put in. If someone wanted some funky maplike thing which may or may not make pieces of the resulting collection vanish into the ether, they should call it funkyMap or setMap or something. Leave poor map alone.

I will always fondly remember the bug where Set's hashCode was calculated something like 

  xs.map(_.##).sum

 

Hey, where are my sets disappearing to, sometimes?

I disagree completely. There's nothing more natural than mapping a function over a set. If you want to maintain same length you need a multi-set, not a set. One could argue that it would be nice to have better support for multi-sets in the Scala library. But arguing that map should not exist on sets is ... weird.

In practice it isn't weird at all and fits into this thread perfectly. There are those little things in the Scala collections library where you even after years cannot say with confidence why a certain operation has a certain effect. Of course, the above semantic of mapping over Maps or Sets is one possible solution. That's not the problem. The problem is that there's at least one other perfectly reasonable outcome which would be an intuitively correct choice in some cases. However, when using map you cannot confidently predict which one is chosen because there's no high-level rule to apply that would work in all cases. To be sure you then resort be being explicit about what you expect which is often made harder than necessary because you suddenly have to understand all of the CanBuildFrom typing rules and logic at once to make the choice.

For views the problem is that under abstraction you also suddenly cannot predict the evaluation mode of methods of collections you get passed into a method. Apart from that over time there were so many bugs that you could never know if a view is still a view after applying an operator or if an operator forces the collection at some points.

--
Johannes

-----------------------------------------------
Johannes Rudolph
http://virtual-void.net

[martin odersky]

On Tue, Sep 10, 2013 at 11:44 AM, Johannes Rudolph <johannes...@googlemail.com> wrote:

On Tue, Sep 10, 2013 at 10:18 AM, martin odersky <martin....@epfl.ch> wrote:

On Tue, Sep 10, 2013 at 12:18 AM, Paul Phillips <pa...@improving.org> wrote:

On Mon, Sep 9, 2013 at 2:59 PM, Jason Zaugg <jza...@gmail.com> wrote:

Thats a bug, IMO, and shows that you can't fuse operations for sets in general.

As a side note, "map" shouldn't even exist on sets. It is a never-ending parade of invisible bugs. It should be an invariant of "map" that you get the same number of things out that you put in. If someone wanted some funky maplike thing which may or may not make pieces of the resulting collection vanish into the ether, they should call it funkyMap or setMap or something. Leave poor map alone.

I will always fondly remember the bug where Set's hashCode was calculated something like 

  xs.map(_.##).sum

 

Hey, where are my sets disappearing to, sometimes?

I disagree completely. There's nothing more natural than mapping a function over a set. If you want to maintain same length you need a multi-set, not a set. One could argue that it would be nice to have better support for multi-sets in the Scala library. But arguing that map should not exist on sets is ... weird.

In practice it isn't weird at all and fits into this thread perfectly. There are those little things in the Scala collections library where you even after years cannot say with confidence why a certain operation has a certain effect. Of course, the above semantic of mapping over Maps or Sets is one possible solution. That's not the problem. The problem is that there's at least one other perfectly reasonable outcome which would be an intuitively correct choice in some cases. However, when using map you cannot confidently predict which one is chosen because there's no high-level rule to apply that would work in all cases. To be sure you then resort be being explicit about what you expect which is often made harder than necessary because you suddenly have to understand all of the CanBuildFrom typing rules and logic at once to make the choice.

Just to be clear: If we pick the other "reasonable outcome", then

 - for expressions do not work for sets

 - Slick or ScalaQuery needs to be abolished because relations are sets

If we follow Paul's guidelines that map is not allowed to change the number of elements in a collection, then random number generators are out as well, so ScalaQuery becomes illegal.

I am not usually the one who rubs "monad!" into people's faces, but, seriously? 

 - Martin

[martin odersky]

I agree that views do present more pitfalls to get things wrong - that's the price you pay for reducing storage requirements. And I also agree that this creates a vicious circle of under-use and under-maintenance. 

But now that Java 8 comes out, the large majority of programmers will expect views as the standard because that's what they know from Java 8. So I expect that vicious cycle to be broken if we decide to fix views rather than abolish them.

Cheers

 - Martin

 

Here, the difference with Java is clear: in Java, if you want to take
advantage of functionnal programmation on collection (and of course, you
do - hell, it's one of the best selling point for Scala), you will have
to use lazy structure, no alternative. So bugs will be find and ironned,
eventually.

To sum up: view are buggy because lazy structure are hard, they are not
well tested because alternative (standard collection) are better and
less risky.
I don't see what would make it change without massive political
implication of Scala product owner (well, the team choosing what Scala
should look like  in the futur).

Cheers,

--
Francois ARMAND
http://rudder-project.org
http://www.normation.com

--
You received this message because you are subscribed to the Google Groups "scala-language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-languag...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Johannes Rudolph]

On Tue, Sep 10, 2013 at 10:16 AM, martin odersky <martin....@epfl.ch> wrote:

Going to iterators instead of views does not always work. For instance, consider, on an indexed seq:

  xs.view.slice(x, y).map(f)

You can do 

  xs.iterator.slice(x, y).map(f)

 

but then slice takes linear instead of constant time.

 

Why? If an iterator made from IndexedSeq offers a slice method why shouldn't you expect it to run in constant time ? Actually, from looking at scaladoc, `Iterator.slice` is defined in terms of drop/take which make no such claim. For me this discussion is a sign that we are still missing some guidelines about how subtyping (and dynamic dispatch) and adhoc polymorphism would play together in a way that is obvious enough that you aren't surprised in so many cases. 

Note that this is the exact opposite of what Java 8 is doing. Java 8 makes collections lazy (views) by default. We seem to say that we only want strict collections. Can someone clarify the reasons why strict collections are better for Scala whereas lazy ones are better for Java? If anything, laziness plays badly with state (as you showed above), so that should make views more attractive for a more functional oriented language like Scala than a more imperative one like Java.

I don't know if you are suggesting to make collection lazy by default but that's something I would agree to in general. Maybe it would mean that you cannot specify the evaluation mode for many of those methods but for those ones which always force the collection but maybe that would be more honest than the current way where strict and lazily evaluated collections share the same types but different expectations.

[Johannes Rudolph]

On Tue, Sep 10, 2013 at 11:56 AM, martin odersky <martin....@epfl.ch> wrote:

On Tue, Sep 10, 2013 at 11:44 AM, Johannes Rudolph <johannes...@googlemail.com> wrote:

On Tue, Sep 10, 2013 at 10:18 AM, martin odersky <martin....@epfl.ch> wrote:

On Tue, Sep 10, 2013 at 12:18 AM, Paul Phillips <pa...@improving.org> wrote:

On Mon, Sep 9, 2013 at 2:59 PM, Jason Zaugg <jza...@gmail.com> wrote:

Thats a bug, IMO, and shows that you can't fuse operations for sets in general.

As a side note, "map" shouldn't even exist on sets. It is a never-ending parade of invisible bugs. It should be an invariant of "map" that you get the same number of things out that you put in. If someone wanted some funky maplike thing which may or may not make pieces of the resulting collection vanish into the ether, they should call it funkyMap or setMap or something. Leave poor map alone.

I will always fondly remember the bug where Set's hashCode was calculated something like 

  xs.map(_.##).sum

 

Hey, where are my sets disappearing to, sometimes?

I disagree completely. There's nothing more natural than mapping a function over a set. If you want to maintain same length you need a multi-set, not a set. One could argue that it would be nice to have better support for multi-sets in the Scala library. But arguing that map should not exist on sets is ... weird.

In practice it isn't weird at all and fits into this thread perfectly. There are those little things in the Scala collections library where you even after years cannot say with confidence why a certain operation has a certain effect. Of course, the above semantic of mapping over Maps or Sets is one possible solution. That's not the problem. The problem is that there's at least one other perfectly reasonable outcome which would be an intuitively correct choice in some cases. However, when using map you cannot confidently predict which one is chosen because there's no high-level rule to apply that would work in all cases. To be sure you then resort be being explicit about what you expect which is often made harder than necessary because you suddenly have to understand all of the CanBuildFrom typing rules and logic at once to make the choice.

Just to be clear: If we pick the other "reasonable outcome", then

I'm for being explicit not for picking one of two similarly reasonable outcomes. If there are contexts where one monad should be chosen over the other one then, I'd guess, there are ways to do that. 

 

[Francois]

On 10/09/2013 12:10, martin odersky wrote:

On Tue, Sep 10, 2013 at 11:27 AM, Francois <fan...@gmail.com> wrote:

On 10/09/2013 10:16, martin odersky wrote:

[...]

So, perhaps if ALL scala collection were lazy, with ALL user forced to
use them, and ALL bug on lazy collection being a bug in Scala collection
with no alternative, that would work. But with the actuall state of
things, I don't see who would pay for the price of using view (either
user or Scala developer). Even less if iterators allow to manage most of
the use cases with much less risks.

I agree that views do present more pitfalls to get things wrong - that's the price you pay for reducing storage requirements. And I also agree that this creates a vicious circle of under-use and under-maintenance. 

But now that Java 8 comes out, the large majority of programmers will expect views as the standard because that's what they know from Java 8. So I expect that vicious cycle to be broken if we decide to fix views rather than abolish them.

Cheers

 - Martin

I don't think "lazy collection for Scala is a bad thing". I would be the first to love to be able to write operation on collection without having to care about garbage collection, short living object, smart and efficient operation composition, etc.

But making users and Scala developers switch from a rather working and complete existing collection framework to a new one (even a 10 times better one) will requires a lot of efforts from Typesafe (?) if the choice to just keep using the old, proven solution exists. That's part of the political decision I was talking about..

[martin odersky]

On Tue, Sep 10, 2013 at 12:11 PM, Johannes Rudolph <johannes...@googlemail.com> wrote:

On Tue, Sep 10, 2013 at 10:16 AM, martin odersky <martin....@epfl.ch> wrote:

Going to iterators instead of views does not always work. For instance, consider, on an indexed seq:

  xs.view.slice(x, y).map(f)

You can do 

  xs.iterator.slice(x, y).map(f)

 

but then slice takes linear instead of constant time.

 

Why? If an iterator made from IndexedSeq offers a slice method why shouldn't you expect it to run in constant time ? Actually, from looking at scaladoc, `Iterator.slice` is defined in terms of drop/take which make no such claim. For me this discussion is a sign that we are still missing some guidelines about how subtyping (and dynamic dispatch) and adhoc polymorphism would play together in a way that is obvious enough that you aren't surprised in so many cases.

Of course you could do that. But in the end you might end up with the same implementation mess as views (not saying you will, but generally one can say little without actually trying things out). Another observation is that views are safer and more modular than iterators. For instance:

  val v = xs.view

  val ys = v.slice(x, y).map(f).toList

  val zs = v.map(f).map(g).toList

With iterators you have the unfortunate side effects that zs always starts at index y!

So I think throwing out functional views in favor of imperative iterators is exactly the wrong direction. Are we really on a Scala mailing list here?  ;-)

I don't know if you are suggesting to make collection lazy by default but that's something I would agree to in general. Maybe it would mean that you cannot specify the evaluation mode for many of those methods but for those ones which always force the collection but maybe that would be more honest than the current way where strict and lazily evaluated collections share the same types but different expectations.

I am not suggesting we make all collections lazy. What I am suggesting is that we keep and improve the general idea of views (maybe along the lines of reducers in Clojure). Dropping views in favor of iterators is a major step backwards.

Cheers

 - Martin

[martin odersky]

But views exist also! And at least speaking for myself, I do use them in production code. I believe the logical course for Typesafe is to maintain and improve them, rather than remove them and upset the user community in doing this.

Cheers

 - Martin

[Simon Ochsenreither]

I am not suggesting we make all collections lazy. What I am suggesting is that we keep and improve the general idea of views (maybe along the lines of reducers in Clojure). Dropping views in favor of iterators is a major step backwards.

I would prefer that too, but I'm skeptical whether it's possible to a) fix views and b) to be competitive in performance compared to Java 8's Streams.

There is also the question of migration. If we have both strict and lazy variants working, why would anyone pick strict (and why are they more convenient to use) ?

[martin odersky]

I believe it has to do with the fact that evaluation of function arguments is more predictable for strict collections. Laziness requires a lot of discipline in a language with side effects. That's why in Scala strictness is the default, whether for variables or for collections. But I believe laziness has its place as well. At the very least we need it when interoperating with Java 8 collections.

Cheers

 - Martin

[Michael Thaler]

Hi,

There is also the question of migration. If we have both strict and lazy variants working, why would anyone pick strict (and why are they more convenient to use) ?

I think debugging programs that use lazy collections is much harder than debugging programs using non-lazy collections. 

Lazy collections are certainly a nice to have but I prefer using them when necessary and not as default because in my opinion, debugging should be as easy as possible.

Best regards,
Michael

[√iktor Ҡlang]

On Tue, Sep 10, 2013 at 2:26 PM, martin odersky <martin....@epfl.ch> wrote:

On Tue, Sep 10, 2013 at 2:21 PM, Simon Ochsenreither <simon.och...@gmail.com> wrote:

I am not suggesting we make all collections lazy. What I am suggesting is that we keep and improve the general idea of views (maybe along the lines of reducers in Clojure). Dropping views in favor of iterators is a major step backwards.

I would prefer that too, but I'm skeptical whether it's possible to a) fix views and b) to be competitive in performance compared to Java 8's Streams.

There is also the question of migration. If we have both strict and lazy variants working, why would anyone pick strict (and why are they more convenient to use) ?

I believe it has to do with the fact that evaluation of function arguments is more predictable for strict collections. Laziness requires a lot of discipline in a language with side effects.

It gets exponentially worse with the number of threads being involved as well. (Closing over mutable state paired with concurrency).

Cheers,

√

 

That's why in Scala strictness is the default, whether for variables or for collections. But I believe laziness has its place as well. At the very least we need it when interoperating with Java 8 collections.

Cheers

 - Martin

--
You received this message because you are subscribed to the Google Groups "scala-language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-languag...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

--

Viktor Klang
Director of Engineering

Typesafe

Twitter: @viktorklang

[martin odersky]

I think you misunderstand what I am trying to say. "map" is a fundamental operation on any monad (it's `bind' composed with `unit'.) Sets are about as canonical a monad as you can think of. To deny sets a map operation means you wash any idea of monadic abstraction down the drain. It's not a matter what monad to pick. It's a matter whether there should be a link between for expressions and monads or not. If this is a "little thing" as you suggest, what is a large one?

Cheers

 - Martin

[Lex Spoon]

Three brief notes on some possibly relevant experience.

First, if you ask old Smalltalk zealots what they liked in their
language, way up the list is the collections library. The Smalltalk
collections library is strict and uses higher-order functions
everywhere. In practice, developers usually write obvious-looking code
that wastes storage, and in cases where that's not sufficient, they
find an alternate solution. Those alternate solutions do not involve
iterators; like in Scala, Smalltalk doesn't offer a lot of support for
imperative code.

Second, I've worked in three Java shops in a row, and I haven't heard
any interest in Java 8 collections. People who think about collections
at all have already switched to Guava and/or Apache Commons, but most
don't even bother with that. It might be worth poking on the idea that
the new "streams" are going to be a standard way to program that
everyone takes for granted. What's the basis for thinking so? It might
be just one more thing on the long list of oddities that someone had a
passion for, which is apparently all it takes these days to get
something into Java.

Third, one thing we know from Haskell's grand laziness experiment is
that lazy code, far from making code automatically run fast, actually
leads to slow code where it is difficult to understand why. The
problem is that the building blocks have unclear performance
implications, and composing them certainly does nothing to make things
clearer. I see no reason Haskell's experience will be different for
lazy collection operations in Scala. As two simple examples of what I
mean:

1. You might make a lowly call to Set.contains, which ought to be
constant time, but it actually forces a pile of pending work that is
quite expensive.

2. You write a dumb-looking List.map, but you pin tons of storage
due to the function argument referencing "compiler.isSubTypeOf" and
thus "compiler".

Icing on the cake is that profiling tools don't work for lazy code.
They bill CPU time to all the wrong places.


I don't know what any of the above implies. It's just three quick
connections to real-world experience with various programming
languages. Most of all, I'm glad Scala has an actual designer, rather
than vascillating from accepting nothing (Java 5-7) to accepting
everything anyone can think of (Java 8+). Far better for someone to
think through how it all fits together.

Lex Spoon

[Bardur Arantsson]

On 2013-09-10 15:34, Lex Spoon wrote:
> Third, one thing we know from Haskell's grand laziness experiment is
> that lazy code, far from making code automatically run fast, actually
> leads to slow code where it is difficult to understand why. The
> problem is that the building blocks have unclear performance
> implications, and composing them certainly does nothing to make things
> clearer. I see no reason Haskell's experience will be different for
> lazy collection operations in Scala.

Indeed, and in fact some of these experiences have brought about changes
in the "containers" library -- Map now comes in two variants: lazy and
(value-)strict.

It should probably be mentioned here that things aren't nearly as
unpredicable in a strict-by-default language like Scala. Your lazy
collections may still incur a lot of "bookkeeping" overhead at
unpredictable times, but at least you won't end up computing the
*element* values at unpredictable times.

Regards,

[Alec Zorab]

But it's somewhat hard to argue that the current implementation of map on sets does the right thing. One can certainly construct (admittedly contrived) examples where it doesn't obey the functor laws, for example:

      import org.scalacheck.Prop.forAll

      case class BreaksIt(a:Int)(val b:Int)

      val f: Int => BreaksIt = i => BreaksIt(0)(i)

      val g: BreaksIt => Int = b => b.b

      check(forAll((s:Set[Int]) => (s map f map g) == (s map (f andThen g))))

[info]   GeneratorDrivenPropertyCheckFailedException was thrown during property evaluation.

[info]  (Test.scala:52)

[info]   Falsified after 3 successful property evaluations.

[info]   Location: (Test.scala:52)

[info]   Occurred when passed generated values (

[info]     arg0 = Set(0, -1) // 30 shrinks

[info]   )

[Johannes Rudolph]

`Set[A]` is as much `Set[A]` as it is an `Iterable[A]`. I have other expectations on its `map` method when I view it as an `Iterable[A]` as when I view it as an `Set[A]`. When I view it as an Iterable[A] I expect that, as its description says, map "returns a new iterable collection resulting from applying the given function f to each element of this iterable collection and collecting the results." It doesn't give any indication about how it is "collecting the results" but there's nothing that would make me expect that collection is done in a way which only collects distinct elements.

Speaking of monadic operations you could do the same for `flatMap` which is defined in terms of concatenation. Iterable.++ is defined as "returns a new collection of type That which contains all elements of this iterable collection followed by all elements of that.". Here, the question is what "followed by" means. Evidence from what Set.++ implements, the definition of "followed by" becomes pretty much useless because it could mean anything based on the concrete subclass of Iterable.

IMO it would make sense to define Iterable with a set of invariants that should be adhered to by all subclasses. Intuitive ones are

(a ++ b).size == a.size + b.size

and, yes, also

a.map(f).size == a.size

etc.

That would lead to Set not being an Iterable any more because it can't adhere to those invariants. But that would be ok in my picture. This wouldn't preclude Set from implementing monadic operations with Set's "canonical" monad semantics. However, it would preclude Set from composing with other monadic values in for-comprehensions. But IMO that would also be ok for me as long as there's an explicit way to select how those monads should compose.

[martin odersky]

Thanks for the explanations. That's definitely a possible design. I guess in the Scala collection Seq overlaps largely with what you would like to capture in Iterable. Except that Seq also defines an apply method for indexing. 

So it comes down to a question of naming and distinction. Is Iterable the right name for what it is? I'd argue yes, because Iterable comes from Java where Sets are also Iterables. Do we need another distinction, such as LengthPreservingIterable with Seq and MultiSet as extensions, but not Set as an extension? Maybe, it comes down to balancing degree of precision for specifying properties against the cognitive overhead for reading the docs.

Cheers

 - Martin

[Oliver Ruebenacker]

     Hello,

--

You received this message because you are subscribed to the Google Groups "scala-language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-languag...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

  Maybe not every one cares about Monads?

  When I read "Iterable", I understand "able to be iterated over", and that's what Set definitely is.

  And you don't need to take a journey into Monadland to understand what Iterable.map does: apply function to all members and add results to new collection of same collection semantics.

  There are also plenty of uses for Iterable.map that work for Sets as well as for Lists, etc:

  def printThemAll(c : Iterable) = c.map(println(_))

  def wrapThemAll(c : Iterable) = c.map(wrap(_))

  And even disallow Set.map, you still may be burned by making "intuitive" assumptions:

scala> val whoShuffledMySet = Set(1, 2, 3, 4, 5, 6, 7)
whoShuffledMySet: scala.collection.immutable.Set[Int] = Set(5, 1, 6, 2, 7, 3, 4)

scala> val whyDoesMySetNotGrow = (Set(0) ++ List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9).map(_/10)).size
whyDoesMySetNotGrow: Int = 1

     Best,

     Oliver

--

Oliver Ruebenacker
IT Project Lead at PanGenX (http://www.pangenx.com)

Be always grateful, but never satisfied.

[Kevin Wright]

They do, even if they don't know they do, even if they've never heard the term.

Define Monad as "thing that you can map, flatMap and filter over, and therefore use in a for-comprehension, with consistent semantics" and it's more obvious.

 

  When I read "Iterable", I understand "able to be iterated over", and that's what Set definitely is.

  And you don't need to take a journey into Monadland to understand what Iterable.map does: apply function to all members and add results to new collection of same collection semantics.

  There are also plenty of uses for Iterable.map that work for Sets as well as for Lists, etc:

  def printThemAll(c : Iterable) = c.map(println(_))

  def wrapThemAll(c : Iterable) = c.map(wrap(_))

 

  And even disallow Set.map, you still may be burned by making "intuitive" assumptions:

scala> val whoShuffledMySet = Set(1, 2, 3, 4, 5, 6, 7)
whoShuffledMySet: scala.collection.immutable.Set[Int] = Set(5, 1, 6, 2, 7, 3, 4)

Sets are unordered, by definition.  This is only unintuitive if you don't know what a set is.

It's about as unintuitive as wondering why your skateboard doesn't have a handle, after assuming it was a kind of scooter with 4 wheels.

 

scala> val whyDoesMySetNotGrow = (Set(0) ++ List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9).map(_/10)).size
whyDoesMySetNotGrow: Int = 1

This isn't disallowing map, this is emphatically *using* map, and demonstrates the exact point that PaulP already made!

 

     Best,

     Oliver

[Johannes Rudolph]

On Tue, Sep 10, 2013 at 5:16 PM, Oliver Ruebenacker <cur...@gmail.com> wrote:

  There are also plenty of uses for Iterable.map that work for Sets as well as for Lists, etc:

  def wrapThemAll(c : Iterable) = c.map(wrap(_))

How do you know it "works" for all of them (especially for "etc")? If Set.map's implementation is allowed why not other possible subtypes of Iterable where `wrapThemAll` suddenly doesn't work* any more? Like a collection that only contains elements where element.toString is less than 5 characters long with `map` implemented similar to Set.map. Sounds unreasonable but in lack of a specification of what to expect from Iterable's methods you can't make any assumptions. So, how would you program against Iterable? 

(I'm just trying to put the finger on what it is that makes Set's behavior as surprising as it is)

--
Johannes

*) for a reasonable interpretation of "works"

[Oliver Ruebenacker]

     Hello,

  Let's say I develop this new theory called frombo theory, which explains much of what Scala does by thinking of Scala objects as frombos performing frombo operations.

  I will then claim that Scala is all about frombo theory. Scala works only thanks to frombo theory. If you don't know frombo theory, you don't know Scala. It's all about frombos. So, before you want to debate Scala, you should frist learn about frombo theory, and then you would understand much better what Scala is all about. And, of course, Scala needs to be fixed to even better work according to frombo theory.

  When I read "Iterable", I understand "able to be iterated over", and that's what Set definitely is.

  And you don't need to take a journey into Monadland to understand what Iterable.map does: apply function to all members and add results to new collection of same collection semantics.

  There are also plenty of uses for Iterable.map that work for Sets as well as for Lists, etc:

  def printThemAll(c : Iterable) = c.map(println(_))

  def wrapThemAll(c : Iterable) = c.map(wrap(_))

 

  And even disallow Set.map, you still may be burned by making "intuitive" assumptions:

scala> val whoShuffledMySet = Set(1, 2, 3, 4, 5, 6, 7)
whoShuffledMySet: scala.collection.immutable.Set[Int] = Set(5, 1, 6, 2, 7, 3, 4)

Sets are unordered, by definition.  This is only unintuitive if you don't know what a set is.

It's about as unintuitive as wondering why your skateboard doesn't have a handle, after assuming it was a kind of scooter with 4 wheels.

  That's exactly my point regarding Set.map.

 

scala> val whyDoesMySetNotGrow = (Set(0) ++ List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9).map(_/10)).size
whyDoesMySetNotGrow: Int = 1

This isn't disallowing map, this is emphatically *using* map, and demonstrates the exact point that PaulP already made!

  This is using List.map, not Set.map.

  I'm not sure what point of PaulP is demonstrated.

     Best,

     Oliver

[Oliver Ruebenacker]

     Hello,

On Tue, Sep 10, 2013 at 11:49 AM, Johannes Rudolph <johannes...@googlemail.com> wrote:

On Tue, Sep 10, 2013 at 5:16 PM, Oliver Ruebenacker <cur...@gmail.com> wrote:

  There are also plenty of uses for Iterable.map that work for Sets as well as for Lists, etc:

  def wrapThemAll(c : Iterable) = c.map(wrap(_))

How do you know it "works" for all of them (especially for "etc")? If Set.map's implementation is allowed why not other possible subtypes of Iterable where `wrapThemAll` suddenly doesn't work* any more? Like a collection that only contains elements where element.toString is less than 5 characters long with `map` implemented similar to Set.map. Sounds unreasonable but in lack of a specification of what to expect from Iterable's methods you can't make any assumptions. So, how would you program against Iterable? 

(I'm just trying to put the finger on what it is that makes Set's behavior as surprising as it is)

 I don't get what the issue is? I check the documentation of Iterable.map:

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

  and that's what I want.

     Best,

     Oliver

[martin odersky]

On Tue, Sep 10, 2013 at 4:10 PM, Alec Zorab <alec...@gmail.com> wrote:

But it's somewhat hard to argue that the current implementation of map on sets does the right thing. One can certainly construct (admittedly contrived) examples where it doesn't obey the functor laws, for example:

      import org.scalacheck.Prop.forAll

      case class BreaksIt(a:Int)(val b:Int)

      val f: Int => BreaksIt = i => BreaksIt(0)(i)

      val g: BreaksIt => Int = b => b.b

      check(forAll((s:Set[Int]) => (s map f map g) == (s map (f andThen g))))

I don't think it's that hard to argue that Set does the right thing. Monad and functor laws only apply to pure functions. What does pure mean in this sense? Hint: It comes back to what Jason mentioned. Functions need to be assumed to be extensional. That is, if x == y then f(x) == f(y) needs to hold also. Wrt to what sort of equality should we interpret that, you might ask? It does not really matter, but what's important is that when we talk about sets, they are understood to be sets with respect to the same concept of equality. 

In the example you gave, equality is ==/equals. But the g function you defined is NOT extensional wrt to that equality. 

  BreaksIt(0)(1) == BreaksIt(0)(2)

yet, g(BreaksIt(0)(1)) == 1 != 2 == g(BreaksIt(0)(2)).

So here's your argument :-)

Cheers

 - Martin

[Johannes Rudolph]

On Tue, Sep 10, 2013 at 6:17 PM, martin odersky <martin....@epfl.ch> wrote:

On Tue, Sep 10, 2013 at 4:10 PM, Alec Zorab <alec...@gmail.com> wrote:

But it's somewhat hard to argue that the current implementation of map on sets does the right thing. One can certainly construct (admittedly contrived) examples where it doesn't obey the functor laws, for example:

      import org.scalacheck.Prop.forAll

      case class BreaksIt(a:Int)(val b:Int)

      val f: Int => BreaksIt = i => BreaksIt(0)(i)

      val g: BreaksIt => Int = b => b.b

      check(forAll((s:Set[Int]) => (s map f map g) == (s map (f andThen g))))

I don't think it's that hard to argue that Set does the right thing.

I agree that there's little choice about what Set's canonical monad is (when seeing Set in isolation). What I've not yet seen is convincing evidence that the current behavior is the most useful. You mentioned ScalaQuery and random number generators. Is there anywhere more information about those use cases? You can find a bit when googling for 'set monad', e.g. [1, 2], but I don't find those particularly convincing. I mean you can hardly argue against "In other cases, with many duplicates, the Set monad is exponentially worthwhile." [2], but is this really the way you use Sets commonly?

--
Johannes

[1] http://www.randomhacks.net/articles/2007/03/15/data-set-monad-haskell-macros

[2] http://okmij.org/ftp/Haskell/set-monad.html

[Alec Zorab]

Right, but you're surely not arguing that nobody has ever experienced unexpected behaviour as a result of mapping a set of elements with an ill defined equals method? 

Implicit in the current construction of sets is that the elements of the set must implement equals and hashcode in a correct and consistent manner, but there's nothing to actually enforce this - the current implementation just uses the methods from Object and hopes for the best. 

There's nothing enforcing the invariant that Set should be using the same notion of equality as any methods used as arguments to map, and I'd argue that this is a source of a confusion in a number of cases where we see the interactions. I'd present the argument that Set is a monad only when there is a properly defined notion of equality for the target type B of the map/flatMap (and a rather more performant/useful monad becomes available if we also have an Ordering[B]).

I have no idea how you'd actually implement that with the std library encoding of collections/functors etc though.

[Kevin Wright]

If frombo theory has a sound mathematical basis, if it offers additional insight into programming, if it provides effective ways to think about the nature of computation and aids in problems of consistency, composability, and maintainability... Then you'd be onto something.

People write monads all the time without recognising them as such, and you can be quite certain that there's old code demonstrating some of the tenets of "object orientation", even though it predates the coining of that term

So yes, if frombos were real and useful then it would make perfect sense to consciously use them.

 

  When I read "Iterable", I understand "able to be iterated over", and that's what Set definitely is.

  And you don't need to take a journey into Monadland to understand what Iterable.map does: apply function to all members and add results to new collection of same collection semantics.

  There are also plenty of uses for Iterable.map that work for Sets as well as for Lists, etc:

  def printThemAll(c : Iterable) = c.map(println(_))

  def wrapThemAll(c : Iterable) = c.map(wrap(_))

 

  And even disallow Set.map, you still may be burned by making "intuitive" assumptions:

scala> val whoShuffledMySet = Set(1, 2, 3, 4, 5, 6, 7)
whoShuffledMySet: scala.collection.immutable.Set[Int] = Set(5, 1, 6, 2, 7, 3, 4)

Sets are unordered, by definition.  This is only unintuitive if you don't know what a set is.

It's about as unintuitive as wondering why your skateboard doesn't have a handle, after assuming it was a kind of scooter with 4 wheels.

  That's exactly my point regarding Set.map.

 

scala> val whyDoesMySetNotGrow = (Set(0) ++ List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9).map(_/10)).size
whyDoesMySetNotGrow: Int = 1

This isn't disallowing map, this is emphatically *using* map, and demonstrates the exact point that PaulP already made!

  This is using List.map, not Set.map.

 

  I'm not sure what point of PaulP is demonstrated.

The point was that sets have distinct elements, so adding something already present is essentially a NOP.

The same applies when mapping over a set with a surjective function[1]; you might attempt to put two copies of a value in the resulting set, which isn't possible, and results in a set smaller than the original.  This change in size during a map operation is what seems counter-intuitive.

It's possible that the type system could be used to enforce the use of injective or bijective functions[2] in this case, but the challenge is then one of identifying functions as such, and would almost certainly fall foul of the halting problem in any turing complete language.

Perhaps a fully developed frombo theory would help here?

[1] http://en.wikipedia.org/wiki/Surjective_function

[2] http://en.wikipedia.org/wiki/Injective_function

 

     Best,

     Oliver

--

Oliver Ruebenacker
IT Project Lead at PanGenX (http://www.pangenx.com)

Be always grateful, but never satisfied.

--

You received this message because you are subscribed to the Google Groups "scala-language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-languag...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

--
Kevin Wright
mail: kevin....@scalatechnology.com
gtalk / msn : kev.lee...@gmail.com

quora: http://www.quora.com/Kevin-Wright

google+: http://gplus.to/thecoda

twitter: @thecoda

vibe / skype: kev.lee.wright

steam: kev_lee_wright

"My point today is that, if we wish to count lines of code, we should not regard them as "lines produced" but as "lines spent": the current conventional wisdom is so foolish as to book that count on the wrong side of the ledger" ~ Dijkstra

[Alex Cruise]

I'm happy that this thread is happening, and that Martin is involved. 

I just want to say that we shouldn't be dismissive of Java.  Sure, Sun/Oracle have made a few bad decisions over the decades (!), but where they go, a huge part of the mainstream follows. Whether we agree with their direction or not, as long as we want to keep claiming that our stuff is compatible with their stuff, we need to pay close attention.

When other people's engineering tradeoffs go in opposite directions to where we would have gone, they might in fact have good reasons of their own. :)

-0xe1a

[Jason Zaugg]

On Tue, Sep 10, 2013 at 6:29 PM, Johannes Rudolph <johannes...@googlemail.com> wrote:

On Tue, Sep 10, 2013 at 6:17 PM, martin odersky <martin....@epfl.ch> wrote:

On Tue, Sep 10, 2013 at 4:10 PM, Alec Zorab <alec...@gmail.com> wrote:

But it's somewhat hard to argue that the current implementation of map on sets does the right thing. One can certainly construct (admittedly contrived) examples where it doesn't obey the functor laws, for example:

      import org.scalacheck.Prop.forAll

      case class BreaksIt(a:Int)(val b:Int)

      val f: Int => BreaksIt = i => BreaksIt(0)(i)

      val g: BreaksIt => Int = b => b.b

      check(forAll((s:Set[Int]) => (s map f map g) == (s map (f andThen g))))

I don't think it's that hard to argue that Set does the right thing.

I agree that there's little choice about what Set's canonical monad is (when seeing Set in isolation). What I've not yet seen is convincing evidence that the current behavior is the most useful. You mentioned ScalaQuery and random number generators. Is there anywhere more information about those use cases? You can find a bit when googling for 'set monad', e.g. [1, 2], but I don't find those particularly convincing. I mean you can hardly argue against "In other cases, with many duplicates, the Set monad is exponentially worthwhile." [2], but is this really the way you use Sets commonly?

The bottom line is that you can treat List as a Monad, or even Set if used in isolation with functions that pure wrt element equality, but you can't do the same in general for Iterable.

The uniform API that Scala collections offer for such a wide range of collections doesn't come for free: once you've abstracted that far you can't really say much about the semantics of the operations (aka reason algebraically with laws). The axes of variation are many: mutable/immutable, set/seq, parallel/sequential, lazy/strict.

But the crucial variation is collections that are fully parametric (List, Vector) vs those that are constrain the element type (WrappedString, Map, TreeSet). You can put other Sets into that last category too -- they rely on the implementation equals/hashCode from Any, which in another sort of constraint, even though those methods happen to be defined universally.)

In practice, I tend to convert to a concrete collection and operate on that.

I've love some feedback from the collection-wranglers out there: Every project ends up with a "CollectionUtils" class that expands the library of collections functions, e.g. to create a multimap, or to chunk a sequence in to runs of identical elements. What's in yours? Do you thread CanBuildFrom's through and generalize these to `Traversable`? Or do you operate on specific data types. What pitfalls have you encountered along the way?

-jason

PS: even in the corner of the collection hierarchy that Sets inhabit, an upcast can show surprises. The polymorphic `newBuilder` mechanism steps in and spits out a Set, but we've switched from the provided ordering to universal equality.

scala> case class A(a: Int)(val b: Int)

defined class A

scala> implicit val AOrd: Ordering[A] = Ordering.by((x: A) => (x.a, x.b))

AOrd: Ordering[A] = scala.math.Ordering$$anon$9@4d09b5ca

scala> val ts = TreeSet[A](A(0)(1), A(0)(2))

ts: scala.collection.immutable.TreeSet[A] = TreeSet(A(0), A(0))

scala> ts.map(x => x)

res5: scala.collection.immutable.SortedSet[A] = TreeSet(A(0), A(0))

scala> (ts: Set[A]).map(x => x)

res6: scala.collection.immutable.Set[A] = Set(A(0))

[Lex Spoon]

On Thu, Sep 12, 2013 at 7:05 AM, Jason Zaugg <jza...@gmail.com> wrote:
> The bottom line is that you can treat List as a Monad, or even Set if used
> in isolation with functions that pure wrt element equality, but you can't do
> the same in general for Iterable.

I don't know whether this is true, but I will say in practice that you
don't want to use quite a lot of the methods currently available on
Iterable. Iterable is so far up the hierarchy that you don't know what
any of them will do.

Some examples are ++ and map, where you probably want to know if you
are dealing with a set. Other examples would be tail, take, and init.
You are better off converting to a concrete type and *then* calling
these methods. It won't be any slower, because as far as you know,
they will iterate the whole collection anyway.

> In practice, I tend to convert to a concrete collection and operate on that.

I use a lot more concrete collection types than when I first started
writing some Scala examples on "nsc", the new and shiny self-hosted
Scala compiler. It's a good instinct to abstract to more general
types, but in the case of collections, you often really want to know
what the underlying type is. The "Iterable" type should only be used
if really all you want to do is iterate. If you want to create new
collections, you at least want to know if you are dealing with a Seq
or a Set, because they will behave differently. If you are dealing
with a Seq, you frequently want to know if it's a List or an Array or
a Vector. If you need to know something, then abstracting it away was
wrong to begin with.

Lex

[martin odersky]

On Thu, Sep 12, 2013 at 3:19 PM, Lex Spoon <l...@lexspoon.org> wrote:

On Thu, Sep 12, 2013 at 7:05 AM, Jason Zaugg <jza...@gmail.com> wrote:
> The bottom line is that you can treat List as a Monad, or even Set if used
> in isolation with functions that pure wrt element equality, but you can't do
> the same in general for Iterable.

I don't know whether this is true, but I will say in practice that you
don't want to use quite a lot of the methods currently available on
Iterable. Iterable is so far up the hierarchy that you don't know what
any of them will do.

Some examples are ++ and map, where you probably want to know if you
are dealing with a set.

Not necessarily. Say you want to search a space of possible candidates that get generated in some fashion. Then ++ is union (take all possibilities) and map a result transformation. Now, you might find it more efficient to remove duplicates from your search space changing your generators to produce sets instead of sequences. But the search functionality is completely unchanged. ++ and map make as much sense as they did before.

 

Other examples would be tail, take, and init.
You are better off converting to a concrete type and *then* calling
these methods. It won't be any slower, because as far as you know,
they will iterate the whole collection anyway.

Take is more of a stretch, but even here you could imagine a scenario where you want to search N solutions in parallel, but do not care which ones, so a take N would be quite appropriate for that.

> In practice, I tend to convert to a concrete collection and operate on that.

I use a lot more concrete collection types than when I first started
writing some Scala examples on "nsc", the new and shiny self-hosted
Scala compiler. It's a good instinct to abstract to more general
types, but in the case of collections, you often really want to know
what the underlying type is. The "Iterable" type should only be used
if really all you want to do is iterate. If you want to create new
collections, you at least want to know if you are dealing with a Seq
or a Set, because they will behave differently. If you are dealing
with a Seq, you frequently want to know if it's a List or an Array or
a Vector. If you need to know something, then abstracting it away was
wrong to begin with.

Agreed. As a user, I also often prefer the more concrete type over the abstract one. But as a library designer you want to make the abstract type available for those algorithms that are abstract in nature. I don't believe in crippling functionality because someone might be confused or might be taken to misuse it.

Cheers

- Martin

Lex

--
You received this message because you are subscribed to the Google Groups "scala-language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-languag...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Paul Phillips]

On Thu, Sep 12, 2013 at 6:28 AM, martin odersky <martin....@epfl.ch> wrote:

Agreed. As a user, I also often prefer the more concrete type over the abstract one. But as a library designer you want to make the abstract type available for those algorithms that are abstract in nature. I don't believe in crippling functionality because someone might be confused or might be taken to misuse it.

It is frequently misrepresented this way, but it is hardly a question of "crippling" functionality because "someone might be confused". It is entirely possible to write code in such a way that people who think these traps are a good idea can have them, and people who don't can avoid them. In the scala collections (among other places in scala) all the traps are bundled directly into the core types. Everyone gets to enjoy them whether they like it or not.

It doesn't have to be like that.

[Oliver Ruebenacker]

     Hello Paul,

  Ok, in a standard library as you envision it, what would happen to code like this:

  case class Wrapper(a: Any)

  def printEmAll(c: Iterable) = c.map(println(_))

  def wrapEmAll(c: Iterable) = c.map(Wrapper(_))

  I want to be able to print or wrap over any collection, including Sets and Seqs.

     Best,

     Oliver

[Eric Torreborre]

PS: even in the corner of the collection hierarchy that Sets inhabit, an upcast can show surprises. The polymorphic `newBuilder` mechanism steps in and spits out a Set, but we've switched from the provided ordering to universal equality.

This is why I gave up trying implementing a UserDefinedSet collection, integrated in the current collection hierarchy, where the user can provide an equality function. One reason why this might not be possible is that Set is not a Functor, but that goes back to the previous discussion...

E.

[martin odersky]

Also agreed. I think since the collections were designed for 2.8, Scala has gained much better tools in what concerns decorators.  So it would be interesting to review the collections design with fewer core methods and more stuff in decorators. The big question is: to what degree can this be compatible with the current library? We need a concrete library to experiment with and to answer this question.

Cheers

 - Martin

--
You received this message because you are subscribed to the Google Groups "scala-language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-languag...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Paul Phillips]

On Thu, Sep 12, 2013 at 11:19 PM, martin odersky <martin....@epfl.ch> wrote:

We need a concrete library to experiment with and to answer this question.

Won't be long[*] now.

[*] Assumes appropriate choice of time scale.

[martin odersky]

On Fri, Sep 13, 2013 at 3:00 AM, Eric Torreborre <etorreborre@gmail.com> wrote:

PS: even in the corner of the collection hierarchy that Sets inhabit, an upcast can show surprises. The polymorphic `newBuilder` mechanism steps in and spits out a Set, but we've switched from the provided ordering to universal equality.

This is why I gave up trying implementing a UserDefinedSet collection, integrated in the current collection hierarchy, where the user can provide an equality function. One reason why this might not be possible is that Set is not a Functor, but that goes back to the previous discussion...

 

I am getting upset when people on this list or in tweets pronounce category-theoretic wisdom without explaining. I get even more upset when this "wisdom" is at best misleading and at worst nonsense. To me it looks like set _is_ a functor in exactly the same sense as List is a functor. Don't believe me? See http://en.wikipedia.org/wiki/Functor and search for "powerset functor".

To not follow the example I have just criticized, let me explain:

Is List a functor? I could argue, obviously not:

   var x = 0

   List(1, 2, 3) map { y => x += 1; y } map { z => x }     gives    List(3, 3, 3)

   List(1, 2, 3) map ({ y => x += 1; y } andThen { z => x })   gives   List(1, 2, 3)

so the associativity law does not hold. 

But if List is not a functor, we can forget about any law whatsoever. So obviously, we have to be precise what we mean by a "function" here. The closures I wrote above are not functions in the mathematical sense because x == y does not imply f(x) == f(y). With extensional functions we can prove that List is a functor.

Now to Set. I would be surprised if you could come up with a counter-example where the associativity law does not hold for Set. Of course, you again may only use functions that are functions in the mathematical sense i.e. x == y must imply f(x) == f(y).

Cheers

 - Martin

[Johannes Rudolph]

On Thu, Sep 12, 2013 at 3:28 PM, martin odersky <martin....@epfl.ch> wrote:

On Thu, Sep 12, 2013 at 3:19 PM, Lex Spoon <l...@lexspoon.org> wrote:

On Thu, Sep 12, 2013 at 7:05 AM, Jason Zaugg <jza...@gmail.com> wrote:
> The bottom line is that you can treat List as a Monad, or even Set if used
> in isolation with functions that pure wrt element equality, but you can't do
> the same in general for Iterable.

I don't know whether this is true, but I will say in practice that you
don't want to use quite a lot of the methods currently available on
Iterable. Iterable is so far up the hierarchy that you don't know what
any of them will do.

Some examples are ++ and map, where you probably want to know if you
are dealing with a set.

I think the important thing for specifying the behavior of Iterable's methods is to specify them in terms of `iterator` which is the only method which really defines an Iterable.

 

Not necessarily. Say you want to search a space of possible candidates that get generated in some fashion. Then ++ is union (take all possibilities) and map a result transformation. Now, you might find it more efficient to remove duplicates from your search space changing your generators to produce sets instead of sequences. But the search functionality is completely unchanged. ++ and map make as much sense as they did before.

The problem with this is that as it stands the specification of ++ is not written in terms of Iterable.iterator's behavior (for receiver, argument, and resulting Iterables). This means that what you suggest is precisely not possible because you don't know how ++ will behave. You don't know if the result of Iterable.++ will contain any elements at all, the receiver could be a collection which is constrained to only contain a single element for example, in the same way as a Set is allowed to be constrained to only contain distinct elements.

I'd say you can make this argument for almost all of Iterable's methods (i.e. current Iterable which allows Set with its current behavior as a valid subtype) apart from maybe toArray and similar methods which have a well-defined behavior in terms of Iterable.iterator even with Set as a subclass.

So it comes down to a question of naming and distinction. Is Iterable the right name for what it is? 

So, what is it? In Scala either

a) Iterable.++ has the intuitive meaning defined in terms of Iterable.iterator in which case Set being a subclass of Iterable is a bug

b) something like Set.++ is allowed to be an implementation of Iterable.++, in which case the label Iterable 

means nothing at all

E.g. see this:

val s: Iterable[Int] = // omitted

val i: Iterable[Int] = // omitted

scala> s.foreach(println)

1

2

3

scala> i.foreach(println)

1

2

3

scala> (s ++ i).foreach(println)

1

2

3

scala> (i ++ s).foreach(println)

1

2

3

1

2

3

I'd argue yes, because Iterable comes from Java where Sets are also Iterables.

Yes, but java.lang.Iterable doesn't define any mutation/transformations methods so it doesn't face the same problems because there's no way you would try to program against Iterable's interface the way you can do in Scala.

-- 

Johannes

[Paul Phillips]

I'm on a phone so this is a bit off the cuff, but when he says Set isn't a functor it is likely he is referring to its variance, not its resistance to duplicates. Invariant type constructors can't be functors because invariance implies a constraint on the input type, so they aren't fully polymorphic. If I weren't on a phone I'd try for an example. Or maybe that's enough to draw a Haskell guy in to correct me. 

[Oliver Ruebenacker]

     Hello,

  What do we have documentation for? Here are the docs for Iterable:

"This is a base trait for all immutable Scala collections that define an iterator method to step through one-by-one the collection's elements. Implementations of this trait need to provide a concrete method with signature:

def iterator: Iterator[A]"

  This does not say that an Iterable needs to have an inherent order or can have duplicates, and I think that is a good thing. Clearly Iterable includes Set, and I can't think of a reason why it should be any different.

  On the other hand, the docs say on ++:

  "Returns a new immutable iterable collection containing the elements from the left hand operand followed by the elements from the right hand operand."

  This is clearly wrong, since it assumes an order ("followed by"), which is not assumed in the definition of Iterable.

  I don't see in the docs on Iterable anything on intuition or Monad theory. Therefore, the simple solution seems to be to fix the docs on ++, let Set remain an Iterable, and create a new trait MonadicallySeqLikeIterable, which then includes Seq, but not Set, which should then make our monad theorists happy.

     Best,

     Oliver

[Erik Osheim]

On Fri, Sep 13, 2013 at 08:51:13AM -0700, Paul Phillips wrote:
> I'm on a phone so this is a bit off the cuff, but when he says Set isn't a
> functor it is likely he is referring to its variance, not its resistance to
> duplicates. Invariant type constructors can't be functors because
> invariance implies a constraint on the input type, so they aren't fully
> polymorphic. If I weren't on a phone I'd try for an example. Or maybe
> that's enough to draw a Haskell guy in to correct me.

The anxiety is around using equals/hashCode for type A that you don't
know anything about. This blog post discusses it in more depth:

http://failex.blogspot.com/2013/06/fake-theorems-for-free.html

The conclusion is basically that set is not a functor, even though it
does not break the functor laws. The reasoning is that you should not
use runtime information (which includes calling equals or hashCode) in
an unconstrained (parametric polymorphic) context.

I think the motivation stems from the fact that any set implementation
which did not use equals/hashCode would require an instance of a type
class like Ordering (or Hashable or something) to create a set. This
is the reason Haskell has no functor for Data.Set--it needs an extra
ordering instance to be available, violating the fmap signature.

I admit that I'm not totally convinced by this argument. But I wanted
to present it since I hadn't seen it made on list. Someone else who
agrees with the position should feel free to correct my
characterization or to add more details.

There are other arguments against a functor for set that stem from
implementing a type with a broken hashCode or equals. I don't take
these arguments very seriously--if a type's equals/hashCode are
broken, the Set won't function properly even without bringing map into
the picture.

-- Erik

[Paul Phillips]

Yes, the fake theorems for free article was elucidative. "if I don't know anything about it, I can't look at it" it says, and that is what I was trying to get at with "a constraint on the input type," which is to say: knowing something about it. A covariant type constructor CC[+A] knows nothing about the element type by definition.

[Shelby]

This discussion brings to mind the Point of Laziness by Bob Harper:

http://existentialtype.wordpress.com/2011/04/24/the-real-point-of-laziness/

And the rebuttal linked at the bottom:

http://augustss.blogspot.com/2011/05/more-points-for-lazy-evaluation-in.html

Have we ruled out deforestation as part of an solution?

Martin's point that we don't really have category theory without pure functions is profound.

[Eric Tanter]

On Sep 14, 2013, at 7:22 PM, Paul Phillips <pa...@improving.org> wrote:

> Yes, the fake theorems for free article was elucidative. "if I don't know anything about it, I can't look at it" it says, and that is what I was trying to get at with "a constraint on the input type," which is to say: knowing something about it. A covariant type constructor CC[+A] knows nothing about the element type by definition.

Sorry, I don't get this. What does parametricity (= "if I don't know anything about it, I can't look at it") has to do with variance?

A parametric output stream can be contravariant CC[-A] without "looking at A", just like an input stream can be declared covariant but break parametricity (eg. by having special cases for specific types observed through type tests).

-- Éric

[Shelby]

At his blog I linked in my prior post, Augustss pointed out that due to laziness we can get foldr from map for free in Haskell:

http://pages.citebite.com/k2g0w9c1c4lhc

Essentially this is due to employing a closure and the fact that mutable variables are allowed in pure functions, e.g.:

def foldRight[A,B](xs: Functor[A], var v: B)(f: (B,A) => (B)) = xs.map( a => v = f(v,a) )

// yeah I know Scala doesn't let me declare it 'var':

//    https://groups.google.com/forum/#!topic/scala-debate/VPdNmvyneyU

// Or in tempermentally (ahem) "correct" Scala syntax

def foldRight[A,B](xs: Functor[A], _v: B)( f: (B,A) => (B)) = {

   var v = _v

   xs.map( a => v = f(v,a) )

}

It is "free" with laziness because a lazy Functor.map doesn't build the resultant collection until it is accessed-- which is never in the implementation of foldr (which is used to implement Haskell's or).

However, we can get map for free from foldr in a strict evaluation language.

def map[A,B](xs: Foldable[A], var v: Monoid[B], f: A => B) = xs.foldRight(null)( (_1,a) => v += f(a); null )

So therefor in my view of what a category theory standard library should be for a strict language like Scala, especially in the immutable case where we assume a pure function, the only Functor.map needs to support the views concept. This should radically simplify implementation.

Implementation of views is simply making the the call to Monoid.+= lazy, which can be accomplished by returning a LazyMonoid[B].

Thoughts?

P.S. As far as I can see, Paul Phillips suggestion at the prior linked discussion thread of functional composition defeats the point of Functor (category theory) model and implications on reuse. 

[Shelby]

On Monday, September 16, 2013 10:40:28 AM UTC+8, Shelby wrote:

Essentially this is due to employing a closure and the fact that mutable variables are allowed in pure functions, e.g.:

def foldRight[A,B](xs: Functor[A], var v: B)(f: (B,A) => (B)) = xs.map( a => v = f(v,a) )

// yeah I know Scala doesn't let me declare it 'var':

//    https://groups.google.com/forum/#!topic/scala-debate/VPdNmvyneyU

Well foldRight is pure, but the anonymous function input to map above is not pure. But this doesn't matter in this case. How does Haskell enable declaring this within its requirement for pure functions? Employing `let`? I admit I didn't study the Haskell code, just made an assumption they get foldr for free from map.

[Shelby]

Apologies for the triple post in succession...

On Sunday, September 8, 2013 11:10:32 PM UTC+8, Paul Phillips wrote:

I decided to stop wasting my effort on scala, that's what happened. Views are yet another fine example of why I'm moving on. 

Rallying the cause against baroque luggage is helpful, but I hope you abandon your hunger strike.

I think we will soon see a rush of fresh air. There has been much progress made in the compiler and the IDE no? Now revisiting the standard library (probably to be completely redesigned yet again). Hopefully the third time is the charm.

 

[Paul Phillips]

On Sun, Sep 15, 2013 at 8:12 PM, Shelby <she...@coolpage.com> wrote:

Rallying the cause against baroque luggage is helpful, but I hope you abandon your hunger strike.

Ship: sailed. Milk: spilt. Barn: horseless. Rubicon: crossed.

I'll still be somewhere doing something, it will just be a little or maybe a lot different than what I've been doing. I'm thinking you can't do any worse.

[Shelby]

Caesar crossed the Rubicon to remove the gridlock and solve the debt crisis:

http://armstrongeconomics.com/693-2/2012-2/anatomy-of-a-debt-crisis/

In open-source, the emperors are those who can produce the best performing code. I don't care how we get there, as long as we do. Hope to see you around. 

[Shelby]

On Monday, September 16, 2013 10:40:28 AM UTC+8, Shelby wrote:

However, we can get map for free from foldr in a strict evaluation language.

def map[A,B](xs: Foldable[A], var v: Monoid[B], f: A => B) = xs.foldRight(null)( (_1,a) => v += f(a); null )

That wasn't returning the correct type and we can make the inner anonymous function pure when we fix:

def map[A,B](xs: Foldable[A], v: Monoid[B], f: A => B) = xs.foldRight(v)( (mb,a) => mb += f(a) )

Are closures now performance free on Java8 JVM? But Scala doesn't yet support that, so we want to discourage closures in inner loops for now?

Note I am not proposing above that only Functors that are Monoid can implement the map interface. Rather I am just showing how those that are can implement map using a fold.

Such an implementation strategy for views could or could not support map implemented on non-Monoid Functors. Would have to study that.

[Shelby]

On Tuesday, September 17, 2013 8:40:37 PM UTC+8, Shelby wrote:

On Monday, September 16, 2013 10:40:28 AM UTC+8, Shelby wrote:

However, we can get map for free from foldr in a strict evaluation language.

def map[A,B](xs: Foldable[A], var v: Monoid[B], f: A => B) = xs.foldRight(null)( (_1,a) => v += f(a); null )

That wasn't returning the correct type and we can make the inner anonymous function pure when we fix:

def map[A,B](xs: Foldable[A], v: Monoid[B], f: A => B) = xs.foldRight(v)( (mb,a) => mb += f(a) )

Are closures now performance free on Java8 JVM? But Scala doesn't yet support that, so we want to discourage closures in inner loops for now?

s/+=/+/

(or to be more safe `append` depending on outcome of discussion here: https://groups.google.com/d/msg/scala-debate/LWBz3-Q0pNI/JoCi6C7jAQYJ )

def map[A,B](xs: Foldable[A], v: Monoid[B], f: A => B) = xs.foldRight(v)( _ append f(_) )

I understand the point of views is reuse and separation-of-concerns, i.e. that I want to call some code that I can't (or shouldn't) refactor and this code does some map-like (e.g. build a collection from a fold as I showed above) operations, e.g. TakeN, BubbleSort, etc..

I am trying to sketch implementation in mind thus I am surely missing some issues.

So if these operations employ typeclasses (for the fold and append methods), then the caller can override the default implicits to inject the lazy versions of the typeclasses:

https://groups.google.com/d/msg/scala-debate/LWBz3-Q0pNI/N3bNmG61DP4J

My example above is returning a Monoid[B], yet it could have been type parametrized on that typeclass and return the type the caller provided. Thus the code which shouldn't be refactored can return a lazy or non-lazy collection (or perhaps any other semantics one want to write typeclasses for, i.e. perhaps a generalized solution isn't limited to solving only the current problem with views).

If the code we don't want to refactor is using higher level operations than append and fold, e.g. TakeN, BubbleSort, then this mechanism could support random access with laziness. Map isn't required to proceed in any sequential order (another reason why my impure anonymous function upthread was an error), thus perhaps map is the function operation that needs to be overridden, yet we need a common trait for collections so that map can persist itself lazily. I would need to actually dig into implementation to understand all the issues well.

Perhaps this is what views is doing and Martin's point may be the most salient, which is to unify and reduce the number of base classes that have to persist the state for supporting laziness.

P.S. wondering if it would be helpful to rename views to lazy collections to make it more explicit what they do and to disambiguate from view bounds:

http://twitter.github.io/scala_school/advanced-types.html#viewbounds

http://stackoverflow.com/questions/4465948/what-are-scala-context-and-view-bounds

[√iktor Ҡlang]

I think view-bounds are likely to be deprecated.

Cheers,

√

--

You received this message because you are subscribed to the Google Groups "scala-language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-languag...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

--

Viktor Klang
Director of Engineering

Typesafe

Twitter: @viktorklang

[Eric Tanter]

Hi Victor,

Could you elaborate on this or point to a discussion of why they would be deprecated?

Is that related to my other recent question on why I cannot find the <%< constraint?

Thanks!

-- Éric

[√iktor Ҡlang]

Hi Eric,

Their functionality have been superseded by context bounds.

As for <%< I have no idea.

Cheers,
V

[Eric Tanter]

Hi Viktor,

(sorry I mispelled your name in my previous message)

> Their functionality have been superseded by context bounds.

Would you mind elaborating a bit?

From what I understand, a context bound is restricted to a type constructor of one argument C[_], while a view bound imposes no such restrictions.
For instance, T <% Map[T,Int] and T <% String are both valid, while they can't seem to be expressed with context bounds.

Thanks!

-- Éric

[martin odersky]

They can, if you are willing to spend a type alias:

  type MapToInt[T] = Map[T, Int]

  type Str[T] = String

  T: MapToInt, T: Str

Cheers

 - Martin

[Eric Tanter]

Hi Martin,

On Sep 18, 2013, at 11:16 PM, martin odersky <martin....@epfl.ch> wrote:
> They can, if you are willing to spend a type alias:
>
> type MapToInt[T] = Map[T, Int]
> type Str[T] = String
>
> T: MapToInt, T: Str

Hadn't thought about that, thanks.
This is of course not so great, just like we prefer to be able to write anonymous functions instead of giving them a name just for a single use.

This suggests a more flexible definition of context bounds, such as:

T : C[T1...Tk _ Tk+1...Tn] means there exists an implicit value of type
C[T1...Tk T Tk+1...Tn].

Meaning one could directly write:
T: Map[_,Int]
T: Str
T: Foo[A,B,_,D]

(possibly using another symbol than _ to denote the hole)

Would that make sense?

Cheers,

-- Éric

[Eric Tanter]

Hi,

I'm still trying to understand how view bounds are superseded by context bounds, and why it makes sense to deprecate view bounds.
Is it correct to say that everywhere one was using:

class Pair[T <% Comparable[T]]

This would have to be replaced by the following?

type ToComparable[T] = T => Comparable[T]
class Pair[T : ToComparable]

In which ways is that a better way to express one's intent than using a view bound?

I understand that using a context bound (eg. [T : Ordering]) is generally more flexible than using a view bound (eg. [T <% Ordered]), but it is also more verbose if the implicit value has to be used in the body of the function, since it must then be explicitly looked up (or, back to the implicit parameter syntax).

I'd appreciate any further information, including links to previous discussions on the topic (I imagine this has been discussed at length somewhere before the consensus of deprecating view bounds was reached).

Thanks!

-- Éric

[√iktor Ҡlang]

On Thu, Sep 19, 2013 at 2:26 PM, Eric Tanter <eta...@dcc.uchile.cl> wrote:

Hi Martin,

On Sep 18, 2013, at 11:16 PM, martin odersky <martin....@epfl.ch> wrote:
> They can, if you are willing to spend a type alias:
>
>   type MapToInt[T] = Map[T, Int]
>   type Str[T] = String
>
>   T: MapToInt, T: Str

Hadn't thought about that, thanks.
This is of course not so great, just like we prefer to be able to write anonymous functions instead of giving them a name just for a single use.

Well, if you want to get rid of the external type aliases you can provide a type lambda.

def t[T : ({type L[T]=Map[T,Int]})#L] = ???

Cheers,

√

 

This suggests a more flexible definition of context bounds, such as:

T : C[T1...Tk _ Tk+1...Tn] means there exists an implicit value of type
C[T1...Tk T Tk+1...Tn].

Meaning one could directly write:
T: Map[_,Int]
T: Str
T: Foo[A,B,_,D]

(possibly using another symbol than _ to denote the hole)

Would that make sense?

Cheers,

-- Éric

--
You received this message because you are subscribed to the Google Groups "scala-language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-languag...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Eric Tanter]

On Sep 19, 2013, at 9:46 AM, √iktor Ҡlang <viktor...@gmail.com> wrote:
> Well, if you want to get rid of the external type aliases you can provide a type lambda.
>
> def t[T : ({type L[T]=Map[T,Int]})#L] = ???

Thanks Viktor -- I didn't know about this mechanism. It's not really anonymous though, you had to come up with L in the first place.
Ie., it's just like the difference between (x:Int) => x and
{ def id(x:Int) = x ; id _}

More importantly, I don't think it is hardly as readable as T: Map[_,Int], right?
(or T <% Map[T,Int])

Is there something inherently wrong/impossible with supporting something like
T: C[A,B,_,D]?

Thanks,

-- Éric

[√iktor Ҡlang]

On Thu, Sep 19, 2013 at 2:53 PM, Eric Tanter <eta...@dcc.uchile.cl> wrote:

On Sep 19, 2013, at 9:46 AM, √iktor Ҡlang <viktor...@gmail.com> wrote:
> Well, if you want to get rid of the external type aliases you can provide a type lambda.
>
> def t[T : ({type L[T]=Map[T,Int]})#L] = ???

Thanks Viktor -- I didn't know about this mechanism. It's not really anonymous though, you had to come up with L in the first place.

It's quite anonymous since it is introduced in a very local scope and type aliases are expanded.

 

Ie., it's just like the difference between (x:Int) => x and
{ def id(x:Int) = x ; id _}

More importantly, I don't think it is hardly as readable as T: Map[_,Int], right?
(or T <% Map[T,Int])

Is there something inherently wrong/impossible with supporting something like
T: C[A,B,_,D]?

Partial type application would be nice to have without having to use type lambdas (like above) but I'm pretty sure that way smarter people than myself have been debating this before,

so I'll let them chime in.

Cheers,

√

 

Thanks,

-- Éric

--
You received this message because you are subscribed to the Google Groups "scala-language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-languag...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Jason Zaugg]

On Thu, Sep 19, 2013 at 2:46 PM, √iktor Ҡlang <viktor...@gmail.com> wrote:

On Thu, Sep 19, 2013 at 2:26 PM, Eric Tanter <eta...@dcc.uchile.cl> wrote:

Hi Martin,

On Sep 18, 2013, at 11:16 PM, martin odersky <martin....@epfl.ch> wrote:
> They can, if you are willing to spend a type alias:
>
>   type MapToInt[T] = Map[T, Int]
>   type Str[T] = String
>
>   T: MapToInt, T: Str

Hadn't thought about that, thanks.
This is of course not so great, just like we prefer to be able to write anonymous functions instead of giving them a name just for a single use.

Well, if you want to get rid of the external type aliases you can provide a type lambda.

def t[T : ({type L[T]=Map[T,Int]})#L] = ???

  def t[T](implicit view: T => Map[T, Int])

Just to step back a little, we've found that APIs designed using view bounds can lead to surprises for users of the API, and the feature tends not be be used by experienced Scala programmers. So we feel that leaving in this shorthand for a questionable design pattern isn't the best thing for new users.

In the proposed deprecation, we suggest you rewrite them as an implicit parameter, rather than as a context bound. Admittedly, it's a little boilerplatey, so you can use the type alias / context bound if you feel comfortable with it instead.

-jason

[√iktor Ҡlang]

On Thu, Sep 19, 2013 at 3:20 PM, Jason Zaugg <jza...@gmail.com> wrote:

On Thu, Sep 19, 2013 at 2:46 PM, √iktor Ҡlang <viktor...@gmail.com> wrote:

On Thu, Sep 19, 2013 at 2:26 PM, Eric Tanter <eta...@dcc.uchile.cl> wrote:

Hi Martin,

On Sep 18, 2013, at 11:16 PM, martin odersky <martin....@epfl.ch> wrote:
> They can, if you are willing to spend a type alias:
>
>   type MapToInt[T] = Map[T, Int]
>   type Str[T] = String
>
>   T: MapToInt, T: Str

Hadn't thought about that, thanks.
This is of course not so great, just like we prefer to be able to write anonymous functions instead of giving them a name just for a single use.

Well, if you want to get rid of the external type aliases you can provide a type lambda.

def t[T : ({type L[T]=Map[T,Int]})#L] = ???

  def t[T](implicit view: T => Map[T, Int])

Just to step back a little, we've found that APIs designed using view bounds can lead to surprises for users of the API, and the feature tends not be be used by experienced Scala programmers. So we feel that leaving in this shorthand for a questionable design pattern isn't the best thing for new users.

In the proposed deprecation,

Thanks for the pointer Jason, hadn't seen that PR. Recommending the implicit converter-function is a good and arguably more readable alternative.

Cheers,

√

 

we suggest you rewrite them as an implicit parameter, rather than as a context bound. Admittedly, it's a little boilerplatey, so you can use the type alias / context bound if you feel comfortable with it instead.

-jason

--

You received this message because you are subscribed to the Google Groups "scala-language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-languag...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Eric Tanter]

Thanks Jason for the general explanation and link to the thread on scala-internals. That's precisely what I was looking for.

I see that a few people there also argue in favor of nicer syntactic support for things like [T: _ => Int].

Anyway, I agree that the implicit parameter notation tends to be clearer.

The overhead of the notation is when one does not need to use the evidence, so maybe just having a better notation for these cases would be enough (and potentially even make context bounds themselves not that interesting anymore).

For instance, instead of:

def t[T](x:T)(implicit ev: T => Map[T, Int])

something like

def t[T](x:T)(T => Map[T, Int])

then, even the typical context view case:

def foo[T: Ordering](x: T) ...

would read

def foo[T](x:T)(Ordering[T])

which is not too bad, considering the conceptual simplification.

Has this been considered?


Cheers,

-- Éric

[√iktor Ҡlang]

On Thu, Sep 19, 2013 at 3:58 PM, Eric Tanter <eta...@dcc.uchile.cl> wrote:

Thanks Jason for the general explanation and link to the thread on scala-internals. That's precisely what I was looking for.

I see that a few people there also argue in favor of nicer syntactic support for things like [T: _ => Int].

Anyway, I agree that the implicit parameter notation tends to be clearer.

The overhead of the notation is when one does not need to use the evidence, so maybe just having a better notation for these cases would be enough (and potentially even make context bounds themselves not that interesting anymore).

For instance, instead of:

def t[T](x:T)(implicit ev: T => Map[T, Int])

something like

def t[T](x:T)(T => Map[T, Int])

then, even the typical context view case:

def foo[T: Ordering](x: T) ...

would read

def foo[T](x:T)(Ordering[T])

which is not too bad, considering the conceptual simplification.

Has this been considered?

TBH I'm not sure it'd pull its weight.

Cheers,

√

[Stephen Compall]

On Thu, 2013-09-19 at 09:53 -0300, Eric Tanter wrote:
> class Pair[T <% Comparable[T]]
> This would have to be replaced by the following?
> type ToComparable[T] = T => Comparable[T]
> class Pair[T : ToComparable]
> In which ways is that a better way to express one's intent than using
> a view bound?
>

It's not. Using a context bound instead of a view bound is about
choosing an abstraction that makes sense with context bounds, which will
almost inevitably be more elegant, general, and capable of expressing
more things. The abstraction you choose for use with context bounds
won't be the same as you used with view bounds -- it will be better.

In scala-library terms, for your example, instead of asking for an
implicit T => Comparable[T], as the view bound does, you ask for an
Ordering[T], as the context bound [T: Ordering] does. An Ordering[T]
takes *two* Ts and tells you how they compare.

The implicit conversion is an unnecessary step, and can only express
abstractions where you happen to have a T in hand, whereas the context
bound approach is entirely type-driven and can speak of relevant
functions independent of some specific value T. Consider:

trait Dionom[T] {
def concatenate(ts: List[T]): T
}

def emptiness[T: Dionom]: T =
implicitly[Dionom[T]].concatenate(List.empty)

What view bound on T could I use to express `emptiness'?

> Is there something inherently wrong/impossible with supporting something like
> T: C[A,B,_,D]?

Unfortunately, as so often happens when you make up syntax with _, that
already means something. :)

I would love syntax for type lambdas, but I'm not going to come up with
it.

--
Stephen Compall
^aCollection allSatisfy: [:each|aCondition]: less is better

[Eric Tanter]

Thanks Stephen,

Yes, I understand that context bounds give a more general and expressive. My question was more targeted at how to deal with deprecation of view bounds if I don't want to change my design.

I have one stylistic question on the example you give:

def emptiness[T: Dionom]: T =
implicitly[Dionom[T]].concatenate(List.empty)

The use of a context bound is generally described as a useful shorthand notation if one does need to use the implicit parameter. In your example above, it seems clearer to give the implicit parameter a name:

def emptiness[T](implicit x: Dionom[T]): T =
x.concatenate(List.empty)

But it's not the first time I see what you wrote, of using a context bound and then using `implicitly' to look up the actual value.

Is there a style recommendation regarding this point?

Thanks!

-- Éric

[Stephen Compall]

On Fri, 2013-09-20 at 09:43 -0300, Eric Tanter wrote:
> Yes, I understand that context bounds give a more general and
> expressive. My question was more targeted at how to deal with
> deprecation of view bounds if I don't want to change my design.

Ah, I see. I believe Jason Zaugg covered that.

> But it's not the first time I see what you wrote, of using a context
> bound and then using `implicitly' to look up the actual value.
>
> Is there a style recommendation regarding this point?

Definitely use whichever matches the style of the surrounding code, and
then, whichever is clearer. That's not always obvious; in this case,
the clearest solution is to leave the context bound in place, define a
function version of concatenate, and use that function instead of
directly calling the method.

--
Stephen Compall
"^aCollection allSatisfy: [:each | aCondition]": less is better than