http://d.puremagic.com/issues/show_bug.cgi?id=5691

           Summary: walkLength() compatible with opApply()
           Product: D
           Version: D2
          Platform: x86
        OS/Version: Windows
            Status: NEW
          Keywords: rejects-valid
          Severity: normal
          Priority: P2
         Component: Phobos
        AssignedTo: nobody@puremagic.com
        ReportedBy: bearophile_hugs@eml.cc


--- Comment #0 from bearophile_hugs@eml.cc 2011-03-03 12:42:36 PST ---
std.range.walkLength() has to return the length of any collection or lazy
iterable that has a length property or is iterable, like a struct with
opApply():


import std.range: walkLength;
struct Iter {
    int stop;
    int opApply(int delegate(ref int) dg) {
        int result;
        foreach (i; 0 .. stop) {
            result = dg(i);
            if (result) break;
        }
        return result;
    }
}
void main() {
    assert(walkLength(Iter(10)) == 10);
}


But DMD 2.052 gives:
test.d(14): Error: template std.range.walkLength(Range) if
(isInputRange!(Range)) does not match any function template declaration
test.d(14): Error: template std.range.walkLength(Range) if
(isInputRange!(Range)) cannot deduce template function from argument types
!()(Iter)

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

http://d.puremagic.com/issues/show_bug.cgi?id=5691


Jonathan M Davis <jmdavisProg@gmx.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|rejects-valid               |
                 CC|                            |jmdavisProg@gmx.com
         OS/Version|Windows                     |All
           Severity|normal                      |enhancement


--- Comment #1 from Jonathan M Davis <jmdavisProg@gmx.com> 2011-03-03 13:34:19 PST ---
Why? walkLength specifically works on _ranges_. A struct with opApply is _not_ a range. I see no reason for it to work with opApply. Not only is it in std.range, but it _specifically_ says that it works on ranges. And since when do the functions in std.range or std.algorithm work on structs with opApply? They all have template constraints like isForwardRange, which sure isn't going to work on a struct with opApply. walkLength isn't even design to work on a container or collection. It works on _ranges_. That's it. I see no reason to contort it to work with opApply.

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

http://d.puremagic.com/issues/show_bug.cgi?id=5691



--- Comment #2 from bearophile_hugs@eml.cc 2011-03-03 14:38:02 PST ---
Then do you want to add another function to Phobos to count the items of a lazy
range created by opApply? Or to do that do you want me to use a wasteful
array(Iter(10)).length (or a foreach loop)?

Phobos and walkLength() need to become a bit more flexible.
If things in std.range are meant to work on ranges only, then I suggest to move
the improved walkLength() to std.algorithm.

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

http://d.puremagic.com/issues/show_bug.cgi?id=5691



--- Comment #3 from bearophile_hugs@eml.cc 2011-03-03 14:38:46 PST ---
(In reply to comment #2)
> to count the items of a lazy range

I meant lazy iterable.

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

http://d.puremagic.com/issues/show_bug.cgi?id=5691



--- Comment #4 from Jonathan M Davis <jmdavisProg@gmx.com> 2011-03-03 14:47:19 PST ---
And since when is a range created by opApply? It's not a range until it's a type with the appropriate functions on it. Sure, you could feed a struct with opApply to std.array.array and get an array, which is then a range. But something that uses opApply is _not_ a range.

opApply is designed specifically for use with foreach. It is not a range and is similar to a range only in that it is related to iterating over a list of items. If you want to treat something with opApply as a range, then make it a range or wrap it in one. It's going to rightfully fail for isInputRange, isForwardRange, etc. It is _not_ a range and should not be treated as one.

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

http://d.puremagic.com/issues/show_bug.cgi?id=5691


Andrei Alexandrescu <andrei@metalanguage.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |andrei@metalanguage.com


--- Comment #5 from Andrei Alexandrescu <andrei@metalanguage.com> 2011-03-03 15:26:56 PST ---
We could define some algorithms to work with opApply, but that would blow up the size of std.algorithm and we'd hit http://d.puremagic.com/issues/show_bug.cgi?id=3923.

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

http://d.puremagic.com/issues/show_bug.cgi?id=5691



--- Comment #6 from bearophile_hugs@eml.cc 2011-03-03 16:15:35 PST ---
(In reply to comment #5)
> We could define some algorithms to work with opApply, but that would blow up the size of std.algorithm

I agree that std.algorithm already contains many functions (as in future
std.container if it doesn't split). But I don't think this can justify keeping
walkLength() semantic as an amputee. A possible solution is then to keep
walkLength() inside std.range, despite it working with opApply() too.

One of the purposes of a good standard library is to reduce the useful functions I have to write and maintain. I will need to keep a walkLength-like function to perform this complete semantics.


> and we'd hit http://d.puremagic.com/issues/show_bug.cgi?id=3923.

walkLength() returns an integral value that represents the walking length of
the iterable, regardless the way the iterable is implemented. This doesn't make
the function harder to understand (but a struct/class is free to have more than
one opApply(), that yield a different number of items. walkLength() has to walk
the single-item-yield opApply()).

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

http://d.puremagic.com/issues/show_bug.cgi?id=5691



--- Comment #7 from Andrei Alexandrescu <andrei@metalanguage.com> 2011-03-03 16:29:17 PST ---
(In reply to comment #6)
> (In reply to comment #5)
> > We could define some algorithms to work with opApply, but that would blow up the size of std.algorithm
> 
> I agree that std.algorithm already contains many functions (as in future
> std.container if it doesn't split). But I don't think this can justify keeping
> walkLength() semantic as an amputee. A possible solution is then to keep
> walkLength() inside std.range, despite it working with opApply() too.
> 
> One of the purposes of a good standard library is to reduce the useful functions I have to write and maintain. I will need to keep a walkLength-like function to perform this complete semantics.

Instead you may want to use the range interface and benefit of walkLength and others.

> > and we'd hit http://d.puremagic.com/issues/show_bug.cgi?id=3923.
> 
> walkLength() returns an integral value that represents the walking length of
> the iterable, regardless the way the iterable is implemented. This doesn't make
> the function harder to understand (but a struct/class is free to have more than
> one opApply(), that yield a different number of items. walkLength() has to walk
> the single-item-yield opApply()).


Definitely increases complexity because it requires the usual type discrimination and an extra version. But let's say that's manageable. The worse problem is that it creates a precedent - then why not do the same for other algorithms (including find itself of which you complain already)? Please abide to your own standards.

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

http://d.puremagic.com/issues/show_bug.cgi?id=5691



--- Comment #8 from Jonathan M Davis <jmdavisProg@gmx.com> 2011-03-03 16:38:57 PST ---
Honestly, whenever I see anyone discussing opApply, my first reaction is to question why they're using it in the first place. In almost all cases, ranges do what opApply can do, and they do it better. There _are_ a few cases where opApply is still better (e.g. you can get indices out of opApply with foreach but not ranges), but in most cases, opApply is unnecessary. And a lazily iteraterable struct sounds _very_ much like it should be range.

std.range and std.algorithm are designed around ranges, not opApply. If anything, the fact that someone needs to use opApply for something rather than a range indicates that ranges need to be improved, not that we need to take our range-based functions are make them work with opApply. As Andrei point out, the added complexity would be quite large, and we definitely don't want that. Really, if you want to use range-based stuff, you should be using ranges. And from the little you've said about your use case, it seems like a _prime_ example of something that should be a range rather than use opApply.

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

http://d.puremagic.com/issues/show_bug.cgi?id=5691



--- Comment #9 from bearophile_hugs@eml.cc 2011-03-03 16:54:17 PST ---
(In reply to comment #7)

> Instead you may want to use the range interface and benefit of walkLength and others.

The semantics of opApply() is inverted compared to the range interface (the opApply() is similar to the Python yield, with a worse syntax). There are situations where for my mind the semantics of opApply()/yield turns out to be more natural. Example: I'm able to write a tree visit in moments using yield, but it takes me some reflection to perform it with the range interface. Maybe it's just a limit/problem of my mind. In bug 5660 I have also tried to explain that sometimes it's also a compact way to write iterable things.


> The worse
> problem is that it creates a precedent - then why not do the same for other
> algorithms (including find itself of which you complain already)?

I see. For me there's a difference between things like map/filter and
array/walkLength because a map over a opApply() can't produce a range
(efficiently), so I have not seriously asked map() to accept an Iter struct
like that.

On the other hand array/walkLength don't need to spit out an iterable, they just scan it, so in my mind they are allowed to be able to digest any kind of iterable.

So is it right for find() to work on opApply()? I'd like the answer to be
positive, but I am willing to accept a negative answer.

I'm trying to help, but I leave you the final word on Phobos, and you often know better. Feel free to close this bug report when you have decided. Sorry for my philosophic dilemmas :)


> Please abide to your own standards.

My standards are complex, because reality is complex.

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