Is this ... heresy?

[Nils Kilden-Pedersen]

Several times I've had to produce a collection of something, iterate it for some purpose and then return it. One way to do that, would be like this:

def getFedMouthes(): Seq[Mouth] = {

val mouthes = mouthProducer.getThoseMouthes()

mouthes.foreach { mouth =>

mouth.feed(food.next)

mouth.clean(toothbrush) // Yeah, we're using the same tooth brush

}

mouthes

}

Now, that's all nice, but a little too verbose, so on occasion I've done this (and felt oddly weird about it):

def getFedMouthes(): Seq[Mouth] = mouthProducer.getThoseMouthes().map { mouth =>

mouth.feed(food.next)

mouth.clean(toothbrush)
mouth

}

Obviously I'm only saving 3 lines of code (in this example) and I'm getting worse runtime characteristics (which I can live with in the normal case).

Is this a flagrant abuse of map? I feel like it is, but I wanted to hear some feedback from those of you who are functional in the brain.

Maybe foreach should return the collection rather than Unit? (calm down, I know some of you get anger attacks when suggestions are made to change long standing and ubiquitous APIs, so I didn't really mean it).

[Daniel Spiewak]

Rather than getting into arguments about the aesthetic of the code (which I'll leave to someone else)…

What you're relying on here is that map is consecutive and sequential.  This is something you can generally rely on for non-parallel Seq, but you're technically not supposed to.  In theory, Seq is free to run the map iteration in any order that is convenient.  If that semantic changes (and it could), your code will unexpectedly break.

Daniel

[Eugene Burmako]

Iirc there's mapConserve which doesn't rebuild the collection if the transformation doesn't change any elements. I think that would remedy the runtime characteristics :)

[Nils Kilden-Pedersen]

On Thu, Apr 5, 2012 at 10:03 AM, Daniel Spiewak <djsp...@gmail.com> wrote:

Rather than getting into arguments about the aesthetic of the code (which I'll leave to someone else)…

What you're relying on here is that map is consecutive and sequential.  This is something you can generally rely on for non-parallel Seq, but you're technically not supposed to.  In theory, Seq is free to run the map iteration in any order that is convenient.  If that semantic changes (and it could), your code will unexpectedly break.

Are you saying that mapping a general Seq provides no guarantees (and shouldn't) about retaining order? That would seem counter-intuitive to me.

[Josh Suereth]

That is correct.   IF you want sequential behavior, you have to run:   foo.seq.map ....

[Josh Suereth]

You may want something like:

def getFedAndCleanedMouthes(): Seq[Mouth] =

   for {

      (mouth, food) <-  mouthProducer.hungryMouths zip foodProducer.makeFoods

      fedMouth = mouth feed food

      cleanMouth = mouth clean touthbrush

   } yield cleanMouth

Although the desugared code of that for expression isn't quite optimal yet, the look is there, IMHO.

[Paul Hudson]

On 5 April 2012 15:48, Nils Kilden-Pedersen <nil...@gmail.com> wrote:

Is this a flagrant abuse of map? I

Shouldn't you be flagrantly abusing a fold instead?

[Daniel Spiewak]

Order is guaranteed to be retained, but the order in which map traverses the sequence is not guaranteed.  Thus:

Seq(1, 2, 3) map { i => println(i); i }           // => Seq(1, 2, 3)

In the above expression, the only thing that is guaranteed is that the result will be Seq(1, 2, 3).  You may see the numbers printed as "2, 3, 1", "3, 1, 2" or any other permutation.  Practically speaking, all of the Seq implementations will traverse in order, and so you will always see "1, 2, 3" (which is why your code works at all).  This traversal order is the semantic you cannot rely upon.

Daniel

[Tom Switzer]

Well, what your example reminds me of is Kestrels, from To Mock a Mocking Bird [1] (Debasish has blogged about this before [2]). In Scala, you may define the Kestrel combinator like this:

def kestrel[A,B,C](f: A => B, g: B => C): A => B = a => {

  val b = f(a)

  g(b)

  b

}

For your particular use case, this isn't too useful. You may want to define something like Ruby's tap:

def tap[A,B](a: A, f: A => B): A = kestrel(identity[A], f)(a)

Then you can,

tap(mouthProducer.getThoseMouths(), _ foreach { mouth =>

  // ...

})

You could make it more Ruby-like by enriching Any,

implicit def tapAny[A](a: A) = new {

  def tap[B](f: A => B): A = tap(a, f)

}

mouthProducer.getThoseMouths().tap (_ foreach {

  // ...

})

[1] http://www.amazon.com/To-Mock-Mockingbird-Raymond-Smullyan/dp/0192801422/ref=sr_1_1?ie=UTF8&qid=1333638968&sr=8-1

[2] http://debasishg.blogspot.ca/2009/09/side-effects-with-kestrel-in-scala.html

Cheers,

Tom

[Josh Suereth]

eh?  It doesn't guarantee traveral order on anything that'd not a Seq, but for a subclass of Seq that has a well-defined "order" to elements, .seq will make it both synchronous and in-order.   Not sure why you thought it didn't....

On Thu, Apr 5, 2012 at 11:24 AM, Daniel Spiewak <djsp...@gmail.com> wrote:

That is correct.   IF you want sequential behavior, you have to run:   foo.seq.map ....

Even foo.seq.map does not guarantee traversal order, only synchronicity and result order.

Daniel

[Josh Suereth]

Ah, I may be confusing foreach with map, but I didn't think I was....

[Luke Vilnis]

This seems really weird. As I understand it, "for" is translated into map/flatmap/filter. Does this also mean that Scala's "for" loop doesn't give guarantees about sequentiality for, say, List? That seems vaguely bonkers.

On Thu, Apr 5, 2012 at 11:28 AM, Josh Suereth <joshua....@gmail.com> wrote:

[Josh Suereth]

No, you're off-base here Daniel.  .seq makes it sequential and synchronous.

[Daniel Spiewak]

There's nothing in the contract of map that says anything about traversal order, only result order.  The foreach function has a guaranteed traversal order, but map does not, even on sequences.  I have often thought that this could be exploited in certain trie-based sequences to improve better performance, but I haven't spent much time thinking in that direction.

Daniel

[Daniel Spiewak]

for is translated into foreach unless you have a yield clause.  Don't put side effects into your for-comprehensions; the results will surprise you.

Daniel

[Josh Suereth]

List happens to be, because it's a Sequence and *not* a parallel collection.

Parallel collections have thier map/flatMap/filter operations evaluated in parallel (i.e. not sequential).   But the result preserves the sequential ordering.

calling .seq on a parallel collection returns you to non-parallel behavior.

Also, collections with no deifned ordering (like Map/Set) don't have to abide by any rules in how their map/filter/flatMap operate.

[Daniel Spiewak]

That would surprise me.  It would make Scala the only collections library that makes a hard guarantee about the traversal order of the map function.

Daniel

[Josh Suereth]

While that's true, if you were to do that in Scala's collections library, expect to break things.

- Josh

[Daniel Sobral]

On Thu, Apr 5, 2012 at 12:23, Daniel Spiewak <djsp...@gmail.com> wrote:
> Order is guaranteed to be retained, but the order in which map traverses the
> sequence is not guaranteed.  Thus:
>
> Seq(1, 2, 3) map { i => println(i); i }           // => Seq(1, 2, 3)
>
> In the above expression, the only thing that is guaranteed is that the
> result will be Seq(1, 2, 3).  You may see the numbers printed as "2, 3, 1",
> "3, 1, 2" or any other permutation.  Practically speaking, all of the Seq
> implementations will traverse in order, and so you will always see "1, 2, 3"
> (which is why your code works at all).  This traversal order is the semantic
> you cannot rely upon.

Let me make something clear before things get too confused: the above
example will ALWAYS print 1, 2, 3. Seq is guaranteed not to be
parallel. It is GenSeq that allows the behavior described.

--
Daniel C. Sobral

I travel to the future all the time.

[Luke Vilnis]

LINQ's "Select" for IEnumerable absolutely traverses in-order, I don't know where you're getting this "only" idea, or what you mean by "hard".

[Daniel Sobral]

On Thu, Apr 5, 2012 at 12:24, Daniel Spiewak <djsp...@gmail.com> wrote:
>
>> That is correct.   IF you want sequential behavior, you have to run:
>> foo.seq.map ....
>
>

> Even foo.seq.map does not guarantee traversal order, only synchronicity and
> result order.

On the contrary. Guaranteeing traversal order is precisely what ".seq" does.

[Daniel Spiewak]

If we're going to make that assumption, then it needs to be documented.  As I said, there is absolutely nothing in the contract of map (on Seq or GenSeq) that says anything about traversal order, only synchronicity and result order.

Daniel

[Daniel Spiewak]

.seq guarantees single-threadedness.  In practice it also provides traversal order.  I don't see any documentation to the effect that it guarantees traversal order.

Daniel

[Josh Suereth]

It seems the documentation in the scaladocs is lacking.  That's something we can correct.

[Daniel Spiewak]

Well, as someone who implements data structures, that sort of information might be considered important.  :-)  Duly filed…

Daniel

[Daniel Sobral]

On Thu, Apr 5, 2012 at 12:30, Luke Vilnis <lvi...@gmail.com> wrote:
> This seems really weird. As I understand it, "for" is translated into
> map/flatmap/filter. Does this also mean that Scala's "for" loop doesn't give
> guarantees about sequentiality for, say, List? That seems vaguely bonkers.

It does. It absolutely does. Every Seq guarantees traversal order.
GenSeq and ParSeq do not (a GenSeq may be either a Seq or a ParSeq).

And since we are speaking of sequentiality, Seq guarantees elements
are kept in such an order that let you refer to them by an index. Set,
Map, Iterable and Traversable do not offer this guarantee -- one can't
say that element x comes before or after element y (LinkedHashMap and
ListMap are exceptions to this rule). At any rate, this guarantee --
that you can say that some element comes before another -- is a
different guarantee than traversal order. A ParSeq does not guarantee
traversal order, while still being able to distinguish which element
comes first.

>
> On Thu, Apr 5, 2012 at 11:28 AM, Josh Suereth <joshua....@gmail.com>
> wrote:
>>
>> eh?  It doesn't guarantee traveral order on anything that'd not a Seq, but
>> for a subclass of Seq that has a well-defined "order" to elements, .seq will
>> make it both synchronous and in-order.   Not sure why you thought it
>> didn't....
>>
>>
>> On Thu, Apr 5, 2012 at 11:24 AM, Daniel Spiewak <djsp...@gmail.com>
>> wrote:
>>>
>>>
>>>> That is correct.   IF you want sequential behavior, you have to run:
>>>> foo.seq.map ....
>>>
>>>
>>> Even foo.seq.map does not guarantee traversal order, only synchronicity
>>> and result order.
>>>
>>> Daniel
>>
>>
>

--

[Josh Suereth]

Just go look at the implementation.   All of the foreach-based abstractions (GenTraversableOnce + friends) use .seq to make that code *work*.   If you don't abide by the 'seq means ordered + synchronous' contract, you break it.

NOW, if you're providing your own collection, you can just fix all those other methods to work the way they should.  As long as your foreach abides by the contract for .seq you can do whatever you want in map.

So, you do have a point, even if it doesn't apply to the current collections library.

This is of course a big digression from the original question :)

- Josh

[Daniel Sobral]

On Thu, Apr 5, 2012 at 12:32, Daniel Spiewak <djsp...@gmail.com> wrote:
> There's nothing in the contract of map that says anything about traversal
> order, only result order.  The foreach function has a guaranteed traversal
> order, but map does not, even on sequences.  I have often thought that this
> could be exploited in certain trie-based sequences to improve better
> performance, but I haven't spent much time thinking in that direction.

That guarantee did not exist, but when parallel collections were added
to the mix, it came to be, as we discovered lots of code depended on
it.

>
> Daniel
>
>
> On Thu, Apr 5, 2012 at 10:28 AM, Josh Suereth <joshua....@gmail.com>
> wrote:
>>
>> eh?  It doesn't guarantee traveral order on anything that'd not a Seq, but
>> for a subclass of Seq that has a well-defined "order" to elements, .seq will
>> make it both synchronous and in-order.   Not sure why you thought it
>> didn't....
>>
>>
>> On Thu, Apr 5, 2012 at 11:24 AM, Daniel Spiewak <djsp...@gmail.com>
>> wrote:
>>>
>>>
>>>> That is correct.   IF you want sequential behavior, you have to run:
>>>> foo.seq.map ....
>>>
>>>
>>> Even foo.seq.map does not guarantee traversal order, only synchronicity
>>> and result order.
>>>
>>> Daniel
>>
>>
>

--

[Daniel Sobral]

On Thu, Apr 5, 2012 at 12:44, Josh Suereth <joshua....@gmail.com> wrote:
> Just go look at the implementation.   All of the foreach-based abstractions
> (GenTraversableOnce + friends) use .seq to make that code *work*.   If you
> don't abide by the 'seq means ordered + synchronous' contract, you break it.

I'm not much of a fan of source-code-based requirements, but there's a
bigger issue here. When parallel collections were added to the mix,
and Seq could suddenly be a ParSeq, things broke. They did not break
because stuff was happening in parallel (though there's certainly
potential for that too), they broke because things were not happening
in an expected order.

I looked over the docs right now and I couldn't find any reference to
what Gen* guarantees or not, and how Traversable&children are expected
to work, and I think it is very important that it does.

[Josh Suereth]

Yes, we need to fix the docs.  No question there.

[Daniel Spiewak]

That is correct.   IF you want sequential behavior, you have to run:   foo.seq.map ....

Even foo.seq.map does not guarantee traversal order, only synchronicity and result order.

Daniel

[Nils Kilden-Pedersen]

On Thu, Apr 5, 2012 at 10:23 AM, Daniel Spiewak <djsp...@gmail.com> wrote:

Order is guaranteed to be retained, but the order in which map traverses the sequence is not guaranteed. 

AHA! 

Or rather, reading the rest of the posts, I can't figure out if that is in fact true. Regardless, it ought to be true, so I'm now convinced to stop such heretic coding.

Thanks.

[Daniel Spiewak]

Or rather, reading the rest of the posts, I can't figure out if that is in fact true. Regardless, it ought to be true, so I'm now convinced to stop such heretic coding.

It ought to be true, but it is not.  Or rather, it is true that map makes no such guarantee, but the implementation does (and makes that assumption).  It sounds like the documentation will be updated to reflect the stronger guarantees of map.

So in other words, you can rely on iteration order after all.

Daniel

[Josh Suereth]

I'd still use "zip" in the future.  It's safest and then you can swap to parallel collections later.

- Josh

[Nils Kilden-Pedersen]

It sounds like it's exactly such assumptions that has caused that guarantee to be put in place, so I'd rather not.

[Tony Morris]

IEnumerable is very different to Seq.

[Luke Vilnis]

Meh, true, but given that it's one of the only immutable data structures used much in .NET, since C# lacks the rich fine-grained immutable collections of Scala, it's the closest equivalent. I assume what you're saying is that IEnumerable doesn't only get implemented by sequential data structures, so it's much more like Iterable in Scala terms? Still, when implemented for sequential data structures, IEnumerable's Select (map) is expected to traverse in the obvious order (in my experience).

[Bakos Gábor]

On 2012.04.06. 5:41, Luke Vilnis wrote:
> Meh, true, but given that it's one of the only immutable data structures
> used much in .NET, since C# lacks the rich fine-grained immutable
> collections of Scala, it's the closest equivalent. I assume what you're
> saying is that IEnumerable doesn't only get implemented by sequential
> data structures, so it's much more like Iterable in Scala terms? Still,
> when implemented for sequential data structures, IEnumerable's Select
> (map) is expected to traverse in the obvious order (in my experience).

Sorry for the off-topic.

I do not think it has guaranteed order, see:
http://msdn.microsoft.com/en-us/library/dd460714.aspx
Yes, AsParallel
(http://msdn.microsoft.com/en-us/library/dd413237.aspx)'s ParallelQuery
is an IEnumerable:
http://msdn.microsoft.com/en-us/library/dd383736.aspx

[Luke Vilnis]

If you'll note I said "when implemented for sequential data structures". Calling AsParallel wraps the structure in a ParallelEnumerable, which is definitely not a sequential data structure. Calls to Select and friends will be run out of order on the new, non-sequential data structure - not on the underlying one. If you wrap a sequential data structure in a ParallelEnumerable, it will not magically de-sequential-ize it. You still need to call "MoveNext" to get any item, and the order in which items are returned by MoveNext will not be changed. For example, think about code inside a method that uses "yield" - that code will be executed sequentially, and the items returned in the same order, no matter what. 

Anyhow to bring it back on topic, my initial reason for mentioning LINQ was just to give a .NET programmers perspective on the notion that you can't rely on streams to execute in-order, which in my opinion seemed baffling and not in line with the way LINQ to Objects is used and taught (for example, here's a blog post by a Microsoft employee showing how to debug LINQ statements by inserting print statements that implicitly assumes in-order is guaranteed). Buuut this issue has already been cleared up so I'm not sure why anyone's still talking about it.

2012/4/6 Bakos Gábor <abor...@gmail.com>

[Tony Morris]

IEnumerable is not immutable.

[Tony Morris]

It's also not type-safe. IEnumerable.Select is subject to different
reasoning as a consequence of being mutable. Indeed, under any type
system that enforces these differences, IEnumerable.Select does not
correspond to map at all and Functor.map with a side-effecting argument
in Scala corresponds to traverse (Essence of the Iterator Pattern), not
map. That Scala conflates map and traverse ensures these topics in their
general form dominate discussion.

By the way, C# does have all the immutable structures of Scala and many
more -- I wrote them.

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

[nafg]

It's a bit ironic, that at least in my digest emails of this thread, the replies do not seem to be very sequential! Sometimes messages quote other messages that occur further down.