Bug 5691 – walkLength() compatible with opApply()

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)

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.

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.

(In reply to comment #2) > to count the items of a lazy range I meant lazy iterable.

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.

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.

(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()).

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

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.

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

Couldn't walkLength simply be redefined to accept an isIterable argument? That covers ranges, opApply, and properly formed delegates. And to answer Jonathan, opApply has very important features that ranges do not. First and foremost, it can use the stack for iteration. This allows things like indexed iteration, iterating trees, and efficient iterating via a virtual interface. Second, ranges do not yet allow more than one item while iterating. I can't do: foreach(i, x; r) on a range. Not saying opApply is better in all cases, ranges do have just as important features, but opApply is more useful in certain important situations.

I agree that opApply has advantages over ranges. I'd also argue it lacks the level of control that would make it a useful abstraction. If we allow walkLength to work with isIterable, we really need to review all algorithms to see if they could also work with isIterable, and possibly adjust a number of them to use foreach. It's not impossible there might be some forking on static if (isIterable!...). Such an effort would be significant and might increase the size and complexity of std.algorithm. At this point in Phobos' design I think it's worth acknowledging that we can't accommodate every design in the book and we need to keep a watchful eye on complexity. (For example I am very seriously thinking of assuming cheap constructors, which would remove all the moveFront etc. functions).

I agree that we don't want to cater to all styles, at the expense of added complexity. I think actually, using isIterable, does not increase complexity immensely for walkLength. It covers the same ground as isInputRange, but with the added bonus of allowing any foreachable structure. One thing to note is, you cannot convert opApply (or similar) constructs into ranges. This means that any function/construct in std.algorithm or std.range that yields a range cannot be used on a generic isIterable type. For example, map yields a range, so it cannot accept opApply type arguments. In addition, any function which operates on multiple aggregates could not take opApply-based args because you can't iterate them in parallel easily. This eliminates quite a few functions. However, any functions that operate on the *whole* set of values from a range should be easily tweaked to also accept isIterable. For example, reduce, some forms of count, isSorted, etc. should be possible on any foreachable construct. I think we may find that a) the number of functions which can also accept isIterable types is pretty small and b) adding the ability to support opApply-based aggregates is not complex. It definitely needs more analysis before judging whether it makes sense. I agree that if you do walkLength, you should do all the functions that make sense. BTW, I just noticed that count(r) is identical to walkLength(r). Any reason for the duplication?

walkLength would need forking for opApply, so already for this first example we're looking at an increase in complexity. This is because walkLength against a range doesn't need to invoke front, so it uses a straight for loop. The difference between walkLength and count is that walkLength accepts a limit.

Reopening. If this gets closed, I think it should be closed as WONTFIX, not as INVALID. The request itself is not unreasonable. The argument against it is that the added complexity isn't worth the functionality. Generally, please give your reasoning when closing issues, especially when you haven't taken part in the discussion.

Sorry. (I think it was me who closed it - how can I see who did?) Yes, that's the reason - at some point we've got to pare down what we support. Reclosing (sic) as WONTFIX.

(In reply to Andrei Alexandrescu from comment #15) > Sorry. (I think it was me who closed it - how can I see who did?) It wasn't you. bb.temp closed it without comment. You can see it on the "History" page: https://issues.dlang.org/show_activity.cgi?id=5691 The link to that page is in the right column of the issue details, in parentheses behind the "Modified" date. Or just search the page for "History".

(In reply to ag0aep6g from comment #16) > (In reply to Andrei Alexandrescu from comment #15) > > Sorry. (I think it was me who closed it - how can I see who did?) > > It wasn't you. bb.temp closed it without comment. You can see it on the > "History" page: > https://issues.dlang.org/show_activity.cgi?id=5691 > The link to that page is in the right column of the issue details, in > parentheses behind the "Modified" date. Or just search the page for > "History". Based on the previous argumentation (see J.M.Davis) and the time elapsed since the report, I took the initiative to close. If it's an error, sorry. It's off topic but the fact is that there is a lot of phobos issues whose validity is discutable. Among the old reports, most of the invalid/already-fixed ones are closed now. Time to stop my initiative to find more of them, I guess.

FWIW, I agree with Andrei here (now). For one thing, walkLength would have to add the complexity of trying to infer the right parameters to pass to foreach. opApply has some usefulness, but much of it has been eroded. There are only a couple of advantages left: 1. ability to use recursion during iteration, 2. overloading based on loop variable types.