reduce of an array of structs with an immutable field

[dlangBugzillaToGithub]

bearophile_hugs reported this on 2013-04-16T16:16:16Z

Transfered from https://issues.dlang.org/show_bug.cgi?id=9947

CC List

• monarchdodra
• r.97all

Description

Maybe this should work:


import std.algorithm: reduce;
struct Foo {
    immutable int x;
}
void main() {
    auto data = [Foo(0)];
    reduce!((a, b) => a)(data);
}



DMD 2.063alpha gives:

...\dmd2\src\phobos\std\algorithm.d(702): Error: cannot modify struct result Foo with immutable members
...\dmd2\src\phobos\std\algorithm.d(723): Error: template instance test.main.reduce!(__lambda3).reduce!(Foo,Foo[]) error instantiating
test.d(7):        instantiated from here: reduce!(Foo[])
test.d(7): Error: template instance test.main.reduce!(__lambda3).reduce!(Foo[]) error instantiating

[dlangBugzillaToGithub]

r.97all commented on 2013-05-16T03:19:35Z

Using DMD32 v2.061 on Windows 32bit, below doesn't work too.
I think this is the same issue:
-----
import std.stdio;
import std.algorithm : sort;

struct S
{
    immutable int x;
}

void main()
{
    auto arr = [S(0), S(2), S(1)];
    sort!((a, b) => a.x < b.x)(arr);
    arr.writeln();
}
-----

algorithm.d(1814):Error: cannot modify struct lhs S with immutable members
algorithm.d(1815): Error: cannot modify struct rhs S with immutable members
algorithm.d(7972): Error: template instance std.algorithm.swap!(S) error instantiating
algorithm.d(7908):   instantiated from here: swapAt!(S[])
algorithm.d(7993):   instantiated from here: getPivot!(__lambda3, S[])
algorithm.d(7712):   instantiated from here: quickSortImpl!(__lambda3, S[])
main.d(12):        instantiated from here: sort!(__lambda3, cast(SwapStrategy)0, S[])
algorithm.d(7908): Error: template instance std.algorithm.swapAt!(S[]) error instantiating
algorithm.d(7993):   instantiated from here: getPivot!(__lambda3, S[])
algorithm.d(7712):   instantiated from here: quickSortImpl!(__lambda3, S[])
main.d(12):        instantiated from here: sort!(__lambda3, cast(SwapStrategy)0, S[])
algorithm.d(7993): Error: template instance main.main.getPivot!(__lambda3, S[]) error instantiating
algorithm.d(7712):   instantiated from here: quickSortImpl!(__lambda3, S[])
main.d(12):        instantiated from here: sort!(__lambda3, cast(SwapStrategy)0, S[])
algorithm.d(7946): Error: cannot modify struct r[j] S with immutable members
algorithm.d(7949): Error: cannot modify struct r[j] S with immutable members
algorithm.d(8028): Error: template instance main.main.optimisticInsertionSort!(__lambda3, S[]) error instantiating
algorithm.d(7712):   instantiated from here: quickSortImpl!(__lambda3, S[])
main.d(12):        instantiated from here: sort!(__lambda3, cast(SwapStrategy)0, S[])
algorithm.d(7712): Error: template instance main.main.quickSortImpl!(__lambda3, S[]) error instantiating
main.d(12):        instantiated from here: sort!(__lambda3, cast(SwapStrategy)0, S[])
main.d(12): Error: template instance main.main.sort!(__lambda3, cast(SwapStrategy)0, S[]) error instantiating

[dlangBugzillaToGithub]

monarchdodra commented on 2014-02-25T12:27:55Z

(In reply to comment #0)
> Maybe this should work:
> 
> 
> import std.algorithm: reduce;
> struct Foo {
>     immutable int x;
> }
> void main() {
>     auto data = [Foo(0)];
>     reduce!((a, b) => a)(data);
> }
> 
> 
> 
> DMD 2.063alpha gives:
> 
> ...\dmd2\src\phobos\std\algorithm.d(702): Error: cannot modify struct result
> Foo with immutable members
> ...\dmd2\src\phobos\std\algorithm.d(723): Error: template instance
> test.main.reduce!(__lambda3).reduce!(Foo,Foo[]) error instantiating
> test.d(7):        instantiated from here: reduce!(Foo[])
> test.d(7): Error: template instance test.main.reduce!(__lambda3).reduce!(Foo[])
> error instantiating

I think it is acceptable to require that whatever the type being reduced be assignable? It would be more friendly if it asserts though.

[dlangBugzillaToGithub]

monarchdodra commented on 2014-02-25T12:29:47Z

(In reply to comment #1)
> Using DMD32 v2.061 on Windows 32bit, below doesn't work too.
> I think this is the same issue:
> -----
> import std.stdio;
> import std.algorithm : sort;
> 
> struct S
> {
>     immutable int x;
> }
> 
> void main()
> {
>     auto arr = [S(0), S(2), S(1)];
>     sort!((a, b) => a.x < b.x)(arr);
>     arr.writeln();
> }
> -----

Indeed. But in this case, `arr` is *simply* not sortable: Not without mutating the immutable.

This is fixed now though:
Error: template std.algorithm.sort cannot deduce function from argument types !((a, b) => a.x < b.x)(S[])

[dlangBugzillaToGithub]

monarchdodra commented on 2014-03-31T06:17:15Z

Yes, I think this is invalid, because the documentation states:
//----
Then, for each element $(D x) in $(D range), $(D result = fun(result, x)) gets evaluated.
//----

And here, the type is not assignable, even when unqualed.

That said, a recursive "divide and conquer" fold could support such a case. I'm leaving this open as en ER.