Add Collection#reduce

[DartBot]

This issue was originally filed by @seaneagan

---

see http://en.wikipedia.org/wiki/Fold_(higher-order_function)

As with the other higher-order Collection methods, would be good to be consistent with JavaScript method names, and JavaScript has Array#reduce.

Similar to Collection#map (issue #945), this really wants to be a generic method (issue #254). The contract of this method could be something like:

R reduce<R>(R callback(R prev, E curr), [R initial = _somePrivateValue]) {
  Iterator iter = iterator();
  if(initial === _somePrivateValue) { // initial value not passed
    if(!iter.hasNext()) return null; // no items either
    initial = iter.next(); // defaults to first item
  }
  R prev = initial;
  while(iter.hasNext()) prev = callback(prev, iter.next());
  return prev;
}

[anders-sandholm]

Added Area-Library, Triaged labels.

[andersjohnsen]

This was added some time ago, parameters swapped :)

• Anders

  ---

  Set owner to @Skabet.
  Added Fixed label.

[DartBot]

This comment was originally written by @seaneagan

---

Oh, I didn't realize the parameters were swapped. Now there will be no way
to make the initialValue optional, defaulting to the first value in the
Iterable as in JavaScript, Ruby, Python, etc. :(

[andersjohnsen]

That's exactly why it's not optional. There are a few potential default values:

• null
• first element

And then, what if there are only one element, should that just be the return value? And would the behaviour then change if a value is given?

We could maybe look into adding 'fold' that does what you suggest?

• Anders

[DartBot]

This comment was originally written by @seaneagan

---

See http://en.wikipedia.org/wiki/Reduce_(higher-order_function)

There are many languages that have a single method with an optional initial
value. All of these (except PHP which doesn't count :) ) use the first
element as the default initial value. And the ones I checked all throw
when there is no initial value and the list is empty:

http://docs.python.org/2/library/functions.html#reduce
https://developer.mozilla.org/en-US/docs/JavaScript/Reference/Global_Objects/Array/Reduce

There were only a few which use 2 separate methods, one with an initial
value, and one which uses the first element as the initial value:

Haskell
Scala
Smalltalk

... possibly due to their stronger type systems (e.g. generic methods).

[andersjohnsen]

Reduce was added with map-reduce in mind(http://en.wikipedia.org/wiki/MapReduce). There it's quite rare that the return-value and the list-value is of the same type, making the 'first-value as initial-value'-pattern non fitting in.

Looking at the link you sent, the reduce you describe is frequently named 'fold'. Why not use the name 'fold', then both methods could co-exist?

[DartBot]

This comment was originally written by @seaneagan

---

I think functional programming's map and reduce are slightly different than
MapReduce's Map and Reduce, and quite often the type is the same as in
sum, product, min, max. But nonetheless I could certainly live with two
separate methods. As far as I know fold and reduce are synonyms, so I'm
not sure which name would correspond to which method.

[DartBot]

This comment was originally written by mailto...@gmail.com

---

Reduce, as far as I know, does what the proposed reduce does when no initial value is given:
It starts with the first element and produces a result of the same type as the list elements.
It "reduces" the collection to a single value.
Fold works with an initial value that can be of any type, and constitutes the result type.
So the collection is "folded" into some result.
The result can be a collection again, as the function given to fold must not necessarily be a sum or product operation.

In Scala, if have rarely used reduce, but I fold a collection into a different type quite often.

[lrhn]

The reduce we have in Dart is an implementation of the classical foldl function on Lisp-like lists (which is pretty much what Iterable corresponds to). It has the advantage over foldr that it runs in constant space.
It's also as generic as possible by not requiring any elements in the Iterable and not requiring the initial value/return type to be related to the element type of the iterable.

That also means that it can be extra verbose for cases where you you just want to apply a binary operation over the element type to a non-empty Iterable. Or unusable if your binary operations doesn't have a unit.
In ECMAScript (and many other languages), the reduce function will default to using the first element as initial value and iterate over the rest if no initial value is provided.
We decided against that. It is really two different functions which can be typed differently (so yes, typing is a reason to prefer two functions to one), and if we have them both, they deserve (and need) different names.

So, I'm not opposed to having a separate function that doesn't take a separate initial value and instead uses the first value, and that necessarily throws on an empty iterable.
For naming, I'm split. I grew up on Scheme and SML, so would in that light perhaps have preferred "fold" for what we have now. But Dart as a language is more influenced by Java and JavaScript, so the name "reduce" from JavaScript (and other imperative languages[1]) is the better choice.
That still leaves us without a name for the other half of JavaScript's reduce.

/L
[1] http://en.wikipedia.org/wiki/Fold_(higher-order_function)

[DartBot]

This comment was originally written by @seaneagan

---

I think if it has to be different than JavaScript (i.e. 2 separate
methods), then maybe use different names than JavaScript:

fold(initialValue, combine(previous, E next));
E collapse(E combine(E previous, E next)); // opposite of "expand"

[DartBot]

This comment was originally written by mail...@gmail.com

---

I am fine with 'fold' and 'collapse', but as 'reduce' is already established and interpreted in the sense of "map/reduce", it may be worth to keep that.

So 'collapse' seems good as an addition, and the name describes what it does IMHO, even in contrast to 'reduce'.

But, please, do NOT declare collapse as being the "opposite of expand", as "expand" (also known as 'bind' or 'flatMap' outside Dart) is a totally different beast.

Best explained: You can't do
neither:

mylist.collapse(...).expand(...) as collapse does not result in a list, but a single value, so expand is not defined on the result (except E might be List casually).

nor:

assert mylist.expand(...).collapse(...) == mylist
as again collapse would result in a single value of the element type and not the original list.

Please refer to the dart-misc mailing list thread titled "Improving the list API" for following the debate around expand:

https://groups.google.com/a/dartlang.org/forum/?fromgroups=#!searchin/misc/Improving$20the$20list$20API/misc/gk788UaAc-A/1o53wB-x6K0J