www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 8803] New: map.filter.array run map delegate an incorrect number of time.

reply d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8803

           Summary: map.filter.array run map delegate an incorrect number
                    of time.
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Phobos
        AssignedTo: nobody puremagic.com
        ReportedBy: deadalnix gmail.com


--- Comment #0 from deadalnix <deadalnix gmail.com> 2012-10-11 14:12:44 PDT ---
See sample code :

import std.algorithm;
import std.range;

void main() {
    uint i;

    uint[] iarray;
    iarray.length = 10;

    iarray.map!(a => i++).filter!(a => a > 0).array();

    import std.stdio;
    writeln(i);
}

This program output 19. In other terms, map delegate is run twice on every
element on which filter's delegate returns true.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 11 2012
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8803


Peter Alexander <peter.alexander.au gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |peter.alexander.au gmail.co
                   |                            |m


--- Comment #1 from Peter Alexander <peter.alexander.au gmail.com> 2012-10-16
09:51:00 PDT ---
I'm assuming the bug here is that map's ddoc says it caches front, but it
clearly isn't. I've updated the ddoc to reflect this.

https://github.com/D-Programming-Language/phobos/pull/876

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 16 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8803



--- Comment #2 from deadalnix <deadalnix gmail.com> 2012-10-16 10:17:43 PDT ---
(In reply to comment #1)

 I'm assuming the bug here is that map's ddoc says it caches front, but it
 clearly isn't. I've updated the ddoc to reflect this.
 
 https://github.com/D-Programming-Language/phobos/pull/876


I don't think fixing the ddoc is the fix.

Being unable to do .map.filter defeat the whole point of map and filter.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 16 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8803



--- Comment #3 from Peter Alexander <peter.alexander.au gmail.com> 2012-10-16
13:59:38 PDT ---
(In reply to comment #2)

 Being unable to do .map.filter defeat the whole point of map and filter.


Sorry, I'm not following. Why are you saying you can't do a .map.filter? You
can, it just calls the map function more than once per element.

What exactly is the problem?

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 16 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8803



--- Comment #4 from deadalnix <deadalnix gmail.com> 2012-10-16 14:20:32 PDT ---
(In reply to comment #3)

 (In reply to comment #2)

 Being unable to do .map.filter defeat the whole point of map and filter.


 
 Sorry, I'm not following. Why are you saying you can't do a .map.filter? You
 can, it just calls the map function more than once per element.
 
 What exactly is the problem?


The problem is that the delegate get executed an impredictable number of time.
Which make side effect extremely hard to handle (I ended up using
map.array.filter most of the time in my own codebase) in terms of side-effect
or performance.

Additionally, the problem is dependent of the inner implementation of both map
and filter, which should stay unknown for the user.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 16 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8803



--- Comment #5 from Peter Alexander <peter.alexander.au gmail.com> 2012-10-16
14:31:13 PDT ---
(In reply to comment #4)

 The problem is that the delegate get executed an impredictable number of time.
 Which make side effect extremely hard to handle (I ended up using
 map.array.filter most of the time in my own codebase) in terms of side-effect
 or performance.

 Additionally, the problem is dependent of the inner implementation of both map
 and filter, which should stay unknown for the user.


I think the real problem here is that your mapping function has side effects.
The undocumented intention of map is that the mapping function is pure. Using
it to produce side-effects on the function call is not the intended use of map
(just like having side effects in the comparison function in a sort would be a
bad idea).

Other than the incorrect documentation, I don't think there is a bug here.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 16 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8803


Alex Rønne Petersen <alex lycus.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |alex lycus.org


--- Comment #6 from Alex Rønne Petersen <alex lycus.org> 2012-10-17 01:03:15
CEST ---
I think it would be a good idea to update std.algorithm's docs to reflect that
some first-class functions are expected to be pure. Can anyone send a pull
request for that?

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 16 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8803



--- Comment #7 from deadalnix <deadalnix gmail.com> 2012-10-17 02:47:53 PDT ---
(In reply to comment #5)

 (In reply to comment #4)

 The problem is that the delegate get executed an impredictable number of time.
 Which make side effect extremely hard to handle (I ended up using
 map.array.filter most of the time in my own codebase) in terms of side-effect
 or performance.

 Additionally, the problem is dependent of the inner implementation of both map
 and filter, which should stay unknown for the user.


 
 I think the real problem here is that your mapping function has side effects.
 The undocumented intention of map is that the mapping function is pure. Using
 it to produce side-effects on the function call is not the intended use of map
 (just like having side effects in the comparison function in a sort would be a
 bad idea).
 
 Other than the incorrect documentation, I don't think there is a bug here.


Well, I do think many valid uses include impure functions, even in sort. For
instance for benchmarking purpose, for educational purpose, for caching.

More importantly, pure function isn't enough. A pure function can return 2
different objects. Even if the object's content will be the same, its identity
will not, which is a problem in many cases (the example above is simplified, in
my case that was the issue).

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 17 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8803



--- Comment #8 from Peter Alexander <peter.alexander.au gmail.com> 2012-10-17
04:54:17 PDT ---
(In reply to comment #7)

 Well, I do think many valid uses include impure functions, even in sort. For
 instance for benchmarking purpose, for educational purpose, for caching.
 
 More importantly, pure function isn't enough. A pure function can return 2
 different objects. Even if the object's content will be the same, its identity
 will not, which is a problem in many cases (the example above is simplified, in
 my case that was the issue).


I think this issue boils down to this: you are expecting something from map,
which is does not advertise to do (any more). There is no bug.

You could change this to an enhancement request, because you are asking for an
additional feature.

Note that if you do add caching for 'front', you still have the same problem if
you try to use indexing. e.g.

auto xs = [1, 2, 3];
auto m = xs.map!(fun)();
auto ref a = m[1], b = m[1];

The only way this could guarantee to apply fun once is if it caches the entire
range, which is totally impractical.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 17 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8803



--- Comment #9 from deadalnix <deadalnix gmail.com> 2012-10-17 05:24:12 PDT ---
(In reply to comment #8)

 (In reply to comment #7)

 Well, I do think many valid uses include impure functions, even in sort. For
 instance for benchmarking purpose, for educational purpose, for caching.
 
 More importantly, pure function isn't enough. A pure function can return 2
 different objects. Even if the object's content will be the same, its identity
 will not, which is a problem in many cases (the example above is simplified, in
 my case that was the issue).


 
 I think this issue boils down to this: you are expecting something from map,
 which is does not advertise to do (any more). There is no bug.
 
 You could change this to an enhancement request, because you are asking for an
 additional feature.
 


That wasn't an additional feature. Using such method, it is easy to solve the
entire bug database within the day.

The spec was made that way for good reason : this is how map works in every
single language that have map and allow side effects.

This violate the least principle and expose filter and map internals.


 Note that if you do add caching for 'front', you still have the same problem if
 you try to use indexing. e.g.
 
 auto xs = [1, 2, 3];
 auto m = xs.map!(fun)();
 auto ref a = m[1], b = m[1];
 
 The only way this could guarantee to apply fun once is if it caches the entire
 range, which is totally impractical.


This can be solved by caching only 0 .. index . Or by caching within filter and
not map.

Or eventually by stating that this is not doable for indices. Most languages
don't allow index on map or create a temporary array automatically.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 17 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8803


William Moore <nyphbl8d gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |nyphbl8d gmail.com


--- Comment #10 from William Moore <nyphbl8d gmail.com> 2012-10-17 06:33:27 PDT
---
Changing the documentation to match does not necessarily make the code correct.
 In this case it means that the documentation is now broken as well.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 17 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8803


Andrei Alexandrescu <andrei metalanguage.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
                 CC|                            |andrei metalanguage.com
         Resolution|                            |WONTFIX


--- Comment #11 from Andrei Alexandrescu <andrei metalanguage.com> 2012-10-17
09:26:02 PDT ---
There are clear advantages and disadvantages of both approaches, and reasonable
people may disagree on the choice. I will close this; formerly map did cache
its current element, to puzzlement by its users. I changed the behavior a long
time ago, to much less puzzlement.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 17 2012
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8803



--- Comment #12 from deadalnix <deadalnix gmail.com> 2012-10-17 09:27:27 PDT ---
(In reply to comment #11)

 There are clear advantages and disadvantages of both approaches, and reasonable
 people may disagree on the choice. I will close this; formerly map did cache
 its current element, to puzzlement by its users. I changed the behavior a long
 time ago, to much less puzzlement.


Then filter should call .front twice.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 17 2012