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.

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

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

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.

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

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

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.

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

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.

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