## digitalmars.D - reduce -> fold?

• Andrei Alexandrescu (8/8) Jan 29 2016 As has been discussed before there's been discussion about
• Adrian Matoga (7/15) Jan 29 2016 YES!
• =?UTF-8?B?THXDrXM=?= Marques (6/8) Jan 29 2016 Just to bikeshed a little, I remember that when I first started
• Dragos Carp (9/13) Jan 29 2016 But not in python, where "accumulate"[1] is the generic
• =?UTF-8?B?THXDrXM=?= Marques (3/11) Jan 29 2016 Fair enough. Yes, that is indeed a useful algorithm, so please do
• Andrei Alexandrescu (3/14) Jan 29 2016 That'd be interesting if (a) lazy and (b) general a la
• Dragos Carp (10/12) Feb 01 2016 To be clear, by general you mean to allow functions with more
• Andrei Alexandrescu (7/18) Feb 03 2016 My ambitions were lower :o). I was thinking of supporting any operation,...
• Walter Bright (3/5) Feb 03 2016 Erik Meijer lists a lot of interesting things that can be done with fold...
• Dragos Carp (7/33) Feb 04 2016 Good that I asked. Contrary to "reduce", "recurrence" works also
• John Colvin (4/23) Feb 04 2016 I wrote a bit about this sort of thing here:
• Timon Gehr (3/14) Jan 30 2016 "scan"
• Andrei Alexandrescu (2/8) Jan 29 2016 Good point, thanks! -- Andrei
• Walter Bright (4/9) Jan 29 2016 Given the different names for this used in different languages, I sugges...
• Walter Bright (3/6) Jan 29 2016 For algorithms and FP in general, we may be better off drawing inspirati...
• Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= (2/10) Jan 29 2016 So D is adding currying and builtin tuples? :^)
• deadalnix (3/4) Jan 29 2016 Yes. Come back in 10 years it'll be ready for you.
• Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= (13/17) Jan 30 2016 Currying is pointless, I believe Swift is removing it. I was
• Xinok (10/11) Jan 30 2016 It might be fairly useless in D but it's definitely not useless
• Andrei Alexandrescu (3/12) Jan 30 2016 I forgot the distinction between currying and partial application. Can
• David Nadlinger (11/13) Jan 30 2016 Currying is turning (A, B, C) -> D into A -> (B -> (C -> D)),
• Andrei Alexandrescu (3/15) Feb 02 2016 Thanks. I guess it'd be nice to have it on code.dlang.org somewhere so
• Jakob Ovrum (9/19) Feb 10 2016 I'm late to the party, but I wrote these novetly tidbits a few
• bachmeier (6/9) Jan 30 2016 I'm sure others can give an informed answer on the distinction,
• Vladimir Panteleev (4/12) Jan 29 2016 I'm not sure what the problem was, but the documentation for
• Y (3/12) Jan 29 2016 Yes yes yes please!
• ixid (3/12) Jan 29 2016 Absolutely yes!
• wobbles (3/12) Jan 29 2016 I think yes. Took me ages to realise the difference with reduce.
• Brad Anderson (9/18) Jan 29 2016 +1
• Edwin van Leeuwen (4/8) Jan 29 2016 Interestingly, that pull request links to another pull request
• Walter Bright (7/15) Jan 29 2016 Haskell can provide us with good inspiration and background for designin...
• Walter Bright (2/3) Jan 29 2016 foldr could be done with reverse.fold
• bachmeier (4/9) Jan 29 2016 Once you use names like foldl and foldr, you're headed down the
• Chris Wright (6/18) Jan 29 2016 For my own sake, I don't care at all. I've seen this announcement, I'll
• Atila Neves (4/13) Feb 02 2016 Definitely yes.
• Andrei Alexandrescu (2/16) Feb 02 2016 Atila, wanna do the honors? -- Andrei
• Atila Neves (4/26) Feb 02 2016 If it's not urgent, sure.
• Andrei Alexandrescu (2/22) Feb 02 2016 Thanks! And don't forget: in D, everything is top priority. -- Andrei
• Atila Neves (7/37) Feb 03 2016 Of course it is ;)
• Andrei Alexandrescu (3/6) Feb 03 2016 If by the old one you mean the valiant effort to overload reduce, forget...
• Atila Neves (8/17) Feb 03 2016 Ah, yes. That definitely makes more sense than me writing one
• Timon Gehr (5/8) Feb 03 2016 Returning Unqual!(ElementType!R).init makes no sense though.
• John Colvin (4/16) Feb 03 2016 I wish we had some standardised way to express what the
• Atila Neves (25/37) Feb 04 2016 Right. I wrote in a hurry and without checking the code I'd
• Timon Gehr (2/23) Feb 04 2016 My point was more that the .init value is often not the value you want.
• Atila Neves (3/21) Feb 29 2016 Got one LGTM already, just need someone else to look over it.
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
```As has been discussed before there's been discussion about
std.algorithm.reduce taking the "wrong" order of arguments (its
definition predates UFCS). I recall the conclusion was there'd be subtle
ambiguities if we worked reduce to implement both orders.

So the next best solution is to introduce a new name such as the popular
"fold", and put them together in the documentation.

Thoughts?

Andrei
```
Jan 29 2016
```On Friday, 29 January 2016 at 12:08:01 UTC, Andrei Alexandrescu
wrote:
As has been discussed before there's been discussion about
std.algorithm.reduce taking the "wrong" order of arguments (its
definition predates UFCS). I recall the conclusion was there'd
be subtle ambiguities if we worked reduce to implement both
orders.

So the next best solution is to introduce a new name such as
the popular "fold", and put them together in the documentation.

Thoughts?

YES!

There was a topic on this [1] and some implementation proposed.
I'm not sure if it was the only one.

[1]
http://forum.dlang.org/post/sqbizjwcyavbrxwagnwl forum.dlang.org
```
Jan 29 2016
=?UTF-8?B?THXDrXM=?= Marques <luis luismarques.eu> writes:
```On Friday, 29 January 2016 at 12:08:01 UTC, Andrei Alexandrescu
wrote:
So the next best solution is to introduce a new name such as
the popular "fold", and put them together in the documentation.

Just to bikeshed a little, I remember that when I first started
using std.algorithm I was ctrl-F'ing for "accumulate" and not
finding it quite often. D competes with C++ directly, so do
consider that name :-)
```
Jan 29 2016
Dragos Carp <dragoscarp gmail.com> writes:
```On Friday, 29 January 2016 at 13:11:34 UTC, Luís Marques wrote:
Just to bikeshed a little, I remember that when I first started
using std.algorithm I was ctrl-F'ing for "accumulate" and not
finding it quite often. D competes with C++ directly, so do
consider that name :-)

But not in python, where "accumulate"[1] is the generic
equivalent of C++ "partial_sum"[2]. I like "fold" more.

BTW this week, a colleague of mine implemented a python
"accumulate" in D. Is there any interest to contribute it to
Phobos? How should this be named?

[1]
https://docs.python.org/3/library/itertools.html#itertools.accumulate
[2] http://en.cppreference.com/w/cpp/algorithm/partial_sum
```
Jan 29 2016
=?UTF-8?B?THXDrXM=?= Marques <luis luismarques.eu> writes:
```On Friday, 29 January 2016 at 13:56:48 UTC, Dragos Carp wrote:
But not in python, where "accumulate"[1] is the generic
equivalent of C++ "partial_sum"[2]. I like "fold" more.

BTW this week, a colleague of mine implemented a python
"accumulate" in D. Is there any interest to contribute it to
Phobos? How should this be named?

[1]
https://docs.python.org/3/library/itertools.html#itertools.accumulate
[2] http://en.cppreference.com/w/cpp/algorithm/partial_sum

Fair enough. Yes, that is indeed a useful algorithm, so please do
contribute. I won't bikeshed on that other name, heh.
```
Jan 29 2016
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
```On 01/29/2016 08:56 AM, Dragos Carp wrote:
On Friday, 29 January 2016 at 13:11:34 UTC, Luís Marques wrote:
Just to bikeshed a little, I remember that when I first started using
std.algorithm I was ctrl-F'ing for "accumulate" and not finding it
quite often. D competes with C++ directly, so do consider that name :-)

But not in python, where "accumulate"[1] is the generic equivalent of
C++ "partial_sum"[2]. I like "fold" more.

BTW this week, a colleague of mine implemented a python "accumulate" in
D. Is there any interest to contribute it to Phobos? How should this be
named?

[1] https://docs.python.org/3/library/itertools.html#itertools.accumulate
[2] http://en.cppreference.com/w/cpp/algorithm/partial_sum

That'd be interesting if (a) lazy and (b) general a la
https://dlang.org/library/std/range/recurrence.html. -- Andrei
```
Jan 29 2016
Dragos Carp <dragoscarp gmail.com> writes:
```On Friday, 29 January 2016 at 20:40:18 UTC, Andrei Alexandrescu
wrote:
That'd be interesting if (a) lazy and (b) general a la
https://dlang.org/library/std/range/recurrence.html. -- Andrei

To be clear, by general you mean to allow functions with more
than 2 arguments?

For example if you have:

foo(int i, int j, int k) { return i + j + k; }

then:

scan!foo([1, 2, 3, 4]).array returns [1, 2, 6, 12]

Is "scan" (thanks Timon) telling enough? The python "accumulate"
conflicts with the C++ meaning.
```
Feb 01 2016
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
```On 02/01/2016 03:46 AM, Dragos Carp wrote:
On Friday, 29 January 2016 at 20:40:18 UTC, Andrei Alexandrescu wrote:
That'd be interesting if (a) lazy and (b) general a la
https://dlang.org/library/std/range/recurrence.html. -- Andrei

To be clear, by general you mean to allow functions with more than 2
arguments?

My ambitions were lower :o). I was thinking of supporting any operation,
not only summation.

For example if you have:

foo(int i, int j, int k) { return i + j + k; }

then:

scan!foo([1, 2, 3, 4]).array returns [1, 2, 6, 12]

Is "scan" (thanks Timon) telling enough? The python "accumulate"
conflicts with the C++ meaning.

That's a sliding window of compile-time-known size, which is interesting
on its own. There are several ways to handle the limits, each useful in
certain situations. I don't get where 12 comes from in your example.

Andrei
```
Feb 03 2016
Walter Bright <newshound2 digitalmars.com> writes:
```On 2/3/2016 8:39 AM, Andrei Alexandrescu wrote:
My ambitions were lower :o). I was thinking of supporting any operation, not
only summation.

Erik Meijer lists a lot of interesting things that can be done with fold:

https://channel9.msdn.com/Series/C9-Lectures-Erik-Meijer-Functional-Programming-Fundamentals/C9-Lectures-Dr-Erik-Meijer-Functional-Programming-Fundamentals-Chapter-7-of-13
```
Feb 03 2016
Dragos Carp <dragoscarp gmail.com> writes:
```On Wednesday, 3 February 2016 at 16:39:26 UTC, Andrei
Alexandrescu wrote:
On 02/01/2016 03:46 AM, Dragos Carp wrote:
On Friday, 29 January 2016 at 20:40:18 UTC, Andrei
Alexandrescu wrote:
That'd be interesting if (a) lazy and (b) general a la
https://dlang.org/library/std/range/recurrence.html. -- Andrei

To be clear, by general you mean to allow functions with more
than 2
arguments?

My ambitions were lower :o). I was thinking of supporting any
operation, not only summation.

Good that I asked. Contrary to "reduce", "recurrence" works also
with functions with more than 2 arguments, so I saw it as a hint
in this direction.

For example if you have:

foo(int i, int j, int k) { return i + j + k; }

then:

scan!foo([1, 2, 3, 4]).array returns [1, 2, 6, 12]

Is "scan" (thanks Timon) telling enough? The python
"accumulate"
conflicts with the C++ meaning.

That's a sliding window of compile-time-known size, which is
interesting on its own. There are several ways to handle the
limits, each useful in certain situations. I don't get where 12

I calculated Yn = fct(Yn-2, Yn-1, Xn) thus Y3 = 2 + 6 + 4 == 12

I will prepare a PR for the binary function implementation.
```
Feb 04 2016
Dragos Carp <dragoscarp gmail.com> writes:
```On Thursday, 4 February 2016 at 08:29:46 UTC, Dragos Carp wrote:
I will prepare a PR for the binary function implementation.

The PR is ready for review:
https://github.com/D-Programming-Language/phobos/pull/3972
```
Feb 04 2016
John Colvin <john.loughran.colvin gmail.com> writes:
```On Friday, 29 January 2016 at 20:40:18 UTC, Andrei Alexandrescu
wrote:
On 01/29/2016 08:56 AM, Dragos Carp wrote:
On Friday, 29 January 2016 at 13:11:34 UTC, Luís Marques wrote:
[...]

But not in python, where "accumulate"[1] is the generic
equivalent of
C++ "partial_sum"[2]. I like "fold" more.

BTW this week, a colleague of mine implemented a python
"accumulate" in
D. Is there any interest to contribute it to Phobos? How
should this be
named?

[1]
https://docs.python.org/3/library/itertools.html#itertools.accumulate
[2] http://en.cppreference.com/w/cpp/algorithm/partial_sum

That'd be interesting if (a) lazy and (b) general a la
https://dlang.org/library/std/range/recurrence.html. -- Andrei

https://github.com/D-Programming-Language/phobos/pull/2991#issuecomment-141816906
```
Feb 04 2016
Timon Gehr <timon.gehr gmx.ch> writes:
```On 01/29/2016 02:56 PM, Dragos Carp wrote:
On Friday, 29 January 2016 at 13:11:34 UTC, Luís Marques wrote:
Just to bikeshed a little, I remember that when I first started using
std.algorithm I was ctrl-F'ing for "accumulate" and not finding it
quite often. D competes with C++ directly, so do consider that name :-)

But not in python, where "accumulate"[1] is the generic equivalent of
C++ "partial_sum"[2]. I like "fold" more.

BTW this week, a colleague of mine implemented a python "accumulate" in
D. Is there any interest to contribute it to Phobos? How should this be
named?

[1] https://docs.python.org/3/library/itertools.html#itertools.accumulate
[2] http://en.cppreference.com/w/cpp/algorithm/partial_sum

"scan"

```
Jan 30 2016
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
```On 01/29/2016 08:11 AM, Luís Marques wrote:
On Friday, 29 January 2016 at 12:08:01 UTC, Andrei Alexandrescu wrote:
So the next best solution is to introduce a new name such as the
popular "fold", and put them together in the documentation.

Just to bikeshed a little, I remember that when I first started using
std.algorithm I was ctrl-F'ing for "accumulate" and not finding it quite
often. D competes with C++ directly, so do consider that name :-)

Good point, thanks! -- Andrei
```
Jan 29 2016
Walter Bright <newshound2 digitalmars.com> writes:
```On 1/29/2016 12:36 PM, Andrei Alexandrescu wrote:
On 01/29/2016 08:11 AM, Luís Marques wrote:
Just to bikeshed a little, I remember that when I first started using
std.algorithm I was ctrl-F'ing for "accumulate" and not finding it quite
often. D competes with C++ directly, so do consider that name :-)

Good point, thanks! -- Andrei

Given the different names for this used in different languages, I suggest in
the
documentation for 'fold' having an 'Also Known As' section, which will make it
greppable.
```
Jan 29 2016
Walter Bright <newshound2 digitalmars.com> writes:
```On 1/29/2016 5:11 AM, Luís Marques wrote:
Just to bikeshed a little, I remember that when I first started using
std.algorithm I was ctrl-F'ing for "accumulate" and not finding it quite often.
D competes with C++ directly, so do consider that name :-)

For algorithms and FP in general, we may be better off drawing inspiration from
Haskell, as C++ does not have FP in its DNA.
```
Jan 29 2016
Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
```On Friday, 29 January 2016 at 23:20:38 UTC, Walter Bright wrote:
On 1/29/2016 5:11 AM, Luís Marques wrote:
Just to bikeshed a little, I remember that when I first
started using
std.algorithm I was ctrl-F'ing for "accumulate" and not
finding it quite often.
D competes with C++ directly, so do consider that name :-)

For algorithms and FP in general, we may be better off drawing
inspiration from Haskell, as C++ does not have FP in its DNA.

So D is adding currying and builtin tuples? :^)
```
Jan 29 2016
```On Friday, 29 January 2016 at 23:45:04 UTC, Ola Fosheim Grøstad
wrote:
So D is adding currying and builtin tuples? :^)

Yes. Come back in 10 years it'll be ready for you.
```
Jan 29 2016
Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
```On Saturday, 30 January 2016 at 01:34:48 UTC, deadalnix wrote:
On Friday, 29 January 2016 at 23:45:04 UTC, Ola Fosheim Grøstad
wrote:
So D is adding currying and builtin tuples? :^)

Yes. Come back in 10 years it'll be ready for you.

Currying is pointless, I believe Swift is removing it. I was
joking, Haskell's naming scheme isn't particularly suited for an
imperative language.

Look:

nub
fst
snd
chr
intercalate
unwords
inits

??
```
Jan 30 2016
Xinok <xinok live.com> writes:
```On Saturday, 30 January 2016 at 12:11:37 UTC, Ola Fosheim Grøstad
wrote:
Currying is pointless, I believe Swift is removing it. ...

It might be fairly useless in D but it's definitely not useless
in general. It' a different design pattern and functional
languages make great use of it. OTOH, D substitutes it with other
design patterns like UFCS and template arguments, e.g.
arr.sort!"a > b".

Phobos even has a function which mimics currying via
std.functional.partial:

https://dlang.org/phobos/std_functional.html#partial
```
Jan 30 2016
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
```On 1/30/16 12:25 PM, Xinok wrote:
On Saturday, 30 January 2016 at 12:11:37 UTC, Ola Fosheim Grøstad wrote:
Currying is pointless, I believe Swift is removing it. ...

It might be fairly useless in D but it's definitely not useless in
general. It' a different design pattern and functional languages make
great use of it. OTOH, D substitutes it with other design patterns like
UFCS and template arguments, e.g. arr.sort!"a > b".

Phobos even has a function which mimics currying via
std.functional.partial:

https://dlang.org/phobos/std_functional.html#partial

I forgot the distinction between currying and partial application. Can
we also define currying in current D? -- Andrei
```
Jan 30 2016
```On Saturday, 30 January 2016 at 17:40:38 UTC, Andrei Alexandrescu
wrote:
I forgot the distinction between currying and partial
application. Can we also define currying in current D? -- Andrei

Currying is turning (A, B, C) -> D into A -> (B -> (C -> D)),
i.e. a function with multiple arguments into a sequence of
functions that each take a single argument to apply each.

I think I've implemented something like that for fun once, but
never really found much use for it. In the few places where I
could have used it (mostly binary functions), just using a lambda
and partial application seemed to be much more idiomatic. I guess
D lacks any idioms that would make its use come naturally.

- David
```
Jan 30 2016
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
```On 1/30/16 1:08 PM, David Nadlinger wrote:
On Saturday, 30 January 2016 at 17:40:38 UTC, Andrei Alexandrescu wrote:
I forgot the distinction between currying and partial application. Can
we also define currying in current D? -- Andrei

Currying is turning (A, B, C) -> D into A -> (B -> (C -> D)), i.e. a
function with multiple arguments into a sequence of functions that each
take a single argument to apply each.

I think I've implemented something like that for fun once, but never
really found much use for it. In the few places where I could have used
it (mostly binary functions), just using a lambda and partial
application seemed to be much more idiomatic. I guess D lacks any idioms
that would make its use come naturally.

- David

Thanks. I guess it'd be nice to have it on code.dlang.org somewhere so
people can play with it. -- Andrei
```
Feb 02 2016
Jakob Ovrum <jakobovrum gmail.com> writes:
```On Saturday, 30 January 2016 at 18:08:00 UTC, David Nadlinger
wrote:
Currying is turning (A, B, C) -> D into A -> (B -> (C -> D)),
i.e. a function with multiple arguments into a sequence of
functions that each take a single argument to apply each.

I think I've implemented something like that for fun once, but
never really found much use for it. In the few places where I
could have used it (mostly binary functions), just using a
lambda and partial application seemed to be much more
idiomatic. I guess D lacks any idioms that would make its use
come naturally.

- David

I'm late to the party, but I wrote these novetly tidbits a few
months ago:

Curry using nested structs
https://gist.github.com/JakobOvrum/8b2cd11b911079735b14

Curry using delegates
https://gist.github.com/JakobOvrum/1a19f670e7a3359006af

Neither approach seems to fit in with idiomatic D.
```
Feb 10 2016
bachmeier <no spam.net> writes:
```On Saturday, 30 January 2016 at 17:40:38 UTC, Andrei Alexandrescu
wrote:
On 1/30/16 12:25 PM, Xinok wrote:

I forgot the distinction between currying and partial
application. Can we also define currying in current D? -- Andrei

I'm sure others can give an informed answer on the distinction,
but a curried function takes only one argument, and I am unaware
of a practical reason to add currying to D if we already have
partial application.
```
Jan 30 2016
```On Friday, 29 January 2016 at 13:11:34 UTC, Luís Marques wrote:
On Friday, 29 January 2016 at 12:08:01 UTC, Andrei Alexandrescu
wrote:
So the next best solution is to introduce a new name such as
the popular "fold", and put them together in the documentation.

Just to bikeshed a little, I remember that when I first started
using std.algorithm I was ctrl-F'ing for "accumulate" and not
finding it quite often. D competes with C++ directly, so do
consider that name :-)

I'm not sure what the problem was, but the documentation for

https://dlang.org/library/std/algorithm/iteration/reduce.html
```
Jan 29 2016
Y <y srtnwz.com> writes:
```On Friday, 29 January 2016 at 12:08:01 UTC, Andrei Alexandrescu
wrote:
As has been discussed before there's been discussion about
std.algorithm.reduce taking the "wrong" order of arguments (its
definition predates UFCS). I recall the conclusion was there'd
be subtle ambiguities if we worked reduce to implement both
orders.

So the next best solution is to introduce a new name such as
the popular "fold", and put them together in the documentation.

Thoughts?

Andrei

```
Jan 29 2016
ixid <nuaccount gmail.com> writes:
```On Friday, 29 January 2016 at 12:08:01 UTC, Andrei Alexandrescu
wrote:
As has been discussed before there's been discussion about
std.algorithm.reduce taking the "wrong" order of arguments (its
definition predates UFCS). I recall the conclusion was there'd
be subtle ambiguities if we worked reduce to implement both
orders.

So the next best solution is to introduce a new name such as
the popular "fold", and put them together in the documentation.

Thoughts?

Andrei

Absolutely yes!
```
Jan 29 2016
wobbles <grogan.colin gmail.com> writes:
```On Friday, 29 January 2016 at 12:08:01 UTC, Andrei Alexandrescu
wrote:
As has been discussed before there's been discussion about
std.algorithm.reduce taking the "wrong" order of arguments (its
definition predates UFCS). I recall the conclusion was there'd
be subtle ambiguities if we worked reduce to implement both
orders.

So the next best solution is to introduce a new name such as
the popular "fold", and put them together in the documentation.

Thoughts?

Andrei

I think yes. Took me ages to realise the difference with reduce.
```
Jan 29 2016
```On Friday, 29 January 2016 at 12:08:01 UTC, Andrei Alexandrescu
wrote:
As has been discussed before there's been discussion about
std.algorithm.reduce taking the "wrong" order of arguments (its
definition predates UFCS). I recall the conclusion was there'd
be subtle ambiguities if we worked reduce to implement both
orders.

So the next best solution is to introduce a new name such as
the popular "fold", and put them together in the documentation.

Thoughts?

Andrei

+1

Let's make sure to write the half dozen other names for it in the
documentation so people coming to D from other languages can
easily find it.

And just for completeness, here is monarchdodra's valiant but
ultimately unsuccessful pull request which attempted fix reduce:
https://github.com/D-Programming-Language/phobos/pull/861#issuecomment-20760448
```
Jan 29 2016
Edwin van Leeuwen <edder tkwsping.nl> writes:
```On Friday, 29 January 2016 at 16:38:23 UTC, Brad Anderson wrote:
And just for completeness, here is monarchdodra's valiant but
ultimately unsuccessful pull request which attempted fix
reduce:
https://github.com/D-Programming-Language/phobos/pull/861#issuecomment-20760448

Interestingly, that pull request links to another pull request
which introduces fold, so we can just merge that one :) ?
https://github.com/D-Programming-Language/phobos/pull/2033
```
Jan 29 2016
Walter Bright <newshound2 digitalmars.com> writes:
```On 1/29/2016 4:08 AM, Andrei Alexandrescu wrote:
As has been discussed before there's been discussion about std.algorithm.reduce
taking the "wrong" order of arguments (its definition predates UFCS). I recall
the conclusion was there'd be subtle ambiguities if we worked reduce to
implement both orders.

So the next best solution is to introduce a new name such as the popular
"fold",
and put them together in the documentation.

Thoughts?

Andrei

Haskell can provide us with good inspiration and background for designing
'fold':

Note there is a foldl, foldr, and some more obscure foldt, foldi, and some
others.

Another design point is should fold be lazy? I.e.

auto x = [1,2,3].fold!dg;

means that x is a function that will actually do the computation if called.
```
Jan 29 2016
Walter Bright <newshound2 digitalmars.com> writes:
```On 1/29/2016 10:41 AM, Walter Bright wrote:
Note there is a foldl, foldr, and some more obscure foldt, foldi, and some
others.

foldr could be done with reverse.fold
```
Jan 29 2016
bachmeier <no spam.com> writes:
```On Friday, 29 January 2016 at 18:41:46 UTC, Walter Bright wrote:
Haskell can provide us with good inspiration and background for
designing 'fold':

Note there is a foldl, foldr, and some more obscure foldt,
foldi, and some others.

Once you use names like foldl and foldr, you're headed down the
slippery slope to Common Lisp naming. Please at least use
foldLeft and foldRight if you want to go that route.
```
Jan 29 2016
Chris Wright <dhasenan gmail.com> writes:
```On Fri, 29 Jan 2016 07:08:01 -0500, Andrei Alexandrescu wrote:

As has been discussed before there's been discussion about
std.algorithm.reduce taking the "wrong" order of arguments (its
definition predates UFCS). I recall the conclusion was there'd be subtle
ambiguities if we worked reduce to implement both orders.

So the next best solution is to introduce a new name such as the popular
"fold", and put them together in the documentation.

Thoughts?

Andrei

For my own sake, I don't care at all. I've seen this announcement, I'll
see deprecation warnings, so the change doesn't really bother me. A minor
irritation that I'd have to change a couple lines of code, that's all.

I always call reduce with UFCS (same with almost everything in
std.algorithm), so the parameter order doesn't affect me.
```
Jan 29 2016
```On Friday, 29 January 2016 at 12:08:01 UTC, Andrei Alexandrescu
wrote:
As has been discussed before there's been discussion about
std.algorithm.reduce taking the "wrong" order of arguments (its
definition predates UFCS). I recall the conclusion was there'd
be subtle ambiguities if we worked reduce to implement both
orders.

So the next best solution is to introduce a new name such as
the popular "fold", and put them together in the documentation.

Thoughts?

Andrei

```
Jan 29 2016
"H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
```On Fri, Jan 29, 2016 at 07:08:19PM +0000, deadalnix via Digitalmars-d wrote:
On Friday, 29 January 2016 at 12:08:01 UTC, Andrei Alexandrescu wrote:
As has been discussed before there's been discussion about
std.algorithm.reduce taking the "wrong" order of arguments (its definition
predates UFCS). I recall the conclusion was there'd be subtle ambiguities
if we worked reduce to implement both orders.

So the next best solution is to introduce a new name such as the popular
"fold", and put them together in the documentation.

Thoughts?

Andrei

Me Too(tm).

T

--
2+2=4. 2*2=4. 2^2=4. Therefore, +, *, and ^ are the same operation.
```
Jan 29 2016
Atila Neves <atila.neves gmail.com> writes:
```On Friday, 29 January 2016 at 12:08:01 UTC, Andrei Alexandrescu
wrote:
As has been discussed before there's been discussion about
std.algorithm.reduce taking the "wrong" order of arguments (its
definition predates UFCS). I recall the conclusion was there'd
be subtle ambiguities if we worked reduce to implement both
orders.

So the next best solution is to introduce a new name such as
the popular "fold", and put them together in the documentation.

Thoughts?

Andrei

Definitely yes.

Atila
```
Feb 02 2016
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
```On 2/2/16 11:02 AM, Atila Neves wrote:
On Friday, 29 January 2016 at 12:08:01 UTC, Andrei Alexandrescu wrote:
As has been discussed before there's been discussion about
std.algorithm.reduce taking the "wrong" order of arguments (its
definition predates UFCS). I recall the conclusion was there'd be
subtle ambiguities if we worked reduce to implement both orders.

So the next best solution is to introduce a new name such as the
popular "fold", and put them together in the documentation.

Thoughts?

Andrei

Definitely yes.

Atila, wanna do the honors? -- Andrei
```
Feb 02 2016
Atila Neves <atila.neves gmail.com> writes:
```On Tuesday, 2 February 2016 at 20:02:39 UTC, Andrei Alexandrescu
wrote:
On 2/2/16 11:02 AM, Atila Neves wrote:
On Friday, 29 January 2016 at 12:08:01 UTC, Andrei
Alexandrescu wrote:
As has been discussed before there's been discussion about
std.algorithm.reduce taking the "wrong" order of arguments
(its
definition predates UFCS). I recall the conclusion was
there'd be
subtle ambiguities if we worked reduce to implement both
orders.

So the next best solution is to introduce a new name such as
the
popular "fold", and put them together in the documentation.

Thoughts?

Andrei

Definitely yes.

Atila, wanna do the honors? -- Andrei

If it's not urgent, sure.

Atila
```
Feb 02 2016
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
```On 2/2/16 3:50 PM, Atila Neves wrote:
On Tuesday, 2 February 2016 at 20:02:39 UTC, Andrei Alexandrescu wrote:
On 2/2/16 11:02 AM, Atila Neves wrote:
On Friday, 29 January 2016 at 12:08:01 UTC, Andrei Alexandrescu wrote:
As has been discussed before there's been discussion about
std.algorithm.reduce taking the "wrong" order of arguments (its
definition predates UFCS). I recall the conclusion was there'd be
subtle ambiguities if we worked reduce to implement both orders.

So the next best solution is to introduce a new name such as the
popular "fold", and put them together in the documentation.

Thoughts?

Andrei

Definitely yes.

Atila, wanna do the honors? -- Andrei

If it's not urgent, sure.

Thanks! And don't forget: in D, everything is top priority. -- Andrei
```
Feb 02 2016
Atila Neves <atila.neves gmail.com> writes:
```On Wednesday, 3 February 2016 at 00:57:18 UTC, Andrei
Alexandrescu wrote:
On 2/2/16 3:50 PM, Atila Neves wrote:
On Tuesday, 2 February 2016 at 20:02:39 UTC, Andrei
Alexandrescu wrote:
On 2/2/16 11:02 AM, Atila Neves wrote:
On Friday, 29 January 2016 at 12:08:01 UTC, Andrei
Alexandrescu wrote:
As has been discussed before there's been discussion about
std.algorithm.reduce taking the "wrong" order of arguments
(its
definition predates UFCS). I recall the conclusion was
there'd be
subtle ambiguities if we worked reduce to implement both
orders.

So the next best solution is to introduce a new name such
as the
popular "fold", and put them together in the documentation.

Thoughts?

Andrei

Definitely yes.

Atila, wanna do the honors? -- Andrei

If it's not urgent, sure.

Thanks! And don't forget: in D, everything is top priority. --
Andrei

Of course it is ;)

I guess this is to be a brand new PR? I've been reading the old
one and the discussions. A lot of unanswered questions there and
I have a new opinion on at least one of them.

Atila
```
Feb 03 2016
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
```On 02/03/2016 10:18 AM, Atila Neves wrote:
I guess this is to be a brand new PR? I've been reading the old one and
the discussions. A lot of unanswered questions there and I have a new
opinion on at least one of them.

If by the old one you mean the valiant effort to overload reduce, forget
it. Just add fold as a one-liner that forwards to reduce. -- Andrei
```
Feb 03 2016
Atila Neves <atila.neves gmail.com> writes:
```On Wednesday, 3 February 2016 at 16:40:49 UTC, Andrei
Alexandrescu wrote:
On 02/03/2016 10:18 AM, Atila Neves wrote:
I guess this is to be a brand new PR? I've been reading the
old one and
the discussions. A lot of unanswered questions there and I
have a new
opinion on at least one of them.

If by the old one you mean the valiant effort to overload
reduce, forget it. Just add fold as a one-liner that forwards
to reduce. -- Andrei

Ah, yes. That definitely makes more sense than me writing one
from scratch this afternoon, which I totally didn't do... :P

https://github.com/D-Programming-Language/phobos/pull/3968

I think fold should be nothrow, but maybe that's just me. It's
also a massive pain to make it that way, so I didn't for now.

Atila
```
Feb 03 2016
Timon Gehr <timon.gehr gmx.ch> writes:
```On 02/03/2016 09:12 PM, Atila Neves wrote:
https://github.com/D-Programming-Language/phobos/pull/3968

I think fold should be nothrow, but maybe that's just me. It's also a
massive pain to make it that way, so I didn't for now.

Returning Unqual!(ElementType!R).init makes no sense though.
The "correct" result of fold!f([]) is a (often, the) value 'a' such that
for any 'b', 'f(a,b)==b' (which is the canonical choice of "seed"), but
there is no way for fold to infer such a value.
```
Feb 03 2016
John Colvin <john.loughran.colvin gmail.com> writes:
```On Wednesday, 3 February 2016 at 21:45:04 UTC, Timon Gehr wrote:
On 02/03/2016 09:12 PM, Atila Neves wrote:
https://github.com/D-Programming-Language/phobos/pull/3968

I think fold should be nothrow, but maybe that's just me. It's
also a
massive pain to make it that way, so I didn't for now.

Returning Unqual!(ElementType!R).init makes no sense though.
The "correct" result of fold!f([]) is a (often, the) value 'a'
such that for any 'b', 'f(a,b)==b' (which is the canonical
choice of "seed"), but there is no way for fold to infer such a
value.

I wish we had some standardised way to express what the
identities (and maybe inverses) are for a given type under given
operations.
```
Feb 03 2016
"H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
```On Wed, Feb 03, 2016 at 10:30:45PM +0000, John Colvin via Digitalmars-d wrote:
On Wednesday, 3 February 2016 at 21:45:04 UTC, Timon Gehr wrote:
On 02/03/2016 09:12 PM, Atila Neves wrote:
https://github.com/D-Programming-Language/phobos/pull/3968

I think fold should be nothrow, but maybe that's just me. It's also
a massive pain to make it that way, so I didn't for now.

Returning Unqual!(ElementType!R).init makes no sense though.  The
"correct" result of fold!f([]) is a (often, the) value 'a' such that
for any 'b', 'f(a,b)==b' (which is the canonical choice of "seed"),
but there is no way for fold to infer such a value.

I wish we had some standardised way to express what the identities
(and maybe inverses) are for a given type under given operations.

I've been wishing for something like this for a long time, though I
haven't come upon a nice way to implement it just yet.  It would present
awesome optimization opportunities to the compiler, if it could be done,
though.  Imagine if you can tell the compiler that a custom numeric type
(say BigInt, or, for that matter, Complex) satisfies certain identities.
That would lift a lot of the case-specific code in the optimizer into
library land, thus simplifying the compiler while affording even more
powerful, high-level optimizations defined by the user.

IMO, compilers of the future will have such capabilities, simply because
one day we will eventually reach the point where certain optimizations
just aren't possible without the user prodding the compiler in the right
direction. Manually writing out optimized code will eventually be a
thing of the past, since it's hard to ensure code correctness, and
nobody wants to optimize the same computations 100 times, every time
they implement something that requires that sequence of operations. The
programmer *should* be able to express the idea of "hey compiler, my
custom type T obeys identities x, y, z; now you go figure out how to
apply x, y, z to produce the most optimized code you can".

T

--
Long, long ago, the ancient Chinese invented a device that lets them see
through walls. It was called the "window".
```
Feb 03 2016
Atila Neves <atila.neves gmail.com> writes:
```On Wednesday, 3 February 2016 at 21:45:04 UTC, Timon Gehr wrote:
On 02/03/2016 09:12 PM, Atila Neves wrote:
https://github.com/D-Programming-Language/phobos/pull/3968

I think fold should be nothrow, but maybe that's just me. It's
also a
massive pain to make it that way, so I didn't for now.

Returning Unqual!(ElementType!R).init makes no sense though.
The "correct" result of fold!f([]) is a (often, the) value 'a'
such that for any 'b', 'f(a,b)==b' (which is the canonical
choice of "seed"), but there is no way for fold to infer such a
value.

Right. I wrote in a hurry and without checking the code I'd
written yesterday. The correct value to return for one function
would be:

template fold(fun...) {
alias binFuncs = staticMap!(binaryFun, fun);
// checks for fun.length == 1, etc.
auto fold(R)(R r) {
return Unqual!(typeof(binFuncs[0](r.front,
r.front))).init;
}
}

Since there's no seed, the first element of the range would
normally be used. But the fact that the range is empty doesn't
change what type such a first element would have. The element
type of the range is fixed (i.e. the 2nd element would be the
same type as the 1st), so passing front twice to the binary
function means the types check out.

For multiple functions it gets hairy fast, but basically
generalise the above to a tuple with the same expression but
instead of always using binFuncs[0] it uses all of them. I've got
an implementation that works, as long as the functions passed in
aren't local. Seems to be some staticMap limitation or maybe I'm
just doing it wrong.

Atila
```
Feb 04 2016
Timon Gehr <timon.gehr gmx.ch> writes:
```On 02/04/2016 10:38 AM, Atila Neves wrote:
On Wednesday, 3 February 2016 at 21:45:04 UTC, Timon Gehr wrote:
On 02/03/2016 09:12 PM, Atila Neves wrote:
https://github.com/D-Programming-Language/phobos/pull/3968

I think fold should be nothrow, but maybe that's just me. It's also a
massive pain to make it that way, so I didn't for now.

Returning Unqual!(ElementType!R).init makes no sense though.
The "correct" result of fold!f([]) is a (often, the) value 'a' such
that for any 'b', 'f(a,b)==b' (which is the canonical choice of
"seed"), but there is no way for fold to infer such a value.

Right. I wrote in a hurry and without checking the code I'd written
yesterday. The correct value to return for one function would be:

template fold(fun...) {
alias binFuncs = staticMap!(binaryFun, fun);
// checks for fun.length == 1, etc.
auto fold(R)(R r) {
return Unqual!(typeof(binFuncs[0](r.front, r.front))).init;
}
}

My point was more that the .init value is often not the value you want.
```
Feb 04 2016
Atila Neves <atila.neves gmail.com> writes:
```On Wednesday, 3 February 2016 at 20:12:38 UTC, Atila Neves wrote:
On Wednesday, 3 February 2016 at 16:40:49 UTC, Andrei
Alexandrescu wrote:
On 02/03/2016 10:18 AM, Atila Neves wrote:
I guess this is to be a brand new PR? I've been reading the
old one and
the discussions. A lot of unanswered questions there and I
have a new
opinion on at least one of them.

If by the old one you mean the valiant effort to overload
reduce, forget it. Just add fold as a one-liner that forwards
to reduce. -- Andrei

Ah, yes. That definitely makes more sense than me writing one
from scratch this afternoon, which I totally didn't do... :P

https://github.com/D-Programming-Language/phobos/pull/3968

I think fold should be nothrow, but maybe that's just me. It's
also a massive pain to make it that way, so I didn't for now.

Atila

Got one LGTM already, just need someone else to look over it.

Atila
```
Feb 29 2016