[Issue 4264] Support opApply in std.algorithm, std.range where possible
https://issues.dlang.org/show_bug.cgi?id=4264 Andrei Alexandrescu changed: What|Removed |Added Status|NEW |RESOLVED CC||and...@erdani.com Resolution|--- |WONTFIX --- Comment #12 from Andrei Alexandrescu --- We don't plan to support internal iteration via opApply in range algorithms. It would add too much complication for too little benefit. --
[Issue 4264] Support opApply in std.algorithm, std.range where possible
https://issues.dlang.org/show_bug.cgi?id=4264 Andrei Alexandrescu changed: What|Removed |Added Version|unspecified |D2 --
[Issue 4264] Support opApply in std.algorithm, std.range where possible
http://d.puremagic.com/issues/show_bug.cgi?id=4264 --- Comment #11 from bearophile_h...@eml.cc 2012-08-28 15:33:46 PDT --- This code: import std.stdio: writeln; struct Iter2 { int stop, current; @property int front() { return current; } @property bool empty() { return current == stop; } void popFront() { current++; } } void main() { writeln(Iter2(10)); } Shows that writeln supports the range protocol: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] While this code: import std.stdio: writeln; struct Iter { int stop; int opApply(int delegate(ref int) dg) { int result; for (int i = 0; i < stop; i++) { result = dg(i); if (result) break; } return result; } } void main() { writeln(Iter(10)); } Outputs this, showing writeln doesn't support opApply iterables: Iter(10) I'd like writeln() to show the items here too. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 4264] Support opApply in std.algorithm, std.range where possible
http://d.puremagic.com/issues/show_bug.cgi?id=4264 --- Comment #10 from kenn...@gmail.com 2011-05-08 00:00:18 PDT --- *** Issue 5952 has been marked as a duplicate of this issue. *** -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 4264] Support opApply in std.algorithm, std.range where possible
http://d.puremagic.com/issues/show_bug.cgi?id=4264 --- Comment #9 from bearophile_h...@eml.cc 2010-08-22 07:48:32 PDT --- > Maybe you should bring it up on the newsgroup. http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=115950 -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 4264] Support opApply in std.algorithm, std.range where possible
http://d.puremagic.com/issues/show_bug.cgi?id=4264 --- Comment #8 from bearophile_h...@eml.cc 2010-08-22 07:39:44 PDT --- Thank you for your answer David Simcha. > Since everything you mention except the opApply issue is fixed either > in 2.048 or in SVN, Yes, indeed now all tests but the one that uses map() work. I agree with more or less all your points here. And I have no final answer for your doubts. Here are few comments. > Even if these get fixed, supporting ref correctly would be non-trivial > enough that I don't want to implement everything w/o ref support and > then have to go back later and add ref support. I see. Working and fixing the std lib is a lot of work, so I suggest to keep Phobos as short (as in number of lines) as possible, so when bugs gets fixed you don't need a week to update it. A possible good solution is to wait and not support opApply until those bugs are fixed, to reduce your work. Sometimes the typical laziness of the programmer is positive. > 2. If we start building higher order iterables out of opApply, things could > become slow as molasses through multiple layers of delegate calls. I know LDC > can inline these at least in simple cases, but what about when you have N > 1 > levels of them? LDC can currently inline one level of opApply, but probably not much more than that. Performance may indeed be reduced (even if we assume LLVM will get a bit better with time). On the other hand: - D is not a functional language, D programmers don't write map(filter(chain(map(... all the time. They usually use no more than one or two level of lazy chaining. - Several operations (like zip) are not possible with opApply, so this reduces the places where they may be abused and where they can slow down code. - In a normal program a good percentage of its code doesn't need to be high-performance, for example you need to covert to numbers few (no more than 5) strings coming from args[] into numbers, and you use a map!(to!(int))(args[1..$]). Many (but not all) of the usages of std.algorithm are to shorten code, to make it more readable or less buggy, but they are not used where max performance is necessary. This means that in practice a map() performed on a struct that defines opApply is often not a performance problem. (But programmers will need to be careful). > 3. This is a big enough change to the way std.range/std.algorithm work that I > think it needs to be discussed first, rather than just being checked in one > day > like a bug fix or minor enhancement. Maybe you should bring it up on the > newsgroup. I will write a small post about this in the main D newsgroup soon then. I don't have a final answer for your doubts. Generally I am not for pure solutions, I think that ranges are good, but life is complex, and if you try to cram everything into a single abstraction, you will have problems. If std.algorithm doesn't support opApply at all, then opApply itself becomes much less useful. In D1 I have seen that you can implement most of std.algorithm using opApply only. Supporting opApply in Phobos may be a lot of work, but it's work done once. Then all D programs are able to use this hard work. This is why I like std libs as flexible as possible, to make them support both fixed-sized arrays and opApply, because this later makes user code simpler and more uniform, and this Python shows that this usage uniformity is _very_ important to make the language (its std lib) handy and quick to use. Another thing about ranges is more general. opApply and ranges may be used for the same purposes, like to create a lazy generator of items, or to offer a way to scan the leaves of a tree through a simple foreach. But if you try to write a tree visit using opApply or using the Range protocol you see that they are not the same thing. You may see other examples here: http://code.activestate.com/recipes/221457/ For example (Python 2.x code): # Inverse Gray code def A006068(): yield 0 for x in A006068(): if x & 1: yield 2*x+1 yield 2*x else: if x: yield 2*x yield 2*x+1 It's not too much hard to implement this using opApply, the code is similar to that Python code, just much more noisy. But if you use the Range protocol you need to manage the state manually. With this I am trying to say that the Range protocol doesn't replace opApply, there are algorithms more naturally implemented with opApply. If you try to cram everything into the Range idea, you risk losing something. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 4264] Support opApply in std.algorithm, std.range where possible
http://d.puremagic.com/issues/show_bug.cgi?id=4264 David Simcha changed: What|Removed |Added Depends on||2443, 4707 Summary|Various std.algorithm.map |Support opApply in |problems|std.algorithm, std.range ||where possible Severity|normal |enhancement --- Comment #7 from David Simcha 2010-08-21 19:54:17 PDT --- Please disregard my last post. I hit commit by accident when I was half-done typing it. Since everything you mention except the opApply issue is fixed either in 2.048 or in SVN, and the discussion has moved beyond Map to std.algorithm/std.range in general, I've changed the name of this bug and made it into an enhancement request. I've thought about supporting opApply in some std.range and std.algorithm types. I think it's useful and conceptually feasible (ignoring implementation minutiae) for at least the following, and probably more: std.algorithm.map std.algorithm.filter std.algorithm.uniq std.algorithm.until std.range.chain std.range.retro (if your object defines opApplyReverse) std.range.stride std.range.cycle It's definitely not feasible for anything that requires random access or manipulating multiple ranges in lockstep, backtracking other than to the beginning of the iteration, or doing stuff with ranges of ranges (Transversal, etc). Here are some of the bigger issues I see at the implementation level: 1. Bugs 2443, 4707 make dealing correctly with ref in the opApply case near impossible. I've made them blockers for this issue. Even if these get fixed, supporting ref correctly would be non-trivial enough that I don't want to implement everything w/o ref support and then have to go back later and add ref support. 2. If we start building higher order iterables out of opApply, things could become slow as molasses through multiple layers of delegate calls. I know LDC can inline these at least in simple cases, but what about when you have N > 1 levels of them? 3. This is a big enough change to the way std.range/std.algorithm work that I think it needs to be discussed first, rather than just being checked in one day like a bug fix or minor enhancement. Maybe you should bring it up on the newsgroup. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---