reduce -> fold?

[H. S. Teoh via Digitalmars-d]

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