Re: reduce -> fold?
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
Re: reduce -> fold?
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.
Re: reduce -> fold?
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
Re: reduce -> fold?
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.
Re: reduce -> fold?
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
Re: reduce -> fold?
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
Re: reduce -> fold?
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.
Re: reduce -> fold?
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
Re: reduce -> fold?
On Wed, Feb 03, 2016 at 10:30:45PM +, 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".
Re: reduce -> fold?
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.
Re: reduce -> fold?
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.
Re: reduce -> fold?
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
Re: reduce -> fold?
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
Re: reduce -> fold?
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
Re: reduce -> fold?
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
Re: reduce -> fold?
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
Re: reduce -> fold?
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
Re: reduce -> fold?
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
Re: reduce -> fold?
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
Re: reduce -> fold?
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
Re: reduce -> fold?
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.
Re: reduce -> fold?
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
Re: reduce -> fold?
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.
Re: reduce -> fold?
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
Re: reduce -> fold?
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
Re: reduce -> fold?
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
Re: reduce -> fold?
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 ??
Re: reduce -> fold?
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.
Re: reduce -> fold?
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
Re: reduce -> fold?
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? :^)
Re: reduce -> fold?
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.
Re: reduce -> fold?
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.
Re: reduce -> fold?
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.
Re: reduce -> fold?
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
Re: reduce -> fold?
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
Re: reduce -> fold?
On Fri, Jan 29, 2016 at 07:08:19PM +, 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.
Re: reduce -> fold?
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
Re: reduce -> fold?
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.
Re: reduce -> fold?
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.
Re: reduce -> fold?
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.
Re: reduce -> fold?
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
Re: reduce -> fold?
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.
Re: reduce -> fold?
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
Re: reduce -> fold?
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!
Re: reduce -> fold?
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!
Re: reduce -> fold?
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.
Re: reduce -> fold?
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
Re: reduce -> fold?
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 :-)
Re: reduce -> fold?
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/sqbizjwcyavbrxwag...@forum.dlang.org
reduce -> fold?
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
