On Thursday, 27 March 2014 at 22:29:01 UTC, Timon Gehr wrote:
> On 03/27/2014 03:45 PM, monarch_dodra wrote:
>>
>> Right, but what about "fold" vs "fold_left"? Is there a difference?
>
> 'fold' is not descriptive enough. Ranges/lists have a very particular structure allowing 'foldl' to make sense. In general recursive data types (eg. think binary tree) allow only one fold (the recursive one). The instantiation for lists is 'foldr'.
>
> I'd rather have this named 'foldl'. 'fold' is a more abstract name 'foldr' rather than 'foldl'.

That makes sense.

Would it make sense to have also have a "fold" that does recursive reduction? EG:

fun(fun(a[0], a[1]), fun(a[2], a[3]))

That could seem useful to me.

On 03/28/2014 01:41 AM, Meta wrote:
> On Thursday, 27 March 2014 at 22:33:50 UTC, Timon Gehr wrote:
>> It doesn't make sense at all. It is an arbitrary limitation. The rule
>> is simple though: One can only alias things that syntactically look
>> like they might be types. This is why the following triviality is way
>> more useful than it should be:
>>
>> alias Id(alias a)=a;
>>
>> alias fun = Id!(a=>a); // ok!
>
> You can tell me that function literals look like types, but I won't
> believe you.

You mean because the literal is accepted as an alias argument? Alias template arguments are not actually the same thing as alias declarations. (Eg. the latter can accept built-in types like 'int', while the former will not, but otherwise allow arbitrary expressions.) I used to think this was a bug, but Walter stated that this is in fact by design. (I think this is a gratuitous design mistake.)

The expressions that are used in alias declarations are 'a' and 'Id!(a=>a)'. Both of those can occur in a context where they denote types.

On Friday, 28 March 2014 at 22:39:24 UTC, Timon Gehr wrote:
> You mean because the literal is accepted as an alias argument? Alias template arguments are not actually the same thing as alias declarations. (Eg. the latter can accept built-in types like 'int', while the former will not, but otherwise allow arbitrary expressions.) I used to think this was a bug, but Walter stated that this is in fact by design. (I think this is a gratuitous design mistake.)
>
> The expressions that are used in alias declarations are 'a' and 'Id!(a=>a)'. Both of those can occur in a context where they denote types.

I'm confused now. What exactly was it that you were saying didn't make sense?

On Saturday, 29 March 2014 at 00:58:46 UTC, Meta wrote:
> I'm confused now. What exactly was it that you were saying didn't make sense?

Ah, I see now. When I said "it's a bit unintuitive as to what works and what doesn't", I was talking about how unless you know exactly what can be assigned to an alias and enum, it seems unintuitive or even random as to what works, but there are actually sound logical underpinnings.

On 03/29/2014 02:02 AM, Meta wrote:
> On Saturday, 29 March 2014 at 00:58:46 UTC, Meta wrote:
>> I'm confused now. What exactly was it that you were saying didn't make
>> sense?
>
> Ah, I see now. When I said "it's a bit unintuitive as to what works and
> what doesn't", I was talking about how unless you know exactly what can
> be assigned to an alias and enum, it seems unintuitive or even random as
> to what works, but there are actually sound logical underpinnings.

My point was: Yes, there are rules, but they are inadequate/unnecessarily restrictive.

monarch_dodra:

> I'm taking this naming-changing event as an opportunity to "cleanup" reduce too.

This is possibly silly question, or perhaps fit just for D.learn. But I think it's sufficiently in topic in this thread.

You have a function foo1 like this:


import std.range, std.algorithm, std.array;

uint[] foo1(uint[][] X) {
    return X.reduce!((i, j) => zip(i, j)
                               .map!(kw => kw[0] | kw[1])
                               .array);
}

void main() {
    import std.stdio;
    uint[][] m1 = [[10, 20], [30, 40]];
    foo1(m1).writeln;
}


foo1 doesn't need to change its input so I'd like to use the signature:

int[] foo1(in int[][] X) {

But that can't work because reduce returns a const.

And you can't do this because it returns a wrong result:

uint[] foo2(in uint[][] X) {
    return reduce!((i, j) => zip(i, j)
                             .map!(kw => kw[0] | kw[1])
                             .array)
                  ((uint[]).init, X);
}



This seems OK, but can fold offer a better solution?:

uint[] foo3(in uint[][] X) {
    return reduce!((i, j) => zip(i, j)
                             .map!(kw => kw[0] | kw[1])
                             .array)
                  (X[0].dup, X[1 .. $]);
}

Bye,
bearophile

On Sunday, 30 March 2014 at 21:53:16 UTC, bearophile wrote:
> monarch_dodra:
>
>> I'm taking this naming-changing event as an opportunity to "cleanup" reduce too.
>
> This seems OK, but can fold offer a better solution?:
>
> Bye,
> bearophile

AFAIK, no: Your range's element type (E) is `const(uint)[]`, and given your predicate (let's just call it "pred"), `pred(e, e)` produces a `const(uint)[]`. There's not much that reduce or fold(l) could do about it at that point.

You'd have two (IMO cleaner) solutions.
1. tweak pred to return the right type (*):
uint[] foo1(uint[][] X)
{
    return X.reduce!((i, j) => zip(i, j)
        .map!(kw => uint(kw[0] | kw[1]))
        .array);
}
(*) This currently fails catastrophically with both single and multiple pred versions of reduce, due to suboptimal code.

I can get it to work for fold though.

2. provide a seed.
uint[] foo1(uint[][] X)
{
    return reduce!((i, j) => zip(i, j)
        .map!(kw => uint(kw[0] | kw[1]))
        .array)([uint(0), uint(0)], X);
}

In any case, thanks for reporting. I'll make certain this works.

monarch_dodra:

Thank you for the answers.

> I can get it to work for fold though.

Good.


> 2. provide a seed.
> uint[] foo1(uint[][] X)
> {
>     return reduce!((i, j) => zip(i, j)
>         .map!(kw => uint(kw[0] | kw[1]))
>         .array)([uint(0), uint(0)], X);
> }


Unfortunately it doesn't work correctly (because the size of the rows is not always 2):



import std.range, std.algorithm, std.array;

// Original correct.
uint[] foo1(uint[][] X) {
    return X.reduce!((i, j) => zip(i, j)
                               .map!(kw => kw[0] | kw[1])
                               .array);
}

// OK
uint[] foo3(in uint[][] X) {
    return reduce!((i, j) => zip(i, j)
                             .map!(kw => kw[0] | kw[1])
                             .array)
                  (X[0].dup, X[1 .. $]);
}

// Modified, not good.
uint[] foo4(uint[][] X) {
    return reduce!((i, j) => zip(i, j)
                             .map!(kw => uint(kw[0] | kw[1]))
                             .array)
                  ([uint(0), uint(0)], X);
}

void main() {
    import std.stdio;
    uint[][] m1 = [[10, 20, 30], [40, 50, 60]];
    foo1(m1).writeln;
    uint[][] m3 = [[10, 20, 30], [40, 50, 60]];
    foo3(m3).writeln;
    uint[][] m4 = [[10, 20, 30], [40, 50, 60]];
    foo4(m4).writeln;
}


Output:

[42, 54, 62]
[42, 54, 62]
[42, 54]

Bye,
bearophile

On Monday, 31 March 2014 at 10:28:10 UTC, bearophile wrote:
> monarch_dodra:
>
> Thank you for the answers.
>
>> I can get it to work for fold though.
>
> Good.

I've reconsidered my answer. It is *impossible* to get what you are asking for to work, without explicitly passing a seed.

This is because the seed is *initialized* to the range's front. Anything other than "const(uint)[]" would simply break the type system: If your range only has 1 element, then you'd be returning a mutable reference to const data.

So my vote goes to this solution.

//----
uint[] foo3(in uint[][] X)
{
    assert(!X.empty)
    auto seed = X.front.dup;
    X.popFront();
    return reduce!((i, j) => zip(i, j)
                             .map!(kw => kw[0] | kw[1])
                             .array)
                  (seed, X);
}
//----

I re-wrote it that way: It's a bit longer, but a bit more generic in terms of customizing your seed.

monarch_dodra:

> So my vote goes to this solution.
>
> //----
> uint[] foo3(in uint[][] X)
> {
>     assert(!X.empty)
>     auto seed = X.front.dup;
>     X.popFront();
>     return reduce!((i, j) => zip(i, j)
>                              .map!(kw => kw[0] | kw[1])
>                              .array)
>                   (seed, X);
> }
> //----
>
> I re-wrote it that way: It's a bit longer, but a bit more generic in terms of customizing your seed.

OK, thank you. So the price for that "in" is to use a dup :-) (Or use lower level code).

Bye,
bearophile