www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - reduce -> fold?

reply 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
next sibling parent Adrian Matoga <dlang.spam matoga.info> 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?


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
prev sibling next sibling parent reply =?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
next sibling parent reply 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
next sibling parent =?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
prev sibling next sibling parent reply 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
next sibling parent reply 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
parent reply 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
next sibling parent 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
prev sibling parent reply 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 
 comes from in your example.


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
parent 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
prev sibling parent 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


I wrote a bit about this sort of thing here: 
https://github.com/D-Programming-Language/phobos/pull/2991#issuecomment-141816906
Feb 04 2016
prev sibling parent 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"

http://hackage.haskell.org/package/base-4.8.2.0/docs/Prelude.html#v:scanl
Jan 30 2016
prev sibling next sibling parent reply 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
parent 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
prev sibling next sibling parent reply 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
parent reply 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
parent reply deadalnix <deadalnix gmail.com> writes:
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
parent reply 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
parent reply 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
parent reply 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
next sibling parent reply David Nadlinger <code klickverbot.at> writes:
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
next sibling parent 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
prev sibling parent 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
prev sibling parent 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
prev sibling parent Vladimir Panteleev <thecybershadow.lists gmail.com> writes:
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 
"reduce" already mentions "accumulate":

https://dlang.org/library/std/algorithm/iteration/reduce.html
Jan 29 2016
prev sibling next sibling parent 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


Yes yes yes please!
Jan 29 2016
prev sibling next sibling parent 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
prev sibling next sibling parent 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
prev sibling next sibling parent reply Brad Anderson <eco gnuk.net> 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


+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
parent 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
prev sibling next sibling parent reply 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':

   https://wiki.haskell.org/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
next sibling parent 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
prev sibling parent 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':

   https://wiki.haskell.org/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
prev sibling next sibling parent 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
prev sibling next sibling parent reply deadalnix <deadalnix 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


Yes, please.
Jan 29 2016
parent "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


 
 Yes, please.


Me Too(tm).


T

-- 
2+2=4. 2*2=4. 2^2=4. Therefore, +, *, and ^ are the same operation.
Jan 29 2016
prev sibling parent reply 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
parent reply 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
parent reply 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
parent reply 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
parent reply 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
parent reply 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
parent reply 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
next sibling parent reply 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
next sibling parent reply 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
parent "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
prev sibling parent reply 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
parent 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
prev sibling parent 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