www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 5691] New: walkLength() compatible with opApply()

reply d-bugmail puremagic.com writes:
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



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: -------
Mar 03 2011
next sibling parent d-bugmail puremagic.com writes:
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



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: -------
Mar 03 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5691




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: -------
Mar 03 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5691






 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: -------
Mar 03 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5691




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: -------
Mar 03 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5691


Andrei Alexandrescu <andrei metalanguage.com> changed:

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



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: -------
Mar 03 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5691






 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: -------
Mar 03 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5691




16:29:17 PST ---




 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: -------
Mar 03 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5691




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: -------
Mar 03 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5691







 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: -------
Mar 03 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5691


Steven Schveighoffer <schveiguy yahoo.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |schveiguy yahoo.com



05:44:27 PST ---
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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Mar 04 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5691




07:41:35 PST ---
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).

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Mar 04 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5691




08:13:08 PST ---
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?

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Mar 04 2011
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5691




08:35:41 PST ---
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.

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