Add reduce to Collection.

Add reduce to Collection.


BUG=
TEST=

Committed: https://code.google.com/p/dart/source/detail?r=10548

[Anders Johnsen, 2012-07-30 07:52:07]

Florian pointed out that we should consider changing this to foldLeft/foldRight.
However, Set is a Collection and is odd to associate with a direction.

[Sean Eagan, 2012-08-06 21:32:18]

On 2012/07/30 07:52:07, ajohnsen wrote:
> Florian pointed out that we should consider changing this to
foldLeft/foldRight.
> However, Set is a Collection and is odd to associate with a direction.

I would keep Collection#reduce and either add List#reduceRight or add
List#reverse (which would just return a wrapper as opposed to actually copying
the elements) allowing for:

list.reverse().reduce(0, add);

[Lasse Reichstein Nielsen, 2012-08-08 07:00:31]

The values should still be accessed in iteration order. That makes foldRight
harder to define efficiently (you'd probably use recursion to keep the earlier
values alive, and doing that on arbitrary collections would likely kill the
stack).

I agree with Sean - keep reduce here, and add reduceRight to the collections
where it makes sense - which is anything that can easily be iterated in reverse
order (List and perhaps OrderedSet).

[Lasse Reichstein Nielsen, 2012-08-08 07:19:14]

LGTM

https://chromiumcodereview.appspot.com/10832060/diff/1/corelib/src/collection...
File corelib/src/collection.dart (right):

https://chromiumcodereview.appspot.com/10832060/diff/1/corelib/src/collection...
corelib/src/collection.dart:17: * for each element [e] of this collection.
[:e:]. The 'e' is not referring to an existing variable in scope for the
function, so it's just a code expression, not a variable reference.

And <soapbox>I think 'map' should be a constructor, not a method!</soapbox>.
This function could return a lazy collection backed by the original, instead of
creating a new collection of unspecified type.

https://chromiumcodereview.appspot.com/10832060/diff/1/corelib/src/collection...
corelib/src/collection.dart:26: * Reduce the entire collection to one value
value, startign with [init]. To
"starting". This comment is not very descriptive - it just repeats the function
signature: function is called "reduce", it acts on a collection and an "init"
value and returns a single value. 
The rest is just an example, which is fine in addition to a description, but not
as a replacement.

How about:
Reduce a collection to a single value by iteratively combining each element of
the collection with an existing value using the provided function.
Use [initialValue] as the initial value, and the function [combine] to create a
new value from the previous one and an element.
<insert example>


Perhaps make the initialValue optional, and use the first element of the
collection if it isn't specified (e.g., use a unique private object as default
marker). That would need to throw a NoSuchElementException if the collection is
empty.

https://chromiumcodereview.appspot.com/10832060/diff/1/corelib/src/collection...
corelib/src/collection.dart:31: reduce(var init, f(var prev, E element));
Don't abbreviate:
  Object reduce(var initialValue, Object combine(var previousValue, E element));

https://chromiumcodereview.appspot.com/10832060/diff/1/corelib/src/implementa...
File corelib/src/implementation/collections.dart (right):

https://chromiumcodereview.appspot.com/10832060/diff/1/corelib/src/implementa...
corelib/src/implementation/collections.dart:10: class Collections {
This class should die. Horribly.
Instead there should be:
  class Collection<T> {
    factory Collection.from(Iterable<T> iterable);
    ...
  }
so instad of:
 Collections.forEach(iterable, f)
you do:
 new Collection.from(iterable).forEach(f);
for the *rare* case where all you have is an iterable.

https://chromiumcodereview.appspot.com/10832060/diff/1/corelib/src/implementa...
corelib/src/implementation/collections.dart:38: static reduce(Iterable iterable,
var init, f(prev, element)) {
Add return value, even if it's just Object. It differentiates it from a "void"
return type.
Also add "var" in front of "prev" and "element" and don't abbreviate variables
nemes.

https://chromiumcodereview.appspot.com/10832060/diff/1/corelib/src/implementa...
corelib/src/implementation/collections.dart:39: for (final e in iterable) {
Yes, that means using 'element' instead of 'e'. It won't hurt.

https://chromiumcodereview.appspot.com/10832060/diff/1/corelib/src/implementa...
File corelib/src/implementation/hash_map_set.dart (right):

https://chromiumcodereview.appspot.com/10832060/diff/1/corelib/src/implementa...
corelib/src/implementation/hash_map_set.dart:353: reduce(var init, f(var prev, E
element)) {
Return type, variable names unabbreviated.

https://chromiumcodereview.appspot.com/10832060/diff/1/runtime/lib/array.dart
File runtime/lib/array.dart (right):

https://chromiumcodereview.appspot.com/10832060/diff/1/runtime/lib/array.dart...
runtime/lib/array.dart:92: return Collections.reduce(this, init, f);
Same.

[Anders Johnsen, 2012-08-08 07:56:14]

PTAL

https://chromiumcodereview.appspot.com/10832060/diff/1/corelib/src/collection...
File corelib/src/collection.dart (right):

https://chromiumcodereview.appspot.com/10832060/diff/1/corelib/src/collection...
corelib/src/collection.dart:17: * for each element [e] of this collection.
On 2012/08/08 07:19:14, Lasse Reichstein Nielsen wrote:
> [:e:]. The 'e' is not referring to an existing variable in scope for the
> function, so it's just a code expression, not a variable reference.
> 
> And <soapbox>I think 'map' should be a constructor, not a method!</soapbox>.
> This function could return a lazy collection backed by the original, instead
of
> creating a new collection of unspecified type.

I'd like if we could resolve this in another CL. The change here is purely the
editor removing tailing whitespaces.

https://chromiumcodereview.appspot.com/10832060/diff/1/corelib/src/collection...
corelib/src/collection.dart:26: * Reduce the entire collection to one value
value, startign with [init]. To
On 2012/08/08 07:19:14, Lasse Reichstein Nielsen wrote:
> "starting". This comment is not very descriptive - it just repeats the
function
> signature: function is called "reduce", it acts on a collection and an "init"
> value and returns a single value. 
> The rest is just an example, which is fine in addition to a description, but
not
> as a replacement.
> 
> How about:
> Reduce a collection to a single value by iteratively combining each element of
> the collection with an existing value using the provided function.
> Use [initialValue] as the initial value, and the function [combine] to create
a
> new value from the previous one and an element.
> <insert example>
> 
> 
> Perhaps make the initialValue optional, and use the first element of the
> collection if it isn't specified (e.g., use a unique private object as default
> marker). That would need to throw a NoSuchElementException if the collection
is
> empty.

Agreed, this is a way better comment. Updated.

Creating it optional as you suggest is not ideal, since we still want the user
to be able to provide 'null' as a real initial value. If we have a nice way to
mark it as 'unprovided', I'd be happy to change it.

https://chromiumcodereview.appspot.com/10832060/diff/1/corelib/src/collection...
corelib/src/collection.dart:31: reduce(var init, f(var prev, E element));
On 2012/08/08 07:19:14, Lasse Reichstein Nielsen wrote:
> Don't abbreviate:
>   Object reduce(var initialValue, Object combine(var previousValue, E
element));

Returning Object is annoying since you have to 'cast' it to be able to use it.
Using var(non for return), the analyzer doesn't care and you can call whatever
you want on it.

https://chromiumcodereview.appspot.com/10832060/diff/1/corelib/src/implementa...
File corelib/src/implementation/collections.dart (right):

https://chromiumcodereview.appspot.com/10832060/diff/1/corelib/src/implementa...
corelib/src/implementation/collections.dart:38: static reduce(Iterable iterable,
var init, f(prev, element)) {
On 2012/08/08 07:19:14, Lasse Reichstein Nielsen wrote:
> Add return value, even if it's just Object. It differentiates it from a "void"
> return type.
> Also add "var" in front of "prev" and "element" and don't abbreviate variables
> nemes.

Adding var does not provide any further information and is orthogonal to the
rest of the lib. The only reason to provide it in the Collection interface is to
show that prev and element is typed differently. We don't have that type
information here.

https://chromiumcodereview.appspot.com/10832060/diff/1/corelib/src/implementa...
corelib/src/implementation/collections.dart:39: for (final e in iterable) {
On 2012/08/08 07:19:14, Lasse Reichstein Nielsen wrote:
> Yes, that means using 'element' instead of 'e'. It won't hurt.

It's using the style from the rest of the file/lib. If we want to style it
differently, we should consider doing it to the hole file/lib.

https://chromiumcodereview.appspot.com/10832060/diff/1/corelib/src/implementa...
File corelib/src/implementation/hash_map_set.dart (right):

https://chromiumcodereview.appspot.com/10832060/diff/1/corelib/src/implementa...
corelib/src/implementation/hash_map_set.dart:353: reduce(var init, f(var prev, E
element)) {
On 2012/08/08 07:19:14, Lasse Reichstein Nielsen wrote:
> Return type, variable names unabbreviated.

Done / see other comments.

https://chromiumcodereview.appspot.com/10832060/diff/1/runtime/lib/array.dart
File runtime/lib/array.dart (right):

https://chromiumcodereview.appspot.com/10832060/diff/1/runtime/lib/array.dart...
runtime/lib/array.dart:92: return Collections.reduce(this, init, f);
On 2012/08/08 07:19:14, Lasse Reichstein Nielsen wrote:
> Same.

Done / see other comments.

[Lasse Reichstein Nielsen, 2012-08-10 11:26:56]

LGTM

https://chromiumcodereview.appspot.com/10832060/diff/1/corelib/src/collection...
File corelib/src/collection.dart (right):

https://chromiumcodereview.appspot.com/10832060/diff/1/corelib/src/collection...
corelib/src/collection.dart:17: * for each element [e] of this collection.
Just fix the [:e:] while you are here, and it'll be fine.
You better get used to comments on surrounding code, even if it isn't yours :)

https://chromiumcodereview.appspot.com/10832060/diff/1/corelib/src/collection...
corelib/src/collection.dart:26: * Reduce the entire collection to one value
value, startign with [init]. To
"Nice" is such a loaded word :)
Let's drop it for now.
Since your argument is untyped, you could do:
 Object _UNSPECIFIED = const Object();
and use that as default.

https://chromiumcodereview.appspot.com/10832060/diff/1/corelib/src/collection...
corelib/src/collection.dart:31: reduce(var init, f(var prev, E element));
Accepted. Use Dynamic or var then.

https://chromiumcodereview.appspot.com/10832060/diff/1/corelib/src/implementa...
File corelib/src/implementation/collections.dart (right):

https://chromiumcodereview.appspot.com/10832060/diff/1/corelib/src/implementa...
corelib/src/implementation/collections.dart:38: static reduce(Iterable iterable,
var init, f(prev, element)) {
Accepted, but not liked.
I prefer being explicit about what is expected. It differentiates a deliberate
choice from an accidental omission.

https://chromiumcodereview.appspot.com/10832060/diff/1/corelib/src/implementa...
corelib/src/implementation/collections.dart:39: for (final e in iterable) {
We do. We shoud. Please start here :)

[Anders Johnsen, 2012-11-12 12:02:56]

https://codereview.chromium.org/10832060/diff/1/corelib/src/collection.dart
File corelib/src/collection.dart (right):

https://codereview.chromium.org/10832060/diff/1/corelib/src/collection.dart#n...
corelib/src/collection.dart:17: * for each element [e] of this collection.
On 2012/08/10 11:26:56, Lasse Reichstein Nielsen wrote:
> Just fix the [:e:] while you are here, and it'll be fine.
> You better get used to comments on surrounding code, even if it isn't yours :)

Done.

https://codereview.chromium.org/10832060/diff/1/corelib/src/collection.dart#n...
corelib/src/collection.dart:31: reduce(var init, f(var prev, E element));
On 2012/08/10 11:26:56, Lasse Reichstein Nielsen wrote:
> Accepted. Use Dynamic or var then.

Done.

https://codereview.chromium.org/10832060/diff/1/corelib/src/implementation/co...
File corelib/src/implementation/collections.dart (right):

https://codereview.chromium.org/10832060/diff/1/corelib/src/implementation/co...
corelib/src/implementation/collections.dart:10: class Collections {
On 2012/08/08 07:19:14, Lasse Reichstein Nielsen wrote:
> This class should die. Horribly.
> Instead there should be:
>   class Collection<T> {
>     factory Collection.from(Iterable<T> iterable);
>     ...
>   }
> so instad of:
>  Collections.forEach(iterable, f)
> you do:
>  new Collection.from(iterable).forEach(f);
> for the *rare* case where all you have is an iterable.

Agreed. I'll gladly create a CL for this in a weeks time!

https://codereview.chromium.org/10832060/diff/1/corelib/src/implementation/co...
corelib/src/implementation/collections.dart:39: for (final e in iterable) {
On 2012/08/10 11:26:56, Lasse Reichstein Nielsen wrote:
> We do. We shoud. Please start here :)

Done.