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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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