www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Why is std.algorithm so complicated to use?

reply Jacob Carlborg <doob me.com> writes:
Almost every time I'm trying to use std.algorithm I run into some kind 
of error, for what seems to be fairly trivial and what one would expect 
to work. It feels like I'm constantly fighting with std.algorithm. For 
example:

import std.algorithm;
import std.range;

struct Foo {}

auto f = Foo();
auto foos = [f];
auto foo = foos.map!(x => "foo");
auto bar = foo.chain("bar");

This simple example result in the follow error:

http://pastebin.com/E4LV2UBE

Another example:

auto str = ["foo", "bar"].map!(x => x);
auto f = str.sort();

Results in:

http://pastebin.com/BeePWQk9

I'm using DMD 2.059.

-- 
/Jacob Carlborg
Jul 09 2012
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 7/9/12 4:09 PM, Jacob Carlborg wrote:
 Almost every time I'm trying to use std.algorithm I run into some kind
 of error, for what seems to be fairly trivial and what one would expect
 to work. It feels like I'm constantly fighting with std.algorithm. For
 example:

 import std.algorithm;
 import std.range;

 struct Foo {}

 auto f = Foo();
 auto foos = [f];
 auto foo = foos.map!(x => "foo");
 auto bar = foo.chain("bar");

 This simple example result in the follow error:

 http://pastebin.com/E4LV2UBE
So foo is a range of strings, because each element of it is a string. Then you want to chain a range of strings with a string, which is a range of dchar. That doesn't work, and I agree the error message should be more informative. To fix the example, write auto bar = foo.chain(["bar"]);
 Another example:

 auto str = ["foo", "bar"].map!(x => x);
 auto f = str.sort();

 Results in:

 http://pastebin.com/BeePWQk9
The first error message is at clear as it goes: Error: r[i2] is not an lvalue Andrei
Jul 09 2012
next sibling parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 07/09/2012 01:16 PM, Andrei Alexandrescu wrote:
 On 7/9/12 4:09 PM, Jacob Carlborg wrote:
 auto str = ["foo", "bar"].map!(x => x);
 auto f = str.sort();

 Results in:

 http://pastebin.com/BeePWQk9
The first error message is at clear as it goes: Error: r[i2] is not an lvalue
And a quick fix is to make an array first: auto str = ["foo", "bar"].map!(x => x)().array(); Also note the added () for map, which is needed when compiled with -property. Ali
Jul 09 2012
next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 07/09/2012 10:23 PM, Ali Çehreli wrote:
 On 07/09/2012 01:16 PM, Andrei Alexandrescu wrote:
  > On 7/9/12 4:09 PM, Jacob Carlborg wrote:

  >> auto str = ["foo", "bar"].map!(x => x);
  >> auto f = str.sort();
  >>
  >> Results in:
  >>
  >> http://pastebin.com/BeePWQk9
  >
  > The first error message is at clear as it goes:
  >
  > Error: r[i2] is not an lvalue

 And a quick fix is to make an array first:

 auto str = ["foo", "bar"].map!(x => x)().array();

 Also note the added () for map, which is needed when compiled with
 -property.

 Ali
-property should be killed. I mean, we can have either map!(x => x)().array() or map!(x => x).array It's blatantly obvious which one we want, especially when there are more than two chained/nested calls. -property is good only for bracket spam. We need to implement property properly, that is, property function pairs behave like fields and other functions can be called with the parentheses left off. IIRC that is how it was designed initially.
Jul 09 2012
prev sibling parent reply Jacob Carlborg <doob me.com> writes:
On 2012-07-09 22:23, Ali Çehreli wrote:

 And a quick fix is to make an array first:

 auto str = ["foo", "bar"].map!(x => x)().array();

 Also note the added () for map, which is needed when compiled with
 -property.
If I first have to convert it to an array, then sort and then convert it to an array again. Isn't that missing the whole point of ranges. -- /Jacob Carlborg
Jul 09 2012
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Tuesday, July 10, 2012 08:51:29 Jacob Carlborg wrote:
 On 2012-07-09 22:23, Ali =C3=87ehreli wrote:
 And a quick fix is to make an array first:
=20
 auto str =3D ["foo", "bar"].map!(x =3D> x)().array();
=20
 Also note the added () for map, which is needed when compiled with
 -property.
=20 If I first have to convert it to an array, then sort and then convert=
it
 to an array again. Isn't that missing the whole point of ranges.
The problem is that map is lazy, so it can't be a random access range, = and=20 sort requires a random access range. If map were eager, it would just b= e=20 creating an array anyway. But you don't need to convert it to an array = again=20 after sorting it. sort returns a SortedRange so that functions such as = find can=20 know that it's sorted and take advantage of it, but it sorts in place=20= (SortedRange is just a wrapper around the range which was passed in and= copies=20 no data), so once you've called sort on your array, it's sorted. You ca= n just=20 ignore the return type if you're not looking to pass it to a function w= hich=20 would take advantage of the fact that it's sorted. But since SortedRang= e=20 _isn't_ lazy (it's just a wrapper around the newly sorted original rang= e,=20 after all), it's still a random access range and will work with functio= ns=20 which require that (unlike map). You only end up with a range with fewer capabilities than the original = when=20 the algorithm itself intrinsicly requires it, and that sort of range is= =20 generally lazy (since it's more efficient that way, and making it non-l= azy would=20 be equivalent to wrapping it in a call to array anyway). - Jonathan M Davis
Jul 10 2012
next sibling parent Jacob Carlborg <doob me.com> writes:
On 2012-07-10 09:04, Jonathan M Davis wrote:

 The problem is that map is lazy, so it can't be a random access range, and
 sort requires a random access range. If map were eager, it would just be
 creating an array anyway. But you don't need to convert it to an array again
 after sorting it. sort returns a SortedRange so that functions such as find can
 know that it's sorted and take advantage of it, but it sorts in place
 (SortedRange is just a wrapper around the range which was passed in and copies
 no data), so once you've called sort on your array, it's sorted. You can just
 ignore the return type if you're not looking to pass it to a function which
 would take advantage of the fact that it's sorted. But since SortedRange
 _isn't_ lazy (it's just a wrapper around the newly sorted original range,
 after all), it's still a random access range and will work with functions
 which require that (unlike map).

 You only end up with a range with fewer capabilities than the original when
 the algorithm itself intrinsicly requires it, and that sort of range is
 generally lazy (since it's more efficient that way, and making it non-lazy
would
 be equivalent to wrapping it in a call to array anyway).
So it's basically what I said. Sine I want an array as the result of the operation I do need to convert it to an array again. For my need, it just seem to be more trouble to use std.algorithm. -- /Jacob Carlborg
Jul 10 2012
prev sibling parent reply "Simen Kjaeraas" <simen.kjaras gmail.com> writes:
On Tue, 10 Jul 2012 09:04:31 +0200, Jonathan M Davis <jmdavisProg gmx.com>  
wrote:

 The problem is that map is lazy, so it can't be a random access range,
Sure it can. If the underlying range is random-access or bidirectional, so can map be. What can't be (as easily) done is caching of elements. -- Simen
Jul 10 2012
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 7/10/12 8:27 AM, Simen Kjaeraas wrote:
 On Tue, 10 Jul 2012 09:04:31 +0200, Jonathan M Davis
 <jmdavisProg gmx.com> wrote:

 The problem is that map is lazy, so it can't be a random access range,
Sure it can. If the underlying range is random-access or bidirectional, so can map be. What can't be (as easily) done is caching of elements.
Indeed map currently maps random-access ranges to random-access ranges. Andrei
Jul 10 2012
prev sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Tuesday, July 10, 2012 14:27:14 Simen Kjaeraas wrote:
 On Tue, 10 Jul 2012 09:04:31 +0200, Jonathan M Davis <jmdavisProg gmx.com>
 
 wrote:
 The problem is that map is lazy, so it can't be a random access range,
Sure it can. If the underlying range is random-access or bidirectional, so can map be. What can't be (as easily) done is caching of elements.
Ah, you're right. I'm too used to thinking about filter, but map doesn't change the number of elements, so it works just fine as random access (though it risks being an efficient way of doing things if the function using it accessing its elements multiple times, since it's going to have to call the predicate every time that the element is accessed, whereas if you just iterate over the range, then odds are that you only access the element once). - Jonathan M Davis
Jul 10 2012
prev sibling next sibling parent Manfred Nowak <svv1999 hotmail.com> writes:
Andrei Alexandrescu wrote:

 auto str = ["foo", "bar"].map!(x => x);
 auto f = str.sort();
[...]
 The first error message is at clear as it goes:
 Error: r[i2] is not an lvalue
... and I panic on reading your answer, because I do not find a `r' nor an `i2' in the source. Therefore "is not an lvalue" stays without sense. Some time ago Walter expressed, that he does not want D to become a language, which only specialists can interpret. But if error messages are part of a language and your "clear"-voting will stay, then "Hades" might become D's middle name. -manfred
Jul 09 2012
prev sibling next sibling parent reply Jacob Carlborg <doob me.com> writes:
On 2012-07-09 22:16, Andrei Alexandrescu wrote:

 So foo is a range of strings, because each element of it is a string.
 Then you want to chain a range of strings with a string, which is a
 range of dchar. That doesn't work, and I agree the error message should
 be more informative.
Is that by design or something that can be fixed?
 To fix the example, write

 auto bar = foo.chain(["bar"]);
I think that's an ugly workaround.
 Another example:

 auto str = ["foo", "bar"].map!(x => x);
 auto f = str.sort();

 Results in:

 http://pastebin.com/BeePWQk9
The first error message is at clear as it goes: Error: r[i2] is not an lvalue
"Clear as it goes" WTF? Are you nuts? It's an insanly bad error message, I have no "r" in my code. Is it too much to ask to be able to sort a range? This just proves that std.algorithm is complicated to use. It's very unintuitive. What I really want is this, but ranges doesn't work like that: Foo f = Foo(); Foo[] foos = [f]; string[] = foos.map!(x => "foo"); string[] bar = foo ~= "foo"; And: string[] str = ["foo", "bar"].map!(x => x); string[] f = str.sort(); -- /Jacob Carlborg
Jul 09 2012
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 7/10/12 2:50 AM, Jacob Carlborg wrote:
 On 2012-07-09 22:16, Andrei Alexandrescu wrote:

 So foo is a range of strings, because each element of it is a string.
 Then you want to chain a range of strings with a string, which is a
 range of dchar. That doesn't work, and I agree the error message should
 be more informative.
Is that by design or something that can be fixed?
We can arrange things in the library that a custom message is issued, or in the compiler to do it once for all. At any rate whenever there's an error pointing somewhere in the library's code that's an insufficient template constraint that should be fixed.
 To fix the example, write

 auto bar = foo.chain(["bar"]);
I think that's an ugly workaround.
Well I made minimal changes. Besides I don't know what the intent is.
 Another example:

 auto str = ["foo", "bar"].map!(x => x);
 auto f = str.sort();

 Results in:

 http://pastebin.com/BeePWQk9
The first error message is at clear as it goes: Error: r[i2] is not an lvalue
"Clear as it goes" WTF? Are you nuts?
To the extent any of us is somewhat nuts, yes, I am. I'm also a fan of civil conversation.
 It's an insanly bad error message,
 I have no "r" in my code. Is it too much to ask to be able to sort a range?
Indeed I agree there should be no error in library code. What I meant to say was, when I saw the code I thought "I bet this is an lvalue thing", and then when I saw lvalue in the error I was satisfied.
 This just proves that std.algorithm is complicated to use. It's very
 unintuitive.

 What I really want is this, but ranges doesn't work like that:

 Foo f = Foo();
 Foo[] foos = [f];
 string[] = foos.map!(x => "foo");
 string[] bar = foo ~= "foo";
I understand. So you need to use array() to convert the lazy map result into an eager array. I disagree this is unintuitive, if it were then very little of D would make sense are lazy, non-array ranges are everywhere.
 And:

 string[] str = ["foo", "bar"].map!(x => x);
 string[] f = str.sort();
Same here. map() does not return arrays, and for very good reasons. Andrei
Jul 10 2012
next sibling parent reply Jacob Carlborg <doob me.com> writes:
On 2012-07-10 15:28, Andrei Alexandrescu wrote:

 We can arrange things in the library that a custom message is issued, or
 in the compiler to do it once for all. At any rate whenever there's an
 error pointing somewhere in the library's code that's an insufficient
 template constraint that should be fixed.
I mean, is it possible to have the original code work? auto bar = foo.chain("bar"); Or perhaps more appropriate: auto bar = foo.append("bar");
 Well I made minimal changes. Besides I don't know what the intent is.
Have a look at this: https://github.com/jacob-carlborg/dstep/blob/master/dstep/translator/Translator.d#L217 I was going to replace the foreach-loop in the above code with a call to "map". But "map" returns a range, not an array. Therefor the append at line 245 won't work. How would I do line 245 if "params" is a range returned by "map"? It seems unnecessary to have to convert the range to an array before "join" is called on line 247.
 Indeed I agree there should be no error in library code. What I meant to
 say was, when I saw the code I thought "I bet this is an lvalue thing",
 and then when I saw lvalue in the error I was satisfied.
Jonathan has already reported these two bugs.
 I understand. So you need to use array() to convert the lazy map result
 into an eager array. I disagree this is unintuitive, if it were then
 very little of D would make sense are lazy, non-array ranges are
 everywhere.
Tell me what is the point of std.algorithm and ranges if I have to convert every single result of an algorithm to an array before I can use it with an other algorithm? I thought the whole idea was to avoid allocations between different usages of algorithms. -- /Jacob Carlborg
Jul 10 2012
next sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 10-Jul-12 17:56, Jacob Carlborg wrote:
 On 2012-07-10 15:28, Andrei Alexandrescu wrote:

 We can arrange things in the library that a custom message is issued, or
 in the compiler to do it once for all. At any rate whenever there's an
 error pointing somewhere in the library's code that's an insufficient
 template constraint that should be fixed.
I mean, is it possible to have the original code work? auto bar = foo.chain("bar"); Or perhaps more appropriate: auto bar = foo.append("bar");
 Well I made minimal changes. Besides I don't know what the intent is.
Have a look at this: https://github.com/jacob-carlborg/dstep/blob/master/dstep/translator/Translator.d#L217
I'm not sure how map can fit there. If anything you need a foreach (and you have it;) ) to build a _string_. I'd rather output ',' right there inside of loop. Thus avoiding costly join and appending to a new buffer on each iteration. Other then doing it with Appender and generalizing to any OutputRange I fail to see a problem.
 I was going to replace the foreach-loop in the above code with a call to
 "map". But "map" returns a range, not an array. Therefor the append at
 line 245 won't work. How would I do line 245 if "params" is a range
 returned by "map"?

 It seems unnecessary to have to convert the range to an array before
 "join" is called on line 247.

 Indeed I agree there should be no error in library code. What I meant to
 say was, when I saw the code I thought "I bet this is an lvalue thing",
 and then when I saw lvalue in the error I was satisfied.
Jonathan has already reported these two bugs.
 I understand. So you need to use array() to convert the lazy map result
 into an eager array. I disagree this is unintuitive, if it were then
 very little of D would make sense are lazy, non-array ranges are
 everywhere.
Tell me what is the point of std.algorithm and ranges if I have to convert every single result of an algorithm to an array before I can use it with an other algorithm? I thought the whole idea was to avoid allocations between different usages of algorithms.
Speed and generality. Think removing temporary arrays. And while a lot of folks won't every use things other then arrays power users sure as hell would. -- Dmitry Olshansky
Jul 10 2012
parent Jacob Carlborg <doob me.com> writes:
On 2012-07-10 16:49, Dmitry Olshansky wrote:

 I'm not sure how map can fit there. If anything you need a foreach (and
 you have it;) ) to build a _string_. I'd rather output ',' right there
 inside of loop. Thus avoiding costly join and appending to a new buffer
 on each iteration.
Sure if remove the call to "join" and build a single string from the beginning, then a foreach would be the right approach. But if you look at the code as it is now the foreach-loop maps an array of "Parameter" to an array of "string".
 Speed and generality. Think removing temporary arrays. And while a lot
 of folks won't every use things other then arrays power users sure as
 hell would.
I have only been able to remove very few temporary arrays. -- /Jacob Carlborg
Jul 10 2012
prev sibling next sibling parent reply travert phare.normalesup.org (Christophe Travert) writes:
Jacob Carlborg , dans le message (digitalmars.D:171685), a écrit :
 I mean, is it possible to have the original code work?
 
 auto bar = foo.chain("bar");
 
 Or perhaps more appropriate:
 
 auto bar = foo.append("bar");
What is wrong with foo.chain(["bar"])? If you do not want the heap allocation of the array, you can create a one-element range to feed to chain (maybe such a thing could be placed in phobos, next to takeOne). struct OneElementRange(E) { E elem; bool passed; property ref E front() { return elem; } void popFront() { passed = true; } property bool empty() { return passed; } property size_t length() { return 1-passed; } //... } You can't expect chain to work the same way as run-time append. A compile-time append would be very inefficient if misused.
 https://github.com/jacob-carlborg/dstep/blob/master/dstep/translator/Translator.d#L217
you might try this (untested) string function(Parameter) stringify = (x) { return (x.isConst? "const("~x.type~")": x.type) ~ (x.name.any?" "~translateIdentifier(x.name):""); } auto params = parameters .map!stringify() .chain(variadic? []: ["..."]) .joiner(", "); context ~= params; I am not sure this will be more efficient. joiner may be slowed down by the fact that it is called with a chain result, which is slower on front. But at leat you save yourself the heap-allocation of the params array*. I would use: context ~= parameters.map!stringify().joiner(", "); if (variadic) context ~= ", ..."; To make the best implementation would require to know how the String context works. *Note that here, stringify is not lazy, and thus allocates. It could be a chain or a joiner, but I'm not sure the result would really be more efficient.
Jul 10 2012
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 7/10/12 11:11 AM, Christophe Travert wrote:
 If you do not want the heap allocation of the array, you can create a
 one-element range to feed to chain (maybe such a thing could be placed
 in phobos, next to takeOne).

 struct OneElementRange(E)
 {
    E elem;
    bool passed;
     property ref E front() { return elem; }
    void popFront() { passed = true; }
     property bool empty() { return passed; }
     property size_t length() { return 1-passed; }
    //...
 }
Yah, probably we should add something like this: auto singletonRange(E)(E value) { return repeat(value).takeExactly(1); } I don't think it would be considerably less efficient than a handwritten specialization. But then I've been wrong before in assessing efficiency. Andrei
Jul 10 2012
next sibling parent reply "Daniel Murphy" <yebblies nospamgmail.com> writes:
"Andrei Alexandrescu" <SeeWebsiteForEmail erdani.org> wrote in message 
news:jthiba$2cg0$1 digitalmars.com...
 On 7/10/12 11:11 AM, Christophe Travert wrote:
 If you do not want the heap allocation of the array, you can create a
 one-element range to feed to chain (maybe such a thing could be placed
 in phobos, next to takeOne).

 struct OneElementRange(E)
 {
    E elem;
    bool passed;
     property ref E front() { return elem; }
    void popFront() { passed = true; }
     property bool empty() { return passed; }
     property size_t length() { return 1-passed; }
    //...
 }
Yah, probably we should add something like this: auto singletonRange(E)(E value) { return repeat(value).takeExactly(1); } I don't think it would be considerably less efficient than a handwritten specialization. But then I've been wrong before in assessing efficiency. Andrei
Could it be extended to accept multiple values? (sort of like chain) eg. foreach(x; makeRange(23, 7, 1990)) // NO allocations! { .... } I would use this in a lot of places I currently jump through hoops to get a static array without allocating.
Jul 10 2012
parent reply travert phare.normalesup.org (Christophe Travert) writes:
"Daniel Murphy" , dans le message (digitalmars.D:171720), a écrit :
 Could it be extended to accept multiple values? (sort of like chain)
 eg.
 foreach(x; makeRange(23, 7, 1990)) // NO allocations!
 {
     ....
 }
 I would use this in a lot of places I currently jump through hoops to get a 
 static array without allocating. 
That's a good idea. IMHO, the real solution would be to make an easy way to create static arrays, and slice them when you want a range. -- Christophe I it were just me, array litterals would be static, and people should use .dup when they want a a surviving slice. Well, if it were just me, all function signature should tell when references to data escape the scope of the function, and all data would be allocated automatically where it should by the compiler.
Jul 10 2012
parent reply "Daniel Murphy" <yebblies nospamgmail.com> writes:
"Christophe Travert" <travert phare.normalesup.org> wrote in message 
news:jthmu8$2s5b$1 digitalmars.com...
 "Daniel Murphy" , dans le message (digitalmars.D:171720), a écrit :
 Could it be extended to accept multiple values? (sort of like chain)
 eg.
 foreach(x; makeRange(23, 7, 1990)) // NO allocations!
 {
     ....
 }
 I would use this in a lot of places I currently jump through hoops to get 
 a
 static array without allocating.
That's a good idea. IMHO, the real solution would be to make an easy way to create static arrays, and slice them when you want a range.
It's not quite the same thing, static arrays are not ranges and once you slice them you no longer have a value type, and might be referring to stack allocated data. With... this thing, the length/progress is not encoded in the type (making it rangeable) but the data _is_ contained in the type, making it safe to pass around. The best of both worlds, in some situations. An easy way to get static arrays would be great too.
 I it were just me, array litterals would be static, and people
 should use .dup when they want a a surviving slice.
It used to be like that. Most of the time you don't really want a static array.
Jul 10 2012
next sibling parent reply travert phare.normalesup.org (Christophe Travert) writes:
"Daniel Murphy" , dans le message (digitalmars.D:171741), a écrit :
 "Christophe Travert" <travert phare.normalesup.org> wrote in message 
 news:jthmu8$2s5b$1 digitalmars.com...
 "Daniel Murphy" , dans le message (digitalmars.D:171720), a écrit :
 Could it be extended to accept multiple values? (sort of like chain)
 eg.
 foreach(x; makeRange(23, 7, 1990)) // NO allocations!
 {
     ....
 }
 I would use this in a lot of places I currently jump through hoops to get 
 a
 static array without allocating.
That's a good idea. IMHO, the real solution would be to make an easy way to create static arrays, and slice them when you want a range.
It's not quite the same thing, static arrays are not ranges and once you slice them you no longer have a value type, and might be referring to stack allocated data. With... this thing, the length/progress is not encoded in the type (making it rangeable) but the data _is_ contained in the type, making it safe to pass around. The best of both worlds, in some situations.
OK, I see. This goes against the principle that ranges are small and easy to copy arround, but it can be useful when you know what you are doing, or when the number of items is small. I don't like makeRange much. Would you have a better name? smallRange? rangeOf?
Jul 10 2012
parent "Daniel Murphy" <yebblies nospamgmail.com> writes:
"Christophe Travert" <travert phare.normalesup.org> wrote in message 
news:jthp14$30em$1 digitalmars.com...
 "Daniel Murphy" , dans le message (digitalmars.D:171741), a écrit :
 "Christophe Travert" <travert phare.normalesup.org> wrote in message
 news:jthmu8$2s5b$1 digitalmars.com...
 "Daniel Murphy" , dans le message (digitalmars.D:171720), a écrit :
 Could it be extended to accept multiple values? (sort of like chain)
 eg.
 foreach(x; makeRange(23, 7, 1990)) // NO allocations!
 {
     ....
 }
 I would use this in a lot of places I currently jump through hoops to 
 get
 a
 static array without allocating.
That's a good idea. IMHO, the real solution would be to make an easy way to create static arrays, and slice them when you want a range.
It's not quite the same thing, static arrays are not ranges and once you slice them you no longer have a value type, and might be referring to stack allocated data. With... this thing, the length/progress is not encoded in the type (making it rangeable) but the data _is_ contained in the type, making it safe to pass around. The best of both worlds, in some situations.
OK, I see. This goes against the principle that ranges are small and easy to copy arround, but it can be useful when you know what you are doing, or when the number of items is small.
Yeah, it works where you'd pass a tuple of elements of the same type, but want to iterate over it.
 I don't like makeRange much. Would you have a better name? smallRange?
 rangeOf?
rangeit
Jul 10 2012
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 7/10/12 1:17 PM, Daniel Murphy wrote:
 "Christophe Travert"<travert phare.normalesup.org>  wrote in message
 news:jthmu8$2s5b$1 digitalmars.com...
 "Daniel Murphy" , dans le message (digitalmars.D:171720), a écrit :
 Could it be extended to accept multiple values? (sort of like chain)
 eg.
 foreach(x; makeRange(23, 7, 1990)) // NO allocations!
 {
      ....
 }
 I would use this in a lot of places I currently jump through hoops to get
 a
 static array without allocating.
That's a good idea. IMHO, the real solution would be to make an easy way to create static arrays, and slice them when you want a range.
It's not quite the same thing, static arrays are not ranges and once you slice them you no longer have a value type, and might be referring to stack allocated data. With... this thing, the length/progress is not encoded in the type (making it rangeable) but the data _is_ contained in the type, making it safe to pass around. The best of both worlds, in some situations.
That does seem good to have. What would be a better name than makeRange? Andrei
Jul 10 2012
parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Tuesday, July 10, 2012 13:58:50 Andrei Alexandrescu wrote:
 On 7/10/12 1:17 PM, Daniel Murphy wrote:
 "Christophe Travert"<travert phare.normalesup.org> wrote in message
 news:jthmu8$2s5b$1 digitalmars.com...
 
 "Daniel Murphy" , dans le message (digitalmars.D:171720), a écrit :
 Could it be extended to accept multiple values? (sort of like chain)
 eg.
 foreach(x; makeRange(23, 7, 1990)) // NO allocations!
 {
 
 ....
 
 }
 I would use this in a lot of places I currently jump through hoops to
 get
 a
 static array without allocating.
That's a good idea. IMHO, the real solution would be to make an easy way to create static arrays, and slice them when you want a range.
It's not quite the same thing, static arrays are not ranges and once you slice them you no longer have a value type, and might be referring to stack allocated data. With... this thing, the length/progress is not encoded in the type (making it rangeable) but the data _is_ contained in the type, making it safe to pass around. The best of both worlds, in some situations.
That does seem good to have. What would be a better name than makeRange?
I see no problem with makeRange. It seems like a sensible name to me. You're taking a sequence of elements and making a range out of them. - Jonathan M Davis
Jul 10 2012
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 7/10/12 2:08 PM, Jonathan M Davis wrote:
 That does seem good to have. What would be a better name than makeRange?
I see no problem with makeRange. It seems like a sensible name to me. You're taking a sequence of elements and making a range out of them.
I swear I'd just call it "range". Andrei
Jul 10 2012
next sibling parent "Simen Kjaeraas" <simen.kjaras gmail.com> writes:
On Tue, 10 Jul 2012 20:09:15 +0200, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:

 On 7/10/12 2:08 PM, Jonathan M Davis wrote:
 That does seem good to have. What would be a better name than  
 makeRange?
I see no problem with makeRange. It seems like a sensible name to me. You're taking a sequence of elements and making a range out of them.
I swear I'd just call it "range". Andrei
I'm with Andy on this. -- Simen
Jul 10 2012
prev sibling next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 07/10/2012 08:09 PM, Andrei Alexandrescu wrote:
 On 7/10/12 2:08 PM, Jonathan M Davis wrote:
 That does seem good to have. What would be a better name than makeRange?
I see no problem with makeRange. It seems like a sensible name to me. You're taking a sequence of elements and making a range out of them.
I swear I'd just call it "range". Andrei
This was my thinking as well.
Jul 10 2012
prev sibling next sibling parent "Daniel Murphy" <yebblies nospamgmail.com> writes:
"Andrei Alexandrescu" <SeeWebsiteForEmail erdani.org> wrote in message 
news:jthr4a$3f3$1 digitalmars.com...
 On 7/10/12 2:08 PM, Jonathan M Davis wrote:
 That does seem good to have. What would be a better name than makeRange?
I see no problem with makeRange. It seems like a sensible name to me. You're taking a sequence of elements and making a range out of them.
I swear I'd just call it "range". Andrei
tuple(1, 2, 3).rangeOf
Jul 10 2012
prev sibling parent "Daniel Murphy" <yebblies nospamgmail.com> writes:
"Andrei Alexandrescu" <SeeWebsiteForEmail erdani.org> wrote in message 
news:jthr4a$3f3$1 digitalmars.com...
 I swear I'd just call it "range".

 Andrei
Sure, why not. http://d.puremagic.com/issues/show_bug.cgi?id=8371
Jul 10 2012
prev sibling parent reply travert phare.normalesup.org (Christophe Travert) writes:
Andrei Alexandrescu , dans le message (digitalmars.D:171717), a écrit :
 On 7/10/12 11:11 AM, Christophe Travert wrote:
 If you do not want the heap allocation of the array, you can create a
 one-element range to feed to chain (maybe such a thing could be placed
 in phobos, next to takeOne).

 struct OneElementRange(E)
 {
    E elem;
    bool passed;
     property ref E front() { return elem; }
    void popFront() { passed = true; }
     property bool empty() { return passed; }
     property size_t length() { return 1-passed; }
    //...
 }
Yah, probably we should add something like this: auto singletonRange(E)(E value) { return repeat(value).takeExactly(1); }
It would be much better to use: auto singletonRange(E)(E value) { return repeat(value).takeOne; } as well as: auto emptyRange(E)(E value) { return repeat(value).takeNone; } to have the advantages of takeOne and takeNone over takeExactly.
 I don't think it would be considerably less efficient than a handwritten 
 specialization. But then I've been wrong before in assessing efficiency.
Error message displaying the type of singletonRange(E) will be weird, but that's far from being the first place where it will be. Simplicity and maintainance of phobos seems more important to me. At least until these algorithm get stable, meaning open bug reports on algorithm and range are solved, and new bugs appears rarely. Optimisers should have no trouble inlining calls to Repeat's methods...
Jul 10 2012
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 7/10/12 12:01 PM, Christophe Travert wrote:
 Andrei Alexandrescu , dans le message (digitalmars.D:171717), a écrit :
 auto singletonRange(E)(E value)
 {
       return repeat(value).takeExactly(1);
 }
It would be much better to use: auto singletonRange(E)(E value) { return repeat(value).takeOne; } as well as: auto emptyRange(E)(E value) { return repeat(value).takeNone; } to have the advantages of takeOne and takeNone over takeExactly.
Ah, such as them being random access. Cool! That also seems to answer Jonathan's quest about defining emptyRange. Just use takeNone(R.init). Andrei
Jul 10 2012
next sibling parent travert phare.normalesup.org (Christophe Travert) writes:
Andrei Alexandrescu , dans le message (digitalmars.D:171723), a écrit :
 auto emptyRange(E)(E value)
 {
    return repeat(value).takeNone;
 }
 That also seems to answer Jonathan's quest about defining emptyRange. 
 Just use takeNone(R.init).
err, that should be more like: auto singletonRange(E)() // with no parameters { return takeNone!type_of(repeat(E.init))(); } An emptyRange compatible with singletonRange should be called singletonRange and take no parameter, so that emptyRange name could be reserved to a real statically empty range (which is pretty easy to implement). -- Christophe
Jul 10 2012
prev sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Tuesday, July 10, 2012 12:22:30 Andrei Alexandrescu wrote:
 On 7/10/12 12:01 PM, Christophe Travert wrote:
 Andrei Alexandrescu , dans le message (digitalmars.D:171717), a écrit :
 auto singletonRange(E)(E value)
 {
 
 return repeat(value).takeExactly(1);
 
 }
It would be much better to use: auto singletonRange(E)(E value) { return repeat(value).takeOne; } as well as: auto emptyRange(E)(E value) { return repeat(value).takeNone; } to have the advantages of takeOne and takeNone over takeExactly.
Ah, such as them being random access. Cool! That also seems to answer Jonathan's quest about defining emptyRange. Just use takeNone(R.init).
Actually, it doesn't, because find needs the ability to get an empty range of the exact same type as the original. It's a nice idea for cases where the resultant range doesn't matter though. - Jonathan M Davis
Jul 10 2012
prev sibling parent reply Jacob Carlborg <doob me.com> writes:
On 2012-07-10 17:11, Christophe Travert wrote:

 What is wrong with foo.chain(["bar"])?
I think it conceptually wrong for what I want to do. I don't know if I misunderstood ranges completely but I'm seeing them as an abstraction over a collection. With most mutable collection you can add/append an element.
 you might try this (untested)


 string function(Parameter) stringify = (x)
 {
   return (x.isConst? "const("~x.type~")": x.type)
      ~ (x.name.any?" "~translateIdentifier(x.name):"");
 }

 auto params = parameters
    .map!stringify()
    .chain(variadic? []: ["..."])
    .joiner(", ");

 context ~= params;

 I am not sure this will be more efficient. joiner may be slowed down by
 the fact that it is called with a chain result, which is slower on
 front. But at leat you save yourself the heap-allocation of the params
 array*.

 I would use:
 context ~= parameters.map!stringify().joiner(",  ");
 if (variadic) context ~= ", ...";

 To make the best implementation would require to know how the String
 context works.

 *Note that here, stringify is not lazy, and thus allocates. It
 could be a chain or a joiner, but I'm not sure the result would really
 be more efficient.
String is a wrapper around str.array.Appender. -- /Jacob Carlborg
Jul 10 2012
next sibling parent travert phare.normalesup.org (Christophe Travert) writes:
Jacob Carlborg , dans le message (digitalmars.D:171725), a écrit :
 On 2012-07-10 17:11, Christophe Travert wrote:
 
 What is wrong with foo.chain(["bar"])?
I think it conceptually wrong for what I want to do. I don't know if I misunderstood ranges completely but I'm seeing them as an abstraction over a collection. With most mutable collection you can add/append an element.
That may be the source of your problem. ranges are not collections. They do not own data. They just show data. You can't make them grow. You can only consume what you have already read.
Jul 10 2012
prev sibling parent reply travert phare.normalesup.org (Christophe Travert) writes:
Jacob Carlborg , dans le message (digitalmars.D:171725), a écrit :
 To make the best implementation would require to know how the String
 context works.
String is a wrapper around str.array.Appender.
Then, if the purpose is to make the code efficient, I would use the loop and append everything to the result without creating the params array, and even without creating the string p. Appender is made to append everything directly to it efficiently.
Jul 10 2012
parent Jacob Carlborg <doob me.com> writes:
On 2012-07-10 22:13, Christophe Travert wrote:

 Then, if the purpose is to make the code efficient, I would use the loop
 and append everything to the result without creating the params array,
 and even without creating the string p. Appender is made to append
 everything directly to it efficiently.
Yeah, I've been thinking about doing that more. -- /Jacob Carlborg
Jul 10 2012
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 7/10/12 9:56 AM, Jacob Carlborg wrote:
 On 2012-07-10 15:28, Andrei Alexandrescu wrote:

 We can arrange things in the library that a custom message is issued, or
 in the compiler to do it once for all. At any rate whenever there's an
 error pointing somewhere in the library's code that's an insufficient
 template constraint that should be fixed.
I mean, is it possible to have the original code work? auto bar = foo.chain("bar"); Or perhaps more appropriate: auto bar = foo.append("bar");
It would be possible to chain a single element to the end of a range. One related thing to do is to define singletonRange(x) that returns a range with exactly one element, namely x.
 I understand. So you need to use array() to convert the lazy map result
 into an eager array. I disagree this is unintuitive, if it were then
 very little of D would make sense are lazy, non-array ranges are
 everywhere.
Tell me what is the point of std.algorithm and ranges if I have to convert every single result of an algorithm to an array before I can use it with an other algorithm? I thought the whole idea was to avoid allocations between different usages of algorithms.
Ranges and std.algorithm obey simple, mathematical realities deriving from algorithm and storage topology constraints. For example sort works in place so it generally can't work on mapped stuff because there's no place to put the sorted contents. Also sort needs a random-access range to work with so it can't work e.g. with the result of filter, which necessarily yields a non-random-access range. And so on. Now I understand if you come from a place where there's no concern over hidden allocations and extra work for the benefit of convenience, you may find std.algorithm less easy to work with. But drawing the conclusion that std.algorithm is badly designed or gratuitously difficult to use would be a mistake. I opine I can recognize a good vs. bad design even when it's mine, and in my opinion std.algorithm is a good design and that most of your opposing impressions derive from a misunderstanding of its charter. Andrei
Jul 10 2012
parent reply Jacob Carlborg <doob me.com> writes:
On 2012-07-10 17:30, Andrei Alexandrescu wrote:

 It would be possible to chain a single element to the end of a range.
 One related thing to do is to define singletonRange(x) that returns a
 range with exactly one element, namely x.
Ok, I saw that suggestion in another post.
 Ranges and std.algorithm obey simple, mathematical realities deriving
 from algorithm and storage topology constraints. For example sort works
 in place so it generally can't work on mapped stuff because there's no
 place to put the sorted contents. Also sort needs a random-access range
 to work with so it can't work e.g. with the result of filter, which
 necessarily yields a non-random-access range. And so on.
Can't "map" and "filter" return a random-access range if that's what they receive?
 Now I understand if you come from a place where there's no concern over
 hidden allocations and extra work for the benefit of convenience, you
 may find std.algorithm less easy to work with. But drawing the
 conclusion that std.algorithm is badly designed or gratuitously
 difficult to use would be a mistake. I opine I can recognize a good vs.
 bad design even when it's mine, and in my opinion std.algorithm is a
 good design and that most of your opposing impressions derive from a
 misunderstanding of its charter.
I don't think I've struggled as much with any other API I've used. In many cases I had to resort to foreach-loops because that was more convenient than using std.algorithm. -- /Jacob Carlborg
Jul 10 2012
next sibling parent reply "Daniel Murphy" <yebblies nospamgmail.com> writes:
"Jacob Carlborg" <doob me.com> wrote in message 
news:jthlpf$2pnb$1 digitalmars.com...
 Can't "map" and "filter" return a random-access range if that's what they 
 receive?
map can, and does. filter cannot, because it doesn't know which element is number 4 until it knows if element 3 is included or not.
Jul 10 2012
parent reply Jacob Carlborg <doob me.com> writes:
On 2012-07-10 18:42, Daniel Murphy wrote:
 "Jacob Carlborg" <doob me.com> wrote in message
 news:jthlpf$2pnb$1 digitalmars.com...
 Can't "map" and "filter" return a random-access range if that's what they
 receive?
map can, and does.
It doesn't seem to: auto a = [3, 4].map!(x => x); auto b = a.sort; Result in one of the original errors I started this thread with. -- /Jacob Carlborg
Jul 10 2012
next sibling parent travert phare.normalesup.org (Christophe Travert) writes:
Jacob Carlborg , dans le message (digitalmars.D:171739), a écrit :
 On 2012-07-10 18:42, Daniel Murphy wrote:
 "Jacob Carlborg" <doob me.com> wrote in message
 news:jthlpf$2pnb$1 digitalmars.com...
 Can't "map" and "filter" return a random-access range if that's what they
 receive?
map can, and does.
It doesn't seem to: auto a = [3, 4].map!(x => x); auto b = a.sort; Result in one of the original errors I started this thread with.
here, map is random-access. But random access is not enough to call sort: you need to have assignable (well, swapable) elements in the range, if you want to be able to sort it. values accessed via a map are not always assignable, since they are the result of a function. It seems the map resulting from (x => x) is not assignable. This is debatable, but since (x => x) is just a stupid function to test. Otherwise, you could try the folowing: auto a = [3, 4].map!(ref int (ref int x) { return x; })(); a.sort;
Jul 10 2012
prev sibling parent reply "Daniel Murphy" <yebblies nospamgmail.com> writes:
"Jacob Carlborg" <doob me.com> wrote in message 
news:jthnlo$2tjg$1 digitalmars.com...
 On 2012-07-10 18:42, Daniel Murphy wrote:
 "Jacob Carlborg" <doob me.com> wrote in message
 news:jthlpf$2pnb$1 digitalmars.com...
 Can't "map" and "filter" return a random-access range if that's what 
 they
 receive?
map can, and does.
It doesn't seem to: auto a = [3, 4].map!(x => x); auto b = a.sort; Result in one of the original errors I started this thread with. -- /Jacob Carlborg
writeln([1, 2, 3].map!"a"()[2]); Sort is in place, and therefore requires more than random access, you need to be able to modify the data you're operating on. Something like [3, 4].map!func().selectionSort() could work lazily without needing to modify the original range, but urrgh.
Jul 10 2012
parent Jacob Carlborg <doob me.com> writes:
On 2012-07-10 19:23, Daniel Murphy wrote:

 writeln([1, 2, 3].map!"a"()[2]);

 Sort is in place, and therefore requires more than random access, you need
 to be able to modify the data you're operating on.

 Something like [3, 4].map!func().selectionSort() could work lazily without
 needing to modify the original range, but urrgh.
Ok, I think I get it now. -- /Jacob Carlborg
Jul 10 2012
prev sibling next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 07/10/2012 06:38 PM, Jacob Carlborg wrote:
 On 2012-07-10 17:30, Andrei Alexandrescu wrote:

 It would be possible to chain a single element to the end of a range.
 One related thing to do is to define singletonRange(x) that returns a
 range with exactly one element, namely x.
Ok, I saw that suggestion in another post.
 Ranges and std.algorithm obey simple, mathematical realities deriving
 from algorithm and storage topology constraints. For example sort works
 in place so it generally can't work on mapped stuff because there's no
 place to put the sorted contents. Also sort needs a random-access range
 to work with so it can't work e.g. with the result of filter, which
 necessarily yields a non-random-access range. And so on.
Can't "map" and "filter" return a random-access range if that's what they receive?
Map can do that and does do that. How would it work for filter?
Jul 10 2012
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 7/10/12 12:38 PM, Jacob Carlborg wrote:
 Can't "map" and "filter" return a random-access range if that's what
 they receive?
(replied to by others)
 Now I understand if you come from a place where there's no concern over
 hidden allocations and extra work for the benefit of convenience, you
 may find std.algorithm less easy to work with. But drawing the
 conclusion that std.algorithm is badly designed or gratuitously
 difficult to use would be a mistake. I opine I can recognize a good vs.
 bad design even when it's mine, and in my opinion std.algorithm is a
 good design and that most of your opposing impressions derive from a
 misunderstanding of its charter.
I don't think I've struggled as much with any other API I've used. In many cases I had to resort to foreach-loops because that was more convenient than using std.algorithm.
That's fine. I don't see std.algorithm as a competitor against simple loops, but instead of work that would be very verbose and difficult to do with loops. I mean I clearly recall at a point I wanted to define a forAll algorithm, but then I was like, "people can use foreach for that". Andrei
Jul 10 2012
prev sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Jul 10, 2012 at 09:28:51AM -0400, Andrei Alexandrescu wrote:
 On 7/10/12 2:50 AM, Jacob Carlborg wrote:
On 2012-07-09 22:16, Andrei Alexandrescu wrote:

So foo is a range of strings, because each element of it is a
string.  Then you want to chain a range of strings with a string,
which is a range of dchar. That doesn't work, and I agree the error
message should be more informative.
Is that by design or something that can be fixed?
We can arrange things in the library that a custom message is issued, or in the compiler to do it once for all.
Please don't do it in the compiler. Custom messages should be in the library. Tying the compiler to phobos is a bad idea; druntime should be the only dependency.
 At any rate whenever there's an error pointing somewhere in the
 library's code that's an insufficient template constraint that should
 be fixed.
[...] Yes. T -- Having a smoking section in a restaurant is like having a peeing section in a swimming pool. -- Edward Burr
Jul 10 2012
next sibling parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 10-Jul-12 17:59, H. S. Teoh wrote:
 On Tue, Jul 10, 2012 at 09:28:51AM -0400, Andrei Alexandrescu wrote:
 On 7/10/12 2:50 AM, Jacob Carlborg wrote:
 On 2012-07-09 22:16, Andrei Alexandrescu wrote:

 So foo is a range of strings, because each element of it is a
 string.  Then you want to chain a range of strings with a string,
 which is a range of dchar. That doesn't work, and I agree the error
 message should be more informative.
Is that by design or something that can be fixed?
We can arrange things in the library that a custom message is issued, or in the compiler to do it once for all.
Please don't do it in the compiler. Custom messages should be in the library. Tying the compiler to phobos is a bad idea; druntime should be the only dependency.
Time and again I think of T func(Blah)(Blah param) if(isMagic!Blah, Blah.stringof~" is not magic") //second param is an error hint { } The idea is that when all functions from overload set fail to meet constraints the error on "doesn't match template parameters" should contain this extra HINTs on what's wrong. HINT in general must be short, and clear. No need to do elobarate a statements. -- Dmitry Olshansky
Jul 10 2012
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 7/10/12 9:59 AM, H. S. Teoh wrote:
 On Tue, Jul 10, 2012 at 09:28:51AM -0400, Andrei Alexandrescu wrote:
 On 7/10/12 2:50 AM, Jacob Carlborg wrote:
 On 2012-07-09 22:16, Andrei Alexandrescu wrote:

 So foo is a range of strings, because each element of it is a
 string.  Then you want to chain a range of strings with a string,
 which is a range of dchar. That doesn't work, and I agree the error
 message should be more informative.
Is that by design or something that can be fixed?
We can arrange things in the library that a custom message is issued, or in the compiler to do it once for all.
Please don't do it in the compiler. Custom messages should be in the library. Tying the compiler to phobos is a bad idea; druntime should be the only dependency.
The idea there being that the compiler could give good details about what part of a complex constraint has failed. Andrei
Jul 10 2012
parent reply Don Clugston <dac nospam.com> writes:
On 10/07/12 16:59, Andrei Alexandrescu wrote:
 On 7/10/12 9:59 AM, H. S. Teoh wrote:
 On Tue, Jul 10, 2012 at 09:28:51AM -0400, Andrei Alexandrescu wrote:
 On 7/10/12 2:50 AM, Jacob Carlborg wrote:
 On 2012-07-09 22:16, Andrei Alexandrescu wrote:

 So foo is a range of strings, because each element of it is a
 string.  Then you want to chain a range of strings with a string,
 which is a range of dchar. That doesn't work, and I agree the error
 message should be more informative.
Is that by design or something that can be fixed?
We can arrange things in the library that a custom message is issued, or in the compiler to do it once for all.
Please don't do it in the compiler. Custom messages should be in the library. Tying the compiler to phobos is a bad idea; druntime should be the only dependency.
The idea there being that the compiler could give good details about what part of a complex constraint has failed.
However the compiler doesn't know which constraint was supposed to pass. If it is lucky enough to only have one template, it can do it, but if it has: template1 if (A && B) template2 if (C && D) template3 if ( (E || F) && G) should it print: foo.d(99): Error: no matching template foo.d(10): constraint failed: A foo.d(28): constraint failed: D foo.d(57): constraint failed: (E || F) ? Could be a very long list, if there are many templates. Determining the minimal list of constraints seems like a nice application for BDDs...
Jul 16 2012
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 07/16/2012 05:22 PM, Don Clugston wrote:
 On 10/07/12 16:59, Andrei Alexandrescu wrote:
 On 7/10/12 9:59 AM, H. S. Teoh wrote:
 On Tue, Jul 10, 2012 at 09:28:51AM -0400, Andrei Alexandrescu wrote:
 On 7/10/12 2:50 AM, Jacob Carlborg wrote:
 On 2012-07-09 22:16, Andrei Alexandrescu wrote:

 So foo is a range of strings, because each element of it is a
 string. Then you want to chain a range of strings with a string,
 which is a range of dchar. That doesn't work, and I agree the error
 message should be more informative.
Is that by design or something that can be fixed?
We can arrange things in the library that a custom message is issued, or in the compiler to do it once for all.
Please don't do it in the compiler. Custom messages should be in the library. Tying the compiler to phobos is a bad idea; druntime should be the only dependency.
The idea there being that the compiler could give good details about what part of a complex constraint has failed.
However the compiler doesn't know which constraint was supposed to pass. If it is lucky enough to only have one template, it can do it, but if it has: template1 if (A && B) template2 if (C && D) template3 if ( (E || F) && G) should it print: foo.d(99): Error: no matching template foo.d(10): constraint failed: A foo.d(28): constraint failed: D foo.d(57): constraint failed: (E || F) ? Could be a very long list, if there are many templates. Determining the minimal list of constraints seems like a nice application for BDDs...
Well, are template constraints likely to contain a lot of redundant information?
Jul 16 2012
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday, July 16, 2012 22:53:36 Timon Gehr wrote:
 On 07/16/2012 05:22 PM, Don Clugston wrote:
 On 10/07/12 16:59, Andrei Alexandrescu wrote:
 On 7/10/12 9:59 AM, H. S. Teoh wrote:
 On Tue, Jul 10, 2012 at 09:28:51AM -0400, Andrei Alexandrescu wrote:
 On 7/10/12 2:50 AM, Jacob Carlborg wrote:
 On 2012-07-09 22:16, Andrei Alexandrescu wrote:
 So foo is a range of strings, because each element of it is a
 string. Then you want to chain a range of strings with a string,
 which is a range of dchar. That doesn't work, and I agree the error
 message should be more informative.
Is that by design or something that can be fixed?
We can arrange things in the library that a custom message is issued, or in the compiler to do it once for all.
Please don't do it in the compiler. Custom messages should be in the library. Tying the compiler to phobos is a bad idea; druntime should be the only dependency.
The idea there being that the compiler could give good details about what part of a complex constraint has failed.
However the compiler doesn't know which constraint was supposed to pass. If it is lucky enough to only have one template, it can do it, but if it has: template1 if (A && B) template2 if (C && D) template3 if ( (E || F) && G) should it print: foo.d(99): Error: no matching template foo.d(10): constraint failed: A foo.d(28): constraint failed: D foo.d(57): constraint failed: (E || F) ? Could be a very long list, if there are many templates. Determining the minimal list of constraints seems like a nice application for BDDs...
Well, are template constraints likely to contain a lot of redundant information?
They're likely to contain a lot of stuff negation of other template constraints. For instance, auto func(R)(R range) if(isForwardRange!R && !isBidirectionalRange!R) {} auto func(R)(R range) if(isBidirectionalRange!R) {} If you have a function with very many overloads, it can be very easy to end up with a bunch of different template constraints which are all slightly different. std.algorithm.find is a prime example of this. But as much as it may be a bit overwhelming to print every failed constraint, without doing that, you _have_ to go to the source code to see what they were, which isn't all that great (especially if it's not in a library that you wrote and don't normally look at the source of - e.g. Phobos). On the other hand, a failed instantiation of std.conv.to would print out reams of failed constraints... Getting the compiler to print out the constraints come out to if combined could be very useful, but in some ways, it would be worse, since it would generally result in one big constraint with a bunch of ||s between them - particularly since it can't understand how the various templates involved work (e.g. isForwardRange vs isBidirectionalRange). I've considered taking up the practice of putting all template function overloads inside of a single template which has a constraint for them all (with each individual function still having its own of course). The programmer would likely do a better job at simplifying it than the compiler, but often you can't do that, especially when different overloads require drastically different stuff (e.g. the constraints on needle often depend on the constraints on haystack for find). So, in a lot of cases, you'd just end up with a really nasty looking and hard to understand template constraint. If it weren't for the case of std.conv, I'd argue for just displaying all of the failed constraints, but I don't know. - Jonathan M Davis
Jul 16 2012
parent reply travert phare.normalesup.org (Christophe Travert) writes:
Jonathan M Davis , dans le message (digitalmars.D:172564), a écrit :
 They're likely to contain a lot of stuff negation of other template 
 constraints. For instance,
 
 auto func(R)(R range)
     if(isForwardRange!R && !isBidirectionalRange!R)
 {}
 
 auto func(R)(R range)
     if(isBidirectionalRange!R)
 {}
 
 If you have a function with very many overloads, it can be very easy to end up 
 with a bunch of different template constraints which are all slightly
different. 
 std.algorithm.find is a prime example of this.
 
 But as much as it may be a bit overwhelming to print every failed constraint, 
 without doing that, you _have_ to go to the source code to see what they were, 
 which isn't all that great (especially if it's not in a library that you wrote 
 and don't normally look at the source of - e.g. Phobos).
 
 On the other hand, a failed instantiation of std.conv.to would print out reams 
 of failed constraints...
The compiler could stop displaying at about 10 failed constrains and claim there are more. It would be best if it could figure out what are the 10 most interesting constrains, but that may not be easy! Then it's up to the programmer to use template constrains, static if and eventually pragma, to allow the compiler to display pleasant error messages. The langage could help you by allowing you to make hiearchized template constrains, but static if is a fine solution most of the time.
Jul 17 2012
parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Tuesday, July 17, 2012 11:47:07 Christophe Travert wrote:
 The compiler could stop displaying at about 10 failed constrains and
 claim there are more. It would be best if it could figure out what are
 the 10 most interesting constrains, but that may not be easy!
That seems like a good idea. - Jonathan M Davis
Jul 17 2012
prev sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday, July 09, 2012 16:16:42 Andrei Alexandrescu wrote:
 Another example:
 
 auto str = ["foo", "bar"].map!(x => x);
 auto f = str.sort();
 
 Results in:
 
 http://pastebin.com/BeePWQk9
The first error message is at clear as it goes: Error: r[i2] is not an lvalue
It's only clear if you go look at sort's implementation, and that failure isn't even in sort itself! It's in its helper function, swapAt. Either sort's template constraint should fail when it's given a range that won't work with it, or it needs a static assertion which tells the programmer exactly what's wrong. The fact that r[i2] isn't an lvalue means nothing without actually digging into the code, which the average programmer should not have to do. - Jonathan M Davis
Jul 10 2012
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 7/10/12 3:48 AM, Jonathan M Davis wrote:
 On Monday, July 09, 2012 16:16:42 Andrei Alexandrescu wrote:
 Another example:

 auto str = ["foo", "bar"].map!(x =>  x);
 auto f = str.sort();

 Results in:

 http://pastebin.com/BeePWQk9
The first error message is at clear as it goes: Error: r[i2] is not an lvalue
It's only clear if you go look at sort's implementation, and that failure isn't even in sort itself! It's in its helper function, swapAt. Either sort's template constraint should fail when it's given a range that won't work with it, or it needs a static assertion which tells the programmer exactly what's wrong. The fact that r[i2] isn't an lvalue means nothing without actually digging into the code, which the average programmer should not have to do.
Agreed, thanks for the bug reports. Andrei
Jul 10 2012
prev sibling next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Monday, July 09, 2012 22:09:54 Jacob Carlborg wrote:
 Almost every time I'm trying to use std.algorithm I run into some kind
 of error, for what seems to be fairly trivial and what one would expect
 to work. It feels like I'm constantly fighting with std.algorithm. For
 example:
 
 import std.algorithm;
 import std.range;
 
 struct Foo {}
 
 auto f = Foo();
 auto foos = [f];
 auto foo = foos.map!(x => "foo");
 auto bar = foo.chain("bar");
 
 This simple example result in the follow error:
 
 http://pastebin.com/E4LV2UBE
 
 Another example:
 
 auto str = ["foo", "bar"].map!(x => x);
 auto f = str.sort();
 
 Results in:
 
 http://pastebin.com/BeePWQk9
 
 I'm using DMD 2.059.
From the looks of it (without digging into what's really going on), in both 
cases, the problem seems to be that a template constraint is insufficiently precise, and so it's attempting to instantiate a template when that instantiation should fail. If a template constraint is written correctly, it should be impossible for the template constraint to succeed and the template instantiation fail. In general, I think that std.range and std.algorithm need better unit tests (ideally with every combination of range types that a particular function is supposed to work with being tested for that function). There are definitely cases where certain range types are supposed to work and don't (reference type ranges being a prime example). I've started on that but haven't gotten all that far yet. But with better testing, it should be much harder for a bad template constraint to be missed. - Jonathan M Davis
Jul 09 2012
prev sibling next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Jacob Carlborg:

 import std.algorithm;
 import std.range;

 struct Foo {}

 auto f = Foo();
 auto foos = [f];
 auto foo = foos.map!(x => "foo");
 auto bar = foo.chain("bar");
I suggest to always compile with "-wi -property". chain() takes two iterables. This means both arguments need to yield the same type. But in your code foo is an iterable of strings, and you try to chain it an iterable of chars. In Python that works just because there are no chars, only single-char strings. It works if you turn the second argument of chain in an iterable of strings: import std.stdio, std.algorithm, std.range; void main() { import std.algorithm; import std.range; struct Foo {} auto f = Foo(); auto foos = [f]; auto foo = foos.map!(x => "foo")(); auto bar = foo.chain(["bar"]); writeln(bar); }
 This simple example result in the follow error:

 http://pastebin.com/E4LV2UBE

 Another example:

 auto str = ["foo", "bar"].map!(x => x);
 auto f = str.sort();
Map returns a lazy iterable. Generally you need an eager random-access iterable to sort (but it seems there are some exceptions like when you sort a zip...). Bye, bearophile
Jul 09 2012
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 07/09/2012 10:46 PM, bearophile wrote:
 Jacob Carlborg:

 import std.algorithm;
 import std.range;

 struct Foo {}

 auto f = Foo();
 auto foos = [f];
 auto foo = foos.map!(x => "foo");
 auto bar = foo.chain("bar");
I suggest to always compile with "-wi -property".
Both -property and -w/-wi are broken and their only merit so far is to break my builds for no reason. -wi spits out about 4000 lines of false (duplicate) warnings when run against my code base.
 This simple example result in the follow error:

 http://pastebin.com/E4LV2UBE

 Another example:

 auto str = ["foo", "bar"].map!(x => x);
 auto f = str.sort();
Map returns a lazy iterable. Generally you need an eager random-access iterable to sort (but it seems there are some exceptions like when you sort a zip...).
Actually you need a random-access range with assignable elements. Map would need to be provided with an inverse mapping to support that. zip has assignable elements when the source ranges do.
Jul 09 2012
next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
On Monday, 9 July 2012 at 21:00:40 UTC, Timon Gehr wrote:
 On 07/09/2012 10:46 PM, bearophile wrote:
 Jacob Carlborg:

 import std.algorithm;
 import std.range;

 struct Foo {}

 auto f = Foo();
 auto foos = [f];
 auto foo = foos.map!(x => "foo");
 auto bar = foo.chain("bar");
I suggest to always compile with "-wi -property".
Both -property and -w/-wi are broken and their only merit so far is to break my builds for no reason.
So far I have not seen one case where -property gives a wrong message. Please show me one. It's stuff for bugzilla.
 -wi spits out about 4000 lines of false (duplicate) warnings 
 when run against my code base.
Please reduce those, maybe there is some false warning that I have not yet put in Bugzilla. In general -wi spits good warnings, with few exceptions.
 zip has assignable elements when the source ranges do.
It's shown in the Phobos docs too, but it's a little unexpected. See also: http://d.puremagic.com/issues/show_bug.cgi?id=8341 Bye, bearophile
Jul 09 2012
prev sibling next sibling parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Monday, July 09, 2012 23:00:39 Timon Gehr wrote:
 On 07/09/2012 10:46 PM, bearophile wrote:
 Jacob Carlborg:
 import std.algorithm;
 import std.range;
 
 struct Foo {}
 
 auto f = Foo();
 auto foos = [f];
 auto foo = foos.map!(x => "foo");
 auto bar = foo.chain("bar");
I suggest to always compile with "-wi -property".
Both -property and -w/-wi are broken and their only merit so far is to break my builds for no reason. -wi spits out about 4000 lines of false (duplicate) warnings when run against my code base.
I'd actually argue the opposite. I think that they should be the normal behavior, and if you're getting a ton of warnings, I'd argue that you have a ton of problems that need fixing. dmd is generally good about not having useless warnings. Now, with the current version of github, it unfortunately seems to spit out a bunch of duplicate messages for the same error/warning with templates in a number of cases, and _that_ should be fixed, but the warnings themselves are generally solid and indicators of a real problem. And as I've expressed in the past, I think that -property is very much doing the right thing and that not strictly enforcing properties is horrible, but obivously we're in disagreement on that. - Jonathan M Davis
Jul 09 2012
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 07/10/2012 12:53 AM, Jonathan M Davis wrote:
 On Monday, July 09, 2012 23:00:39 Timon Gehr wrote:
 On 07/09/2012 10:46 PM, bearophile wrote:
 Jacob Carlborg:
 import std.algorithm;
 import std.range;

 struct Foo {}

 auto f = Foo();
 auto foos = [f];
 auto foo = foos.map!(x =>  "foo");
 auto bar = foo.chain("bar");
I suggest to always compile with "-wi -property".
Both -property and -w/-wi are broken and their only merit so far is to break my builds for no reason. -wi spits out about 4000 lines of false (duplicate) warnings when run against my code base.
I'd actually argue the opposite. I think that they should be the normal behavior, and if you're getting a ton of warnings, I'd argue that you have a ton of problems that need fixing.
Nonsense. I explicitly expressed that the warnings I get are bare of value.
 dmd is generally good about not having
 useless warnings.
case 0,1: // warning: switch fallthrough (nonsense) case 2,3: This is the only kind of warning I get (clearly a bug, and it is reported). After that, the compiler spits out ~4000 lines of completely unrelated internal AST from a different module.
 Now, with the current version of github, it unfortunately
 seems to spit out a bunch of duplicate messages for the same error/warning
 with templates in a number of cases, and _that_ should be fixed, but the
 warnings themselves are generally solid and indicators of a real problem.

 And as I've expressed in the past, I think that -property is very much doing
 the right thing and that not strictly enforcing properties is horrible,
Language design shouldn't be based on statements like "I think it is horrible". There is nothing objective in it.
 but obivously we're in disagreement on that.
What we disagree on is what is called a property and what is called a function call. I am ok with disallowing function calls of the form function = argument.
Jul 09 2012
next sibling parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Tuesday, July 10, 2012 01:20:21 Timon Gehr wrote:
 Now, with the current version of github, it unfortunately
 seems to spit out a bunch of duplicate messages for the same error/warning
 with templates in a number of cases, and _that_ should be fixed, but the
 warnings themselves are generally solid and indicators of a real problem.
 
 And as I've expressed in the past, I think that -property is very much
 doing the right thing and that not strictly enforcing properties is
 horrible,
Language design shouldn't be based on statements like "I think it is horrible". There is nothing objective in it.
Without -property, it's lax. The rules aren't enforced. It allows you to use a function as if it were a property when it's not. Language rules should be strictly enforced not be left up to the programmer whether they want to bother following them or not. That just leads to confusion and bugs. If the API states that it's property, so it should be used as a property. If the API says that it should be used as a function, then it should be used as a function. You wouldn't use () on a variable would you (aside from defining opCall)? I should think not, and I don't think that () should be left out on a function any more than they should be used on a variable. It's sloppy and confusing. Regardless, TDPL calls for strict property enforcement, so that's where we're headed. - Jonathan M Davis
Jul 09 2012
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 07/10/2012 01:34 AM, Jonathan M Davis wrote:
 On Tuesday, July 10, 2012 01:20:21 Timon Gehr wrote:
 Now, with the current version of github, it unfortunately
 seems to spit out a bunch of duplicate messages for the same error/warning
 with templates in a number of cases, and _that_ should be fixed, but the
 warnings themselves are generally solid and indicators of a real problem.

 And as I've expressed in the past, I think that -property is very much
 doing the right thing and that not strictly enforcing properties is
 horrible,
Language design shouldn't be based on statements like "I think it is horrible". There is nothing objective in it.
Without -property, it's lax. The rules aren't enforced.
Yes they are. It is just another set of rules.
 It allows you to use a function as if it were a property when it's not.
No, it allows you to call a function by calling it's name. Walter presumably got this from Eiffel, where it is called 'uniform access principle'.
 Language rules should be
 strictly enforced not be left up to the programmer whether they want to bother
 following them or not.  That just leads to confusion and bugs.
That is the realm of unsafe casts. We are just discussing syntax here. Less brackets are better, because it is easier to match them. Fact.
 If the API
 states that it's  property, so it should be used as a property. If the API
 says that it should be used as a function, then it should be used as a
 function.
function; is a perfectly good function call. It is used as a function. It is none of the API's business to claim that it must be called like function(), just because that brings in good memories of C. There are enough languages that got rid of the obligatory '()'.
 You wouldn't use () on a variable would you (aside from defining
 opCall)?
delegates and function pointers come to mind. But that is besides the point.
 I should think not, and I don't think that () should be left out on a
 function any more than they should be used on a variable. It's sloppy and
 confusing.
We are going to disagree on that. Note that '()' can always be included as a visual clue if it makes sense. There are however cases where it does not.
 Regardless, TDPL calls for strict property enforcement, so that's where we're
 headed.
I have heard that rumour, but TDPL wisely specifies the behaviour of the property attribute as follows: 'In particular "property" is recognized by the the compiler and signals the fact that the function bearing such an attribute must be called without the trailing ().' That is exactly the behaviour I described. Note that this sentence includes the notion of _calling a function_ without the trailing () and it even seems to express that the trailing () is usually optional. So TDPL actually describes a subset of what I have in mind. (it seems to leave out the function = argument case completely.) We should therefore change where we are headed.
Jul 09 2012
parent reply "Jesse Phillips" <Jessekphillips+D gmail.com> writes:
On Tuesday, 10 July 2012 at 00:17:12 UTC, Timon Gehr wrote:
 I have heard that rumour, but TDPL wisely specifies the 
 behaviour of
 the  property attribute as follows:

 'In particular "property" is recognized by the the compiler
 and signals the fact that the function bearing such an 
 attribute must be called without the trailing ().'

 That is exactly the behaviour I described.

 Note that this sentence includes the notion of _calling a 
 function_
 without the trailing () and it even seems to express that the 
 trailing
 () is usually optional.
No it doesn't. It does have emphasis with 'must' and this likely comes from D having such a long history of the optional (), but that does not make this statement include such a notion.
 So TDPL actually describes a subset of what I have in mind. (it 
 seems
 to leave out the function = argument case completely.) We should
 therefore change where we are headed.
The -property is an implementation of what is to come. I was never greatly for property but since we have it it should be fully enforced, otherwise we may as well just drop it.
Jul 10 2012
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 07/10/2012 09:36 PM, Jesse Phillips wrote:
 On Tuesday, 10 July 2012 at 00:17:12 UTC, Timon Gehr wrote:
 I have heard that rumour, but TDPL wisely specifies the behaviour of
 the  property attribute as follows:

 'In particular "property" is recognized by the the compiler
 and signals the fact that the function bearing such an attribute must
 be called without the trailing ().'

 That is exactly the behaviour I described.

 Note that this sentence includes the notion of _calling a function_
 without the trailing () and it even seems to express that the trailing
 () is usually optional.
No it doesn't. It does have emphasis with 'must' and this likely comes from D having such a long history of the optional (), but that does not make this statement include such a notion.
I'm sure a lawyer could make a good case out of it. Anyway, TDPL clearly does not document the broken -property behaviour.
 So TDPL actually describes a subset of what I have in mind. (it seems
 to leave out the function = argument case completely.) We should
 therefore change where we are headed.
The -property is an implementation of what is to come. I was never greatly for property but since we have it it should be fully enforced, otherwise we may as well just drop it.
I think you may be misunderstanding what property is about. Given: property int delegate() foo(){ ... } property int bar(){ ... } int baz(){ ... } foo(); // calls the delegate. bar(); // illegal baz; // ok, call baz dmd -property gets every single one of these wrong. -property does _not_ enforce property semantics. It only adds a silly rule that was never part of the property design. I am astonished that it made it into the compiler.
Jul 10 2012
next sibling parent reply "Tobias Pankrath" <tobias pankrath.net> writes:
 Given:

  property int delegate() foo(){ ... }
  property int bar(){ ... }
 int baz(){ ... }

 foo(); // calls the delegate.
 bar(); // illegal
 baz;   // ok, call baz

 dmd -property gets every single one of these wrong. -property 
 does _not_
 enforce  property semantics. It only adds a silly rule that was 
 never
 part of the  property design. I am astonished that it made it 
 into the
 compiler.
+1
Jul 10 2012
parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 11-Jul-12 00:07, Tobias Pankrath wrote:
 Given:

  property int delegate() foo(){ ... }
  property int bar(){ ... }
 int baz(){ ... }

 foo(); // calls the delegate.
 bar(); // illegal
 baz;   // ok, call baz

 dmd -property gets every single one of these wrong. -property does _not_
 enforce  property semantics. It only adds a silly rule that was never
 part of the  property design. I am astonished that it made it into the
 compiler.
+1
Same here. Still no idea what they were smoking at the time. -- Dmitry Olshansky
Jul 10 2012
prev sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Tuesday, July 10, 2012 22:04:17 Timon Gehr wrote:
  property int delegate() foo(){ ... }
  property int bar(){ ... }
 int baz(){ ... }
 
 foo(); // calls the delegate.
 bar(); // illegal
 baz; // ok, call baz
 
 dmd -property gets every single one of these wrong. -property does _not_
 enforce  property semantics.
The current implementation of -property is horribly broken: http://d.puremagic.com/issues/show_bug.cgi?id=4183 http://d.puremagic.com/issues/show_bug.cgi?id=8162 It's not actually enforcing what it's supposed to enforce, and it needs to be fixed. - Jonathan M Davis
Jul 10 2012
prev sibling parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 07/09/2012 04:20 PM, Timon Gehr wrote:
 On 07/10/2012 12:53 AM, Jonathan M Davis wrote:
 dmd is generally good about not having
 useless warnings.
case 0,1: // warning: switch fallthrough (nonsense) case 2,3: This is the only kind of warning I get (clearly a bug, and it is reported).
I thought the code above was illegal at least in 2.059. I get an error unless I use goto case: void main() { int i; int j; switch (i) { case 0,1: goto case; // goto, embraced by D :) case 2,3: j = 42; break; default: j = 43; } } Ali
Jul 09 2012
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 07/10/2012 01:41 AM, Ali Çehreli wrote:
 On 07/09/2012 04:20 PM, Timon Gehr wrote:
  > On 07/10/2012 12:53 AM, Jonathan M Davis wrote:

  >> dmd is generally good about not having
  >> useless warnings.
  >
  > case 0,1: // warning: switch fallthrough (nonsense)
  > case 2,3:
  >
  > This is the only kind of warning I get (clearly a bug, and it is
  > reported).

 I thought the code above was illegal at least in 2.059.
You can write the code as case 0: case 1: case 2,3: and be ok.
 I get an error
 unless I use goto case:

 void main()
 {
      int i;
      int j;

      switch (i) {
      case 0,1:
          goto case;  // goto, embraced by D :)

      case 2,3:
          j = 42;
          break;

      default:
          j = 43;
      }
 }

 Ali
The error only shows up if -w is used.
Jul 09 2012
prev sibling parent reply Jacob Carlborg <doob me.com> writes:
On 2012-07-09 23:00, Timon Gehr wrote:

 Actually you need a random-access range with assignable elements. Map
 would need to be provided with an inverse mapping to support that.

 zip has assignable elements when the source ranges do.
Are you saying I can't sort a range that comes from "map"? To me it seems like std.algorithm and ranges are a complete failure. -- /Jacob Carlborg
Jul 09 2012
next sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 10-Jul-12 10:54, Jacob Carlborg wrote:
 On 2012-07-09 23:00, Timon Gehr wrote:

 Actually you need a random-access range with assignable elements. Map
 would need to be provided with an inverse mapping to support that.

 zip has assignable elements when the source ranges do.
Are you saying I can't sort a range that comes from "map"? To me it seems like std.algorithm and ranges are a complete failure.
Can you do it in other languages? -- Dmitry Olshansky
Jul 09 2012
parent reply Jacob Carlborg <doob me.com> writes:
On 2012-07-10 08:59, Dmitry Olshansky wrote:

 Can you do it in other languages?
Sure, in Ruby, but that only works on arrays: p [5, 3, 5, 6, 8].uniq.map{ |e| e.to_s }.sort Prints: ["3", "5", "6", "8"] -- /Jacob Carlborg
Jul 10 2012
next sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 10-Jul-12 13:35, Jacob Carlborg wrote:
 On 2012-07-10 08:59, Dmitry Olshansky wrote:

 Can you do it in other languages?
Sure, in Ruby, but that only works on arrays: p [5, 3, 5, 6, 8].uniq.map{ |e| e.to_s }.sort
and what type has the return of map ? Let me guess - array.
 Prints:

 ["3", "5", "6", "8"]
Please count the number of allocations in your paste of Ruby. -- Dmitry Olshansky
Jul 10 2012
parent reply Jacob Carlborg <doob me.com> writes:
On 2012-07-10 12:05, Dmitry Olshansky wrote:

 and what type has the return of map ? Let me guess - array.
Yes, and that is what I _want_. I have no need for streaming data from the network into a linked list, filter it and then convert it to an array (or something similar). I want to start with an array and end with an array.
 Please count the number of allocations in your paste of Ruby.
Probably four (if you count the initial allocation for the array literal). Plus a couple for the "to_s" method. But I can use the same methods and modify the array in place instead: a = [5, 3, 5, 6, 8] a.uniq! a.map!{ |e| e.to_s } a.sort! p a Prints: ["3", "5", "6", "8"] The corresponding D version would be: auto a = [5, 3, 5, 6, 8].uniq.map!(x => x.to!(string)).array.sort.array; writeln(a); I'm guessing that's three allocations. But that doesn't even work, it prints: ["3", "5", "5", "6", "8"] -- /Jacob Carlborg
Jul 10 2012
next sibling parent reply Nick Treleaven <nospam example.net> writes:
On 10/07/2012 12:37, Jacob Carlborg wrote:
 The corresponding D version would be:

 auto a = [5, 3, 5, 6, 8].uniq.map!(x => x.to!(string)).array.sort.array;
 writeln(a);

 I'm guessing that's three allocations. But that doesn't even work, it
 prints:

 ["3", "5", "5", "6", "8"]
uniq needs sorted input: auto r = [5, 3, 5, 6, 8].sort.uniq.map!(x => x.to!string); writeln(r); Tested with dmd 2.059. I think the above should be one allocation (except for the strings). Maybe uniq should require a SortedRange? Nick
Jul 10 2012
next sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 10-Jul-12 16:50, Nick Treleaven wrote:
 On 10/07/2012 12:37, Jacob Carlborg wrote:
 The corresponding D version would be:

 auto a = [5, 3, 5, 6, 8].uniq.map!(x => x.to!(string)).array.sort.array;
 writeln(a);

 I'm guessing that's three allocations. But that doesn't even work, it
 prints:

 ["3", "5", "5", "6", "8"]
uniq needs sorted input: auto r = [5, 3, 5, 6, 8].sort.uniq.map!(x => x.to!string); writeln(r); Tested with dmd 2.059. I think the above should be one allocation (except for the strings).
Yup and that was my whole point. You get fast and easy way with D or just very easy way with any suitable scripting language.
 Maybe uniq should require a SortedRange?
+1 And say so explicitly in the docs. -- Dmitry Olshansky
Jul 10 2012
parent Jacob Carlborg <doob me.com> writes:
On 2012-07-10 14:55, Dmitry Olshansky wrote:

 Maybe uniq should require a SortedRange?
And say so explicitly in the docs.
Than it should be enforced with a constraint (if possible). -- /Jacob Carlborg
Jul 10 2012
prev sibling next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 07/10/2012 02:50 PM, Nick Treleaven wrote:
 On 10/07/2012 12:37, Jacob Carlborg wrote:
 The corresponding D version would be:

 auto a = [5, 3, 5, 6, 8].uniq.map!(x => x.to!(string)).array.sort.array;
 writeln(a);

 I'm guessing that's three allocations. But that doesn't even work, it
 prints:

 ["3", "5", "5", "6", "8"]
uniq needs sorted input: auto r = [5, 3, 5, 6, 8].sort.uniq.map!(x => x.to!string); writeln(r); Tested with dmd 2.059. I think the above should be one allocation (except for the strings). Maybe uniq should require a SortedRange? Nick
uniq provides useful functionality even if the input is not sorted.
Jul 10 2012
prev sibling next sibling parent Jacob Carlborg <doob me.com> writes:
On 2012-07-10 14:50, Nick Treleaven wrote:

 uniq needs sorted input:

 auto r = [5, 3, 5, 6, 8].sort.uniq.map!(x => x.to!string);
 writeln(r);

 Tested with dmd 2.059.
 I think the above should be one allocation (except for the strings).
But I want the result to be an array, which would require an additional allocation. -- /Jacob Carlborg
Jul 10 2012
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 7/10/12 8:50 AM, Nick Treleaven wrote:
 On 10/07/2012 12:37, Jacob Carlborg wrote:
 The corresponding D version would be:

 auto a = [5, 3, 5, 6, 8].uniq.map!(x => x.to!(string)).array.sort.array;
 writeln(a);

 I'm guessing that's three allocations. But that doesn't even work, it
 prints:

 ["3", "5", "5", "6", "8"]
uniq needs sorted input: auto r = [5, 3, 5, 6, 8].sort.uniq.map!(x => x.to!string); writeln(r); Tested with dmd 2.059. I think the above should be one allocation (except for the strings). Maybe uniq should require a SortedRange?
Yes, please file a bug. Thanks! Andrei
Jul 10 2012
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 7/10/12 10:26 AM, Andrei Alexandrescu wrote:
 On 7/10/12 8:50 AM, Nick Treleaven wrote:
 On 10/07/2012 12:37, Jacob Carlborg wrote:
 The corresponding D version would be:

 auto a = [5, 3, 5, 6, 8].uniq.map!(x => x.to!(string)).array.sort.array;
 writeln(a);

 I'm guessing that's three allocations. But that doesn't even work, it
 prints:

 ["3", "5", "5", "6", "8"]
uniq needs sorted input: auto r = [5, 3, 5, 6, 8].sort.uniq.map!(x => x.to!string); writeln(r); Tested with dmd 2.059. I think the above should be one allocation (except for the strings). Maybe uniq should require a SortedRange?
Yes, please file a bug. Thanks! Andrei
Actually I take that back. One may use uniq to remove duplicates in unsorted ranges. Andrei
Jul 10 2012
parent reply Jacob Carlborg <doob me.com> writes:
On 2012-07-10 16:54, Andrei Alexandrescu wrote:

 Actually I take that back. One may use uniq to remove duplicates in
 unsorted ranges.
How does that work? It didn't work in my example. -- /Jacob Carlborg
Jul 10 2012
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 07/10/2012 06:40 PM, Jacob Carlborg wrote:
 On 2012-07-10 16:54, Andrei Alexandrescu wrote:

 Actually I take that back. One may use uniq to remove duplicates in
 unsorted ranges.
How does that work? It didn't work in my example.
It works. It removes consecutive duplicates. 'uniq' in ruby is different, which is strange as the name was taken from the command-line facility. (that also removes consecutive duplicates)
Jul 10 2012
prev sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 10-Jul-12 15:37, Jacob Carlborg wrote:
 On 2012-07-10 12:05, Dmitry Olshansky wrote:

 and what type has the return of map ? Let me guess - array.
Yes, and that is what I _want_.
Too bad, as there is no need to make an array when you map something. I have no need for streaming data from
 the network into a linked list, filter it and then convert it to an
 array (or something similar). I want to start with an array and end with
 an array.
Then you need something like transform. Anyway the result of map should be sortable it's a bug.
 Please count the number of allocations in your paste of Ruby.
Probably four (if you count the initial allocation for the array literal). Plus a couple for the "to_s" method.
Now scale the problem to at least ~ 10^6 ...
 But I can use the same methods and modify the array in place instead:

 a = [5, 3, 5, 6, 8]
 a.uniq!
 a.map!{ |e| e.to_s }
 a.sort!
 p a

 Prints:

 ["3", "5", "6", "8"]

 The corresponding D version would be:

 auto a = [5, 3, 5, 6, 8].uniq.map!(x => x.to!(string)).array.sort.array;
The last array is unnecessary as sort is in-place. Also why would you not sort before map? It'd be faster this way as it's sorting integers. Thus it's only 2 and one of them is literal. The map can't be sorted because uniq produces lazy bidirectional range. Thus you turn it into array as simple as that. My version would be: auto a = [5, 3, 5, 6, 8].sort().uniq().map!(x => x.to!(string))(); fixed?
 writeln(a);

 I'm guessing that's three allocations. But that doesn't even work, it
 prints:

 ["3", "5", "5", "6", "8"]
Because uniq work only on sorted ranges? Have you tried reading docs? " Iterates unique consecutive elements of the given range (functionality akin to the uniq system utility). Equivalence of elements is assessed by using the predicate pred, by default "a == b". If the given range is bidirectional, uniq also yields a bidirectional range. " Though it doesn't explicitly mentions it, the example is: int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ]; assert(equal(uniq(arr), [ 1, 2, 3, 4, 5 ][])); And it's a general knowledge that you can't run uniq in reasonable speed on unsorted sequence. (it'd take O(N^2) which is worse then sorting and then doing unique). -- Dmitry Olshansky
Jul 10 2012
next sibling parent reply Jacob Carlborg <doob me.com> writes:
On 2012-07-10 14:53, Dmitry Olshansky wrote:

 Too bad, as there is no need to make an array when you map something.
How do you store your ranges in a struct or class? Most of them are voldemort types.
 Then you need something like transform. Anyway the result of map should
 be sortable it's a bug.
Thank you for clearing that up.
 Please count the number of allocations in your paste of Ruby.
Probably four (if you count the initial allocation for the array literal). Plus a couple for the "to_s" method.
Now scale the problem to at least ~ 10^6 ...
 But I can use the same methods and modify the array in place instead:

 a = [5, 3, 5, 6, 8]
 a.uniq!
 a.map!{ |e| e.to_s }
 a.sort!
 p a

 Prints:

 ["3", "5", "6", "8"]

 The corresponding D version would be:

 auto a = [5, 3, 5, 6, 8].uniq.map!(x => x.to!(string)).array.sort.array;
 The last array is unnecessary as sort is in-place.
Again, I want an array, not a range.
 Also why would you not sort before map? It'd be faster this way as it's
 sorting integers.
Isn't it obvious that is just an example and not real code. I'm trying to keep the code as short as possible here.
 Thus it's only 2 and one of them is literal. The map can't be sorted
 because uniq produces lazy bidirectional range. Thus you turn it into
 array as simple as that.

 My version would be:

 auto a = [5, 3, 5, 6, 8].sort().uniq().map!(x => x.to!(string))();

 fixed?
Still need an array. Real code: https://github.com/jacob-carlborg/dstep/blob/master/dstep/translator/IncludeHandler.d#L124 I want the end result to be sorted.
 Because uniq work only on sorted ranges? Have you tried reading docs?
 "
 Iterates unique consecutive elements of the given range (functionality
 akin to the uniq system utility). Equivalence of elements is assessed by
 using the predicate pred, by default "a == b". If the given range is
 bidirectional, uniq also yields a bidirectional range.
 "
 Though it doesn't explicitly mentions it, the example is:
Yes, exactly.
 int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ];
 assert(equal(uniq(arr), [ 1, 2, 3, 4, 5 ][]));
How should I know that from the example? -- /Jacob Carlborg
Jul 10 2012
next sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 10-Jul-12 18:15, Jacob Carlborg wrote:
 On 2012-07-10 14:53, Dmitry Olshansky wrote:

 Too bad, as there is no need to make an array when you map something.
How do you store your ranges in a struct or class? Most of them are voldemort types.
typeof to the rescue. In fact I'm not so proud of voldemort types. As when you need to sotre range somewhere they stand in your way for no benefit.
 Then you need something like transform. Anyway the result of map should
 be sortable it's a bug.
Thank you for clearing that up.
 The corresponding D version would be:

 auto a = [5, 3, 5, 6, 8].uniq.map!(x => x.to!(string)).array.sort.array;
 The last array is unnecessary as sort is in-place.
Again, I want an array, not a range.
auto a = [5, 3, 5, 6, 8].uniq.map!(x => x.to!(string)).array; sort(a); return a; Just use the same array, it's just that sort returns a wrapper around array (or other range) that indicates it's sorted by predicate x. It can then help to reuse this information e.g. to perforam binary search etc.
 Also why would you not sort before map? It'd be faster this way as it's
 sorting integers.
Isn't it obvious that is just an example and not real code. I'm trying to keep the code as short as possible here.
Sorry, it wasn't.
 Thus it's only 2 and one of them is literal. The map can't be sorted
 because uniq produces lazy bidirectional range. Thus you turn it into
 array as simple as that.

 My version would be:

 auto a = [5, 3, 5, 6, 8].sort().uniq().map!(x => x.to!(string))();

 fixed?
Still need an array. Real code: https://github.com/jacob-carlborg/dstep/blob/master/dstep/translator/IncludeHandler.d#L124 I want the end result to be sorted.
Just take an array and call sort on it like in the old days. I don't think that stuffing it into one liner is required. Again if you need an array just call array at the end that's how it's supposed to be.
 Because uniq work only on sorted ranges? Have you tried reading docs?
 "
 Iterates unique consecutive elements of the given range (functionality
 akin to the uniq system utility). Equivalence of elements is assessed by
 using the predicate pred, by default "a == b". If the given range is
 bidirectional, uniq also yields a bidirectional range.
 "
 Though it doesn't explicitly mentions it, the example is:
Yes, exactly.
 int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ];
 assert(equal(uniq(arr), [ 1, 2, 3, 4, 5 ][]));
How should I know that from the example?
Dunno, to me it says SORTED in one big scary thought. Again it should ether check constraint or put some more useful description. e.g. "(functionality akin to the uniq system utility)" doesn't strike me as helpful. -- Dmitry Olshansky
Jul 10 2012
parent reply Jacob Carlborg <doob me.com> writes:
On 2012-07-10 16:36, Dmitry Olshansky wrote:

 typeof to the rescue. In fact I'm not so proud of voldemort types. As
 when you need to sotre range somewhere they stand in your way for no
 benefit.
I'm not exactly sure how you mean but this is what I came up with: import std.algorithm; import std.traits; import std.conv; class Foo { auto bar () { return [3, 4].map!(x => x.to!(string)); } ReturnType!(bar) x; } Which is just the worst idea ever. BTW I can't see how "typeof" would work.
 auto a = [5, 3, 5, 6, 8].uniq.map!(x => x.to!(string)).array;
 sort(a);
 return a;

 Just use the same array, it's just that sort returns a wrapper around
 array (or other range) that indicates it's sorted by predicate x. It can
 then help to reuse this information e.g. to perforam binary search etc.
Aha, I didn't know that it sorted in place.
 Just take an array and call sort on it like in the old days. I don't
 think that stuffing it into one liner is required.
 Again if you need an array just call array at the end that's how it's
 supposed to be.
See above.
 Dunno, to me it says SORTED in one big scary thought. Again it should
 ether check constraint or put some more useful description. e.g.
 "(functionality akin to the uniq system utility)" doesn't strike me as
 helpful.
Sure, this particular example uses a sorted array, but nothing says an unsorted array won't work. Does it only handle ints. It doesn't say anything about that in the documentation and the example uses ints. Then it must only accept ints. You see how stupid that is. -- /Jacob Carlborg
Jul 10 2012
next sibling parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Tuesday, July 10, 2012 18:57:25 Jacob Carlborg wrote:
 On 2012-07-10 16:36, Dmitry Olshansky wrote:
 typeof to the rescue. In fact I'm not so proud of voldemort types. As
 when you need to sotre range somewhere they stand in your way for no
 benefit.
I'm not exactly sure how you mean but this is what I came up with: import std.algorithm; import std.traits; import std.conv; class Foo { auto bar () { return [3, 4].map!(x => x.to!(string)); } ReturnType!(bar) x; }
typeof(bar()) x; works. But regardless, given that you're dealing with a return type which is auto, there's really no other choice. Even if we weren't using voldemort types for stuff like map, the return type would still be templated and depend on the actual arguments to map, making writing the type a pain - especially if it's complicated; until (which _doesn't_ use a voldemort type) is a prime example of this. You end up with something like Until!("a == b",int[],int) for a basic call to until, and it gets really nasty if you start chaining function calls so that the range passed to Until is far more complicated than int[]. Using ReturnType and typeof becames the sane thing to do (and much more maintainable too, since you don't have to change it if/when you change the call to map enough that it's return type changes). It does take some getting used to, but it works very well. You just have to realize that if you're operating on ranges, you're generally _not_ caring what they exact type is, and you use auto and templates a lot. Sometimes converting the result to an array is exactly what you want to do, but the less you do that, the more efficient your code will be. - Jonathan M Davis
Jul 10 2012
parent reply Jacob Carlborg <doob me.com> writes:
On 2012-07-10 19:30, Jonathan M Davis wrote:

 typeof(bar()) x;

 works. But regardless, given that you're dealing with a return type which is
 auto, there's really no other choice. Even if we weren't using voldemort types
 for stuff like map, the return type would still be templated and depend on the
 actual arguments to map, making writing the type a pain - especially if it's
 complicated; until (which _doesn't_ use a voldemort type) is a prime example
 of this. You end up with something like Until!("a == b",int[],int) for a basic
 call to until, and it gets really nasty if you start chaining function calls
 so that the range passed to Until is far more complicated than int[]. Using
 ReturnType and typeof becames the sane thing to do (and much more maintainable
 too, since you don't have to change it if/when you change the call to map
 enough that it's return type changes). It does take some getting used to, but
 it works very well. You just have to realize that if you're operating on
 ranges, you're generally _not_ caring what they exact type is, and you use
 auto and templates a lot. Sometimes converting the result to an array is
 exactly what you want to do, but the less you do that, the more efficient your
 code will be.
First, both using typeof and ReturnType forces me to have the instance variable below the method due to otherwise forward reference errors. Which I really, really don't like. Second, it would be much easier if it would be possible to better name these ranges, something like interfaces but without polymorphism. This as been mentioned several times before. -- /Jacob Carlborg
Jul 10 2012
parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Tuesday, July 10, 2012 21:07:51 Jacob Carlborg wrote:
 Second, it would be much easier if it would be possible to better name
 these ranges, something like interfaces but without polymorphism. This
 as been mentioned several times before.
They're templated types. They have to be templated types. And since they're templated types, better names do you no good whatsoever as far as declaring a variable goes. You'll _never_ be able to do something like NiceName range; NiceName will always be templated. The _closest_ that you get is with Voldemort types. Since they're templated as part of the function that they're in rather than separately, they end up with names such as Result or FilteredRange, but you couldn't do FilteredRange range; because that type depends on its outer scope (in this case, filter). You'd _still_ have to use typeof or ReturnType if you need to declare such a variable without directly assigning it (in which case, you can use auto). And if you have a separate range type rather than a Voldemort Type, you end up with stuff like Until!("a == b", string, dchar). The templated nature of ranges makes it impossible to have friendly names which you can use to simply declare variables of a particular range type. auto, ReturnType, and typeof are required tools for dealing with templated types like this. - Jonathan M Davis
Jul 10 2012
parent "Daniel Murphy" <yebblies nospamgmail.com> writes:
"Jonathan M Davis" <jmdavisProg gmx.com> wrote in message 
news:mailman.249.1341951069.31962.digitalmars-d puremagic.com...
 On Tuesday, July 10, 2012 21:07:51 Jacob Carlborg wrote:
 Second, it would be much easier if it would be possible to better name
 these ranges, something like interfaces but without polymorphism. This
 as been mentioned several times before.
They're templated types. They have to be templated types. And since they're templated types, better names do you no good whatsoever as far as declaring a variable goes. You'll _never_ be able to do something like NiceName range;
This isn't really true. You can still in some cases the type relative to some other type. (warning: old code, may not compile any more) Sure, you can use auto and typeof, but that doesn't make it clearer. struct SubSequences(R) { R r; R s; Take!R c; int n; this(R r) { this.r = r; s = r; n = 0; c = take(r, 1); popFront(); } void popFront() { c.popFront(); if (c.empty) { c = take(r, ++n); s.popFront(); } } Take!R front() { return c; } bool empty() { return s.empty; } typeof(this) save() { return this; } }; SubSequences!R subSequences(R)(R r) { return SubSequences!R(r); }
Jul 10 2012
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 7/10/12 12:57 PM, Jacob Carlborg wrote:
 On 2012-07-10 16:36, Dmitry Olshansky wrote:
 Dunno, to me it says SORTED in one big scary thought. Again it should
 ether check constraint or put some more useful description. e.g.
 "(functionality akin to the uniq system utility)" doesn't strike me as
 helpful.
Sure, this particular example uses a sorted array, but nothing says an unsorted array won't work.
Clearly this and any documentation can be improved, but I'd say if it says "range" there there's no assumption "sorted range" there. I think the main thing that could be expressed better is "unique consecutive".
 Does it only handle ints. It doesn't say anything about that in the
 documentation and the example uses ints. Then it must only accept ints.
I think it would be onerous to mention for each algorithm, although clearly they all are generic, that they can handle ranges with any element type.
 You see how stupid that is.
That being what? Andrei
Jul 10 2012
parent Jacob Carlborg <doob me.com> writes:
On 2012-07-10 19:55, Andrei Alexandrescu wrote:

 Clearly this and any documentation can be improved, but I'd say if it
 says "range" there there's no assumption "sorted range" there. I think
 the main thing that could be expressed better is "unique consecutive".
Fair enough.
 I think it would be onerous to mention for each algorithm, although
 clearly they all are generic, that they can handle ranges with any
 element type.

 You see how stupid that is.
That being what?
I was trying to point out that one cannot assume how a function behaves just by looking at one example. Specially not a template function. -- /Jacob Carlborg
Jul 10 2012
prev sibling next sibling parent travert phare.normalesup.org (Christophe Travert) writes:
Jacob Carlborg , dans le message (digitalmars.D:171690), a écrit :
 int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ];
 assert(equal(uniq(arr), [ 1, 2, 3, 4, 5 ][]));
How should I know that from the example?
Maybe there should be an example with an unsorted range, and a better explanation: | auto uniq(...) | Iterates unique consecutive elements of a given range (...) | Note that equivalent elements are kept if they are not consecutive. | | Example: | int[] arr = [ 1, 2, 2, 3, 4, 4, 4, 2, 4, 4]; | assert(equal(uniq(arr), [ 1, 2, 3, 4, 2, 4][]));
Jul 10 2012
prev sibling parent reply "Simen Kjaeraas" <simen.kjaras gmail.com> writes:
On Tue, 10 Jul 2012 16:15:09 +0200, Jacob Carlborg <doob me.com> wrote:

 On 2012-07-10 14:53, Dmitry Olshansky wrote:

 Too bad, as there is no need to make an array when you map something.
How do you store your ranges in a struct or class? Most of them are voldemort types.
Well, there is std.range.inputRangeObject, but as the name indicates, it's only an input range.
 "
 Iterates unique consecutive elements of the given range (functionality
 akin to the uniq system utility). Equivalence of elements is assessed by
 using the predicate pred, by default "a == b". If the given range is
 bidirectional, uniq also yields a bidirectional range.
 "
 Though it doesn't explicitly mentions it, the example is:
Yes, exactly.
 int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ];
 assert(equal(uniq(arr), [ 1, 2, 3, 4, 5 ][]));
How should I know that from the example?
You shouldn't. The description however, says 'unique consecutive elements', which *does* explain it. -- Simen
Jul 10 2012
parent =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 07/10/2012 10:48 AM, Simen Kjaeraas wrote:
 On Tue, 10 Jul 2012 16:15:09 +0200, Jacob Carlborg <doob me.com> wrote:
 How do you store your ranges in a struct or class? Most of them are
 voldemort types.
Well, there is std.range.inputRangeObject, but as the name indicates
As the name "misleads"... :)
, it's
 only an input range.
... it can be used as any one of the non-OutputRanges: import std.algorithm; import std.range; import std.stdio; void main() { int[] a1 = [1, 2, 3]; ForwardRange!int r1 = inputRangeObject(map!"2 * a"(a1)); ForwardRange!int r2 = inputRangeObject(map!"a ^^ 2"(a1)); auto a2 = [r1, r2]; writeln(a2); } Replace ForwardRange!int above with any other non-OutputRange, and as long as the input to inputRangeObject() is compatible, it will work. (static if magic). Ali
Jul 10 2012
prev sibling next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 07/10/2012 02:53 PM, Dmitry Olshansky wrote:
 On 10-Jul-12 15:37, Jacob Carlborg wrote:
 On 2012-07-10 12:05, Dmitry Olshansky wrote:

 and what type has the return of map ? Let me guess - array.
Yes, and that is what I _want_.
Too bad, as there is no need to make an array when you map something. I have no need for streaming data from
 the network into a linked list, filter it and then convert it to an
 array (or something similar). I want to start with an array and end with
 an array.
Then you need something like transform. Anyway the result of map should be sortable it's a bug.
What would sort do? Special case the result of map and then call schwartzSort on the underlying range?
Jul 10 2012
parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 10-Jul-12 19:00, Timon Gehr wrote:
 On 07/10/2012 02:53 PM, Dmitry Olshansky wrote:
 On 10-Jul-12 15:37, Jacob Carlborg wrote:
 On 2012-07-10 12:05, Dmitry Olshansky wrote:

 and what type has the return of map ? Let me guess - array.
Yes, and that is what I _want_.
Too bad, as there is no need to make an array when you map something. I have no need for streaming data from
 the network into a linked list, filter it and then convert it to an
 array (or something similar). I want to start with an array and end with
 an array.
Then you need something like transform. Anyway the result of map should be sortable it's a bug.
What would sort do? Special case the result of map and then call schwartzSort on the underlying range?
It may be a good idea actually. I once found myself in a need to sort mapped range. I think I just sorted original with "mapped" predicate it could get slow but in my case it was ok. Then assumeSorted(map!(...)). -- Dmitry Olshansky
Jul 10 2012
prev sibling parent travert phare.normalesup.org (Christophe Travert) writes:
Dmitry Olshansky , dans le message (digitalmars.D:171679), a écrit :
 Because uniq work only on sorted ranges? Have you tried reading docs?
 "
 Iterates unique consecutive elements of the given range (functionality 
 akin to the uniq system utility). Equivalence of elements is assessed by 
 using the predicate pred, by default "a == b". If the given range is 
 bidirectional, uniq also yields a bidirectional range.
 "
Not, as the doc says, uniq work on any range, but remove only the consecutive elements. It you want to remove all duplicates, then you need a sorted range.
Jul 10 2012
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 7/10/12 5:35 AM, Jacob Carlborg wrote:
 On 2012-07-10 08:59, Dmitry Olshansky wrote:

 Can you do it in other languages?
Sure, in Ruby, but that only works on arrays: p [5, 3, 5, 6, 8].uniq.map{ |e| e.to_s }.sort
This is very inefficient. I agree that if efficiency wasn't a concern for std.algorithm, its API would have been different. As things are, I think std.algorithm strikes a very good balance between efficiency and usability. Andrei
Jul 10 2012
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Tuesday, July 10, 2012 10:21:23 Andrei Alexandrescu wrote:
 On 7/10/12 5:35 AM, Jacob Carlborg wrote:
 On 2012-07-10 08:59, Dmitry Olshansky wrote:
 Can you do it in other languages?
Sure, in Ruby, but that only works on arrays: p [5, 3, 5, 6, 8].uniq.map{ |e| e.to_s }.sort
This is very inefficient. I agree that if efficiency wasn't a concern for std.algorithm, its API would have been different. As things are, I think std.algorithm strikes a very good balance between efficiency and usability.
The other thing that affects a lot is infinite ranges. The functions with lazy results work wonderfully with infinite ranges but would generally result in infinite loops if used with functions with eager results. auto vals = map!"a % 10"(rndGen()); works great, but you'd be forced to use take directly on rndGen pretty much all the time you wanted to do something like that if functions like map were lazy. But I suspect that the sort of people who will be complaining about map not returning an array are also the sort of people who won't be all that familar with operating on infinite lists and at least initially probably won't care. - Jonathan M Davis
Jul 10 2012
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 7/10/12 11:17 AM, Jonathan M Davis wrote:
 On Tuesday, July 10, 2012 10:21:23 Andrei Alexandrescu wrote:
 On 7/10/12 5:35 AM, Jacob Carlborg wrote:
 On 2012-07-10 08:59, Dmitry Olshansky wrote:
 Can you do it in other languages?
Sure, in Ruby, but that only works on arrays: p [5, 3, 5, 6, 8].uniq.map{ |e| e.to_s }.sort
This is very inefficient. I agree that if efficiency wasn't a concern for std.algorithm, its API would have been different. As things are, I think std.algorithm strikes a very good balance between efficiency and usability.
The other thing that affects a lot is infinite ranges. The functions with lazy results work wonderfully with infinite ranges but would generally result in infinite loops if used with functions with eager results. auto vals = map!"a % 10"(rndGen()); works great, but you'd be forced to use take directly on rndGen pretty much all the time you wanted to do something like that if functions like map were lazy. But I suspect that the sort of people who will be complaining about map not returning an array are also the sort of people who won't be all that familar with operating on infinite lists and at least initially probably won't care. - Jonathan M Davis
It's also about the unnecessary work done eagerly on finite but long inputs. Andrei
Jul 10 2012
prev sibling parent reply Brad Anderson <eco gnuk.net> writes:
On Tue, Jul 10, 2012 at 3:35 AM, Jacob Carlborg <doob me.com> wrote:

 On 2012-07-10 08:59, Dmitry Olshansky wrote:

  Can you do it in other languages?

 Sure, in Ruby, but that only works on arrays:

 p [5, 3, 5, 6, 8].uniq.map{ |e| e.to_s }.sort

 Prints:

 ["3", "5", "6", "8"]

 --
 /Jacob Carlborg
For what it's worth: e = 10_000_000 a = ((1..e).to_a + (1..e).to_a).sort.uniq.map{ |e| e } Runs in 21,320 ms on my machine with Ruby 1.9.3 whereas: auto end = 10_000_000; auto a = chain(iota(1, end), iota(1, end)).array() .sort() .uniq() .map!(n=>n).array(); Runs in 3,057ms with DMD 2.059. I believe they are largely equivalent but there is probably room for improvement on both. I removed to_s/to!string because I didn't want it allocation bound since we are talking about algorithm and not the GC or string conversion (with string conversion the numbers are 28,646ms for Ruby and 14,113ms for D). Regards, Brad Anderson
Jul 10 2012
parent reply Jacob Carlborg <doob me.com> writes:
On 2012-07-10 20:53, Brad Anderson wrote:

 For what it's worth:

      e = 10_000_000
      a = ((1..e).to_a + (1..e).to_a).sort.uniq.map{ |e| e }

 Runs in 21,320 ms on my machine with Ruby 1.9.3 whereas:

      auto end = 10_000_000;
      auto a = chain(iota(1, end), iota(1, end)).array()
                  .sort()
                  .uniq()
                  .map!(n=>n).array();

 Runs in 3,057ms with DMD 2.059.  I believe they are largely equivalent
 but there is probably room for improvement on both.  I removed
 to_s/to!string because I didn't want it allocation bound since we are
 talking about algorithm and not the GC or string conversion (with string
 conversion the numbers are 28,646ms for Ruby and 14,113ms for D).
For me, using Ruby 1.9.2 and DMD 2.059, D is only just under 10 seconds faster. -- /Jacob Carlborg
Jul 10 2012
parent Brad Anderson <eco gnuk.net> writes:
On Tue, Jul 10, 2012 at 1:22 PM, Jacob Carlborg <doob me.com> wrote:

 On 2012-07-10 20:53, Brad Anderson wrote:

  For what it's worth:
      e = 10_000_000
      a = ((1..e).to_a + (1..e).to_a).sort.uniq.map{ |e| e }

 Runs in 21,320 ms on my machine with Ruby 1.9.3 whereas:

      auto end = 10_000_000;
      auto a = chain(iota(1, end), iota(1, end)).array()
                  .sort()
                  .uniq()
                  .map!(n=>n).array();

 Runs in 3,057ms with DMD 2.059.  I believe they are largely equivalent
 but there is probably room for improvement on both.  I removed
 to_s/to!string because I didn't want it allocation bound since we are
 talking about algorithm and not the GC or string conversion (with string
 conversion the numbers are 28,646ms for Ruby and 14,113ms for D).
For me, using Ruby 1.9.2 and DMD 2.059, D is only just under 10 seconds faster. -- /Jacob Carlborg
I used -O -inline -noboundscheck -release -d to build. Regards, Brad Anderson
Jul 10 2012
prev sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Tuesday, July 10, 2012 08:54:18 Jacob Carlborg wrote:
 On 2012-07-09 23:00, Timon Gehr wrote:
 Actually you need a random-access range with assignable elements. Map
 would need to be provided with an inverse mapping to support that.
 
 zip has assignable elements when the source ranges do.
Are you saying I can't sort a range that comes from "map"? To me it seems like std.algorithm and ranges are a complete failure.
It's a complete failure because not every range works with every range-based function? We have isInputRange, isForwardRange, isRandomAccessRange, hasSlicing, etc. for a reason. Different ranges have different capabilities, and different algorithms generate different types of ranges based on what they do. For instance, filter cannot possibly have slicing, because it's on O(n) operation to determine which elements match the predicate. You have to iterate through _all_ of the elements. Rather than doing that (and therefore not working with infinite ranges and being inefficient with non-infinite ranges), it's lazy, and if you _do_ want to process all of the elements to know filter's length and therefore make it slicable, you generate a new range from it - generally with std.array.array. map is in the same boat. It has to generate new range type, and the choice is between being lazy and efficient (and therefore require a call to array) or being inefficient and calling array internally. - Jonathan M Davis
Jul 10 2012
parent reply Jacob Carlborg <doob me.com> writes:
On 2012-07-10 09:09, Jonathan M Davis wrote:

 It's a complete failure because not every range works with every range-based
 function? We have isInputRange, isForwardRange, isRandomAccessRange,
 hasSlicing, etc. for a reason. Different ranges have different capabilities,
and
 different algorithms generate different types of ranges based on what they do.
 For instance, filter cannot possibly have slicing, because it's on O(n)
 operation to determine which elements match the predicate. You have to iterate
 through _all_ of the elements. Rather than doing that (and therefore not
 working with infinite ranges and being inefficient with non-infinite ranges),
it's
 lazy, and if you _do_ want to process all of the elements to know filter's
 length and therefore make it slicable, you generate a new range from it -
 generally with std.array.array. map is in the same boat. It has to generate
 new range type, and the choice is between being lazy and efficient (and
 therefore require a call to array) or being inefficient and calling array
 internally.
Well, I haven't been able to use a single function from std.algorithm without adding a lot of calls to "array" or "to!(string)". I think the things I'm trying to do seems trivial and quite common. I'm I overrating std.algorithm or does it not fit my needs? -- /Jacob Carlborg
Jul 10 2012
next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 07/10/2012 11:41 AM, Jacob Carlborg wrote:
 On 2012-07-10 09:09, Jonathan M Davis wrote:

 It's a complete failure because not every range works with every
 range-based
 function? We have isInputRange, isForwardRange, isRandomAccessRange,
 hasSlicing, etc. for a reason. Different ranges have different
 capabilities, and
 different algorithms generate different types of ranges based on what
 they do.
 For instance, filter cannot possibly have slicing, because it's on O(n)
 operation to determine which elements match the predicate. You have to
 iterate
 through _all_ of the elements. Rather than doing that (and therefore not
 working with infinite ranges and being inefficient with non-infinite
 ranges), it's
 lazy, and if you _do_ want to process all of the elements to know
 filter's
 length and therefore make it slicable, you generate a new range from it -
 generally with std.array.array. map is in the same boat. It has to
 generate
 new range type, and the choice is between being lazy and efficient (and
 therefore require a call to array) or being inefficient and calling array
 internally.
Well, I haven't been able to use a single function from std.algorithm without adding a lot of calls to "array" or "to!(string)". I think the things I'm trying to do seems trivial and quite common. I'm I overrating std.algorithm or does it not fit my needs?
If you consider it a problem to call array or to!string when you want to get an array, then it does not fit your needs.
Jul 10 2012
prev sibling next sibling parent reply "Simen Kjaeraas" <simen.kjaras gmail.com> writes:
On Tue, 10 Jul 2012 11:41:02 +0200, Jacob Carlborg <doob me.com> wrote:

 On 2012-07-10 09:09, Jonathan M Davis wrote:

 It's a complete failure because not every range works with every  
 range-based
 function? We have isInputRange, isForwardRange, isRandomAccessRange,
 hasSlicing, etc. for a reason. Different ranges have different  
 capabilities, and
 different algorithms generate different types of ranges based on what  
 they do.
 For instance, filter cannot possibly have slicing, because it's on O(n)
 operation to determine which elements match the predicate. You have to  
 iterate
 through _all_ of the elements. Rather than doing that (and therefore not
 working with infinite ranges and being inefficient with non-infinite  
 ranges), it's
 lazy, and if you _do_ want to process all of the elements to know  
 filter's
 length and therefore make it slicable, you generate a new range from it  
 -
 generally with std.array.array. map is in the same boat. It has to  
 generate
 new range type, and the choice is between being lazy and efficient (and
 therefore require a call to array) or being inefficient and calling  
 array
 internally.
Well, I haven't been able to use a single function from std.algorithm without adding a lot of calls to "array" or "to!(string)". I think the things I'm trying to do seems trivial and quite common. I'm I overrating std.algorithm or does it not fit my needs?
bearophile (who else? :p) has suggested the addition of eager and in-place versions of some ranges, and I think he has a very good point. -- Simen
Jul 10 2012
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 7/10/12 8:52 AM, Simen Kjaeraas wrote:
 bearophile (who else? :p) has suggested the addition of eager and in-place
 versions of some ranges, and I think he has a very good point.
Where would good old loops not work for eager stuff? Andrei
Jul 10 2012
parent "Simen Kjaeraas" <simen.kjaras gmail.com> writes:
On Tue, 10 Jul 2012 16:27:31 +0200, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:

 On 7/10/12 8:52 AM, Simen Kjaeraas wrote:
 bearophile (who else? :p) has suggested the addition of eager and  
 in-place
 versions of some ranges, and I think he has a very good point.
Where would good old loops not work for eager stuff?
Mostly because I like the std.algorithm way of writing stuff, now we have UFCS. But yes, could not come up with a good case for not using loops beyond that. -- Simen
Jul 10 2012
prev sibling parent reply travert phare.normalesup.org (Christophe Travert) writes:
"Simen Kjaeraas" , dans le message (digitalmars.D:171678), a écrit :
 Well, I haven't been able to use a single function from std.algorithm  
 without adding a lot of calls to "array" or "to!(string)". I think the  
 things I'm trying to do seems trivial and quite common. I'm I overrating  
 std.algorithm or does it not fit my needs?
bearophile (who else? :p) has suggested the addition of eager and in-place versions of some ranges, and I think he has a very good point.
That would have been useful before UFSC. Now, writing .array() at the end of an algorithm call is not a pain. int[] = [1, 2, 2, 3].uniq().map!toString().array();
Jul 10 2012
next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Tuesday, July 10, 2012 15:21:14 Christophe Travert wrote:
 "Simen Kjaeraas" , dans le message (digitalmars.D:171678), a =C3=A9cr=
it :
 Well, I haven't been able to use a single function from std.algori=
thm
 without adding a lot of calls to "array" or "to!(string)". I think=
the
 things I'm trying to do seems trivial and quite common. I'm I over=
rating
 std.algorithm or does it not fit my needs?
=20 bearophile (who else? :p) has suggested the addition of eager and i=
n-place
 versions of some ranges, and I think he has a very good point.
=20 That would have been useful before UFSC. Now, writing .array() at the end of an algorithm call is not a pain. =20 int[] =3D [1, 2, 2, 3].uniq().map!toString().array();
It's not like auto result =3D array(map!"to!string(a)"(uniq([1, 2, 2, 3]))); is a pain either. It's just ordered differently. But regardless, it's easy to get an eager result by calling array on a = lazy=20 range, so there's no point in adding eager versions. They'd just be=20 duplicating code for no real benefit. Not to mention, if anyone having = to call=20 array on ranges all of the time, you should probably rethink how they'r= e using=20 ranges. It's definitely necessary some of the time, but most of the tim= e, you=20 can just operate on the lazy ranges and save yourself unnecessary alloc= ations. - Jonathan M Davis
Jul 10 2012
prev sibling parent reply "Simen Kjaeraas" <simen.kjaras gmail.com> writes:
On Tue, 10 Jul 2012 17:21:14 +0200, Christophe Travert  =

<travert phare.normalesup.org> wrote:

 "Simen Kjaeraas" , dans le message (digitalmars.D:171678), a =C3=A9cri=
t :
 Well, I haven't been able to use a single function from std.algorith=
m
 without adding a lot of calls to "array" or "to!(string)". I think t=
he
 things I'm trying to do seems trivial and quite common. I'm I  =
 overrating
 std.algorithm or does it not fit my needs?
bearophile (who else? :p) has suggested the addition of eager and =
 in-place
 versions of some ranges, and I think he has a very good point.
That would have been useful before UFSC. Now, writing .array() at the end of an algorithm call is not a pain. int[] =3D [1, 2, 2, 3].uniq().map!toString().array();
Please tell me how that is in-place. -- = Simen
Jul 10 2012
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 7/10/12 2:02 PM, Simen Kjaeraas wrote:
 On Tue, 10 Jul 2012 17:21:14 +0200, Christophe Travert
 <travert phare.normalesup.org> wrote:

 "Simen Kjaeraas" , dans le message (digitalmars.D:171678), a écrit :
 Well, I haven't been able to use a single function from std.algorithm
 without adding a lot of calls to "array" or "to!(string)". I think the
 things I'm trying to do seems trivial and quite common. I'm I
 overrating
 std.algorithm or does it not fit my needs?
bearophile (who else? :p) has suggested the addition of eager and in-place versions of some ranges, and I think he has a very good point.
That would have been useful before UFSC. Now, writing .array() at the end of an algorithm call is not a pain. int[] = [1, 2, 2, 3].uniq().map!toString().array();
Please tell me how that is in-place.
Let's say it doesn't perform unnecessary allocations. It's like you'd create the array ["1", "2", "3"] from the array [1, 2, 2, 3] using a loop and a couple of state variables. Andrei
Jul 10 2012
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 7/10/12 5:41 AM, Jacob Carlborg wrote:
 Well, I haven't been able to use a single function from std.algorithm
 without adding a lot of calls to "array" or "to!(string)". I think the
 things I'm trying to do seems trivial and quite common. I'm I overrating
 std.algorithm or does it not fit my needs?
It may be the case you're trying to write ruby in D. I rarely need to convert stuff to arrays. Andrei
Jul 10 2012
parent reply Jacob Carlborg <doob me.com> writes:
On 2012-07-10 16:22, Andrei Alexandrescu wrote:

 It may be the case you're trying to write ruby in D. I rarely need to
 convert stuff to arrays.
Mostly I receive an array, do some operations on it and then want to store the result in an instance variable in a class or struct. It's quite awkward to store a range in an instance variable. -- /Jacob Carlborg
Jul 10 2012
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 7/10/12 1:05 PM, Jacob Carlborg wrote:
 On 2012-07-10 16:22, Andrei Alexandrescu wrote:

 It may be the case you're trying to write ruby in D. I rarely need to
 convert stuff to arrays.
Mostly I receive an array, do some operations on it and then want to store the result in an instance variable in a class or struct. It's quite awkward to store a range in an instance variable.
Then store an array. "No one's put a gun to yer head." http://youtu.be/CB1Pij54gTw?t=2m29s Andrei
Jul 10 2012
parent reply Jacob Carlborg <doob me.com> writes:
On 2012-07-10 20:04, Andrei Alexandrescu wrote:

 Then store an array. "No one's put a gun to yer head."
 http://youtu.be/CB1Pij54gTw?t=2m29s
That's what I'm doing. -- /Jacob Carlborg
Jul 10 2012
parent travert phare.normalesup.org (Christophe Travert) writes:
Jacob Carlborg , dans le message (digitalmars.D:171769), a écrit :
 On 2012-07-10 20:04, Andrei Alexandrescu wrote:
 
 Then store an array. "No one's put a gun to yer head."
 http://youtu.be/CB1Pij54gTw?t=2m29s
That's what I'm doing.
And that's what you should do. Algorithm are not made to be stored in struct or class instance. You could use InputRange(E) and friends to do that, but that's often not optimal. Algorithm are here to do their job and output non-lazy result in the end.
Jul 10 2012
prev sibling next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday, July 09, 2012 22:09:54 Jacob Carlborg wrote:
 Almost every time I'm trying to use std.algorithm I run into some kind
 of error, for what seems to be fairly trivial and what one would expect
 to work. It feels like I'm constantly fighting with std.algorithm. For
 example:
 
 import std.algorithm;
 import std.range;
 
 struct Foo {}
 
 auto f = Foo();
 auto foos = [f];
 auto foo = foos.map!(x => "foo");
 auto bar = foo.chain("bar");
 
 This simple example result in the follow error:
 
 http://pastebin.com/E4LV2UBE
 
 Another example:
 
 auto str = ["foo", "bar"].map!(x => x);
 auto f = str.sort();
 
 Results in:
 
 http://pastebin.com/BeePWQk9
 
 I'm using DMD 2.059.
http://d.puremagic.com/issues/show_bug.cgi?id=8367 http://d.puremagic.com/issues/show_bug.cgi?id=8368 - Jonathan M Davis
Jul 10 2012
parent Jacob Carlborg <doob me.com> writes:
On 2012-07-10 09:25, Jonathan M Davis wrote:

 http://d.puremagic.com/issues/show_bug.cgi?id=8367
 http://d.puremagic.com/issues/show_bug.cgi?id=8368
Thanks. -- /Jacob Carlborg
Jul 10 2012
prev sibling parent reply "Mehrdad" <wfunction hotmail.com> writes:
Another example of how std.algorithm is so hard to use (it's 
almost tempting me to start swearing...):

How do you remove an item from an array in place?

It seems so darn simple, and yet it's not in std.algorithm (or 
std.range). It makes something so easy so tedious.
Jul 15 2012
next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Sunday, July 15, 2012 23:42:29 Mehrdad wrote:
 Another example of how std.algorithm is so hard to use (it's
 almost tempting me to start swearing...):
 
 How do you remove an item from an array in place?
 
 It seems so darn simple, and yet it's not in std.algorithm (or
 std.range). It makes something so easy so tedious.
Iterators have exactly the same problem for exactly the same reasons as std.algorithm.remove (e.g. take a look at C++'s erase function). The only way to do this in place would be to create a separate removeInPlace function specifically for arrays. But since all it takes is reassigning the result of std.algorithm.remove to the array that you passed in and an std.array.replaceInPlace would be doing exactly that, I don't think that adding such a function buys us much: auto arr = [10, 22, 19, 4, 6]; arr = remove(arr, 3); assert(arr == [10, 22, 19, 6]); The main problem is understanding why remove (or erase in C++) works this way, which seems to throw off a bunch of people in both D and C++, but it's something that we're pretty much stuck with. You need the actual container (not an iterator or range) if you want to actually remove the element. - Jonathan M Davis
Jul 15 2012
next sibling parent reply "Mehrdad" <wfunction hotmail.com> writes:
On Sunday, 15 July 2012 at 22:03:33 UTC, Jonathan M Davis wrote:
     auto arr = [10, 22, 19, 4, 6];
     arr = remove(arr, 3);
     assert(arr == [10, 22, 19, 6]);
Yeah, the problem is that this reallocates... (not claiming remove() itself is supposed to be efficient, but this is making it even worse)
 The main problem is understanding why remove (or erase in C++) 
 works this way, which seems to throw off a bunch of people in 
 both D and C++, but it's something that we're pretty much stuck 
 with. You need the actual container (not an iterator or range) 
 if you want to actually remove the element.
Well, for arrays, the "actual container" is the array, so that doesn't work either. :\ On the other hand, even C++ has vector<T>::erase()!
Jul 15 2012
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 7/15/12 6:22 PM, Mehrdad wrote:
 On Sunday, 15 July 2012 at 22:03:33 UTC, Jonathan M Davis wrote:
 auto arr = [10, 22, 19, 4, 6];
 arr = remove(arr, 3);
 assert(arr == [10, 22, 19, 6]);
Yeah, the problem is that this reallocates...
doesn't
Jul 15 2012
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Sunday, July 15, 2012 18:24:47 Andrei Alexandrescu wrote:
 On 7/15/12 6:22 PM, Mehrdad wrote:
 On Sunday, 15 July 2012 at 22:03:33 UTC, Jonathan M Davis wrote:
 auto arr = [10, 22, 19, 4, 6];
 arr = remove(arr, 3);
 assert(arr == [10, 22, 19, 6]);
Yeah, the problem is that this reallocates...
doesn't
Yeah. It just slices. remove moves the elements over by one, and returns a slice of the range which is shorter by the number of elements removed. And since assigning one array is just assigning the ptr and length properties, there's no copying of the elements there, and no reallocations are required anywhere. Now, if you want to append to the array afterwards, then you're going to get a reallocation (unless you know that there are no other arrays referring to anything after the returned slice, in which case, you can use assumeSafeAppend make it so that it doesn't reallocate). But the removal involves no reallocations at all. - Jonathan M Davis
Jul 15 2012
parent reply "Mehrdad" <wfunction hotmail.com> writes:
On Sunday, 15 July 2012 at 22:39:47 UTC, Jonathan M Davis wrote:
 On Sunday, July 15, 2012 18:24:47 Andrei Alexandrescu wrote:
 On 7/15/12 6:22 PM, Mehrdad wrote:
 On Sunday, 15 July 2012 at 22:03:33 UTC, Jonathan M Davis 
 wrote:
 auto arr = [10, 22, 19, 4, 6];
 arr = remove(arr, 3);
 assert(arr == [10, 22, 19, 6]);
Yeah, the problem is that this reallocates...
doesn't
Yeah. It just slices.
Ooooooh, I misunderstood what was happening. Thanks to both you & Andrei!
Jul 15 2012
parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday, July 16, 2012 01:47:15 Mehrdad wrote:
 On Sunday, 15 July 2012 at 22:39:47 UTC, Jonathan M Davis wrote:
 On Sunday, July 15, 2012 18:24:47 Andrei Alexandrescu wrote:
 On 7/15/12 6:22 PM, Mehrdad wrote:
 On Sunday, 15 July 2012 at 22:03:33 UTC, Jonathan M Davis
 
 wrote:
 auto arr = [10, 22, 19, 4, 6];
 arr = remove(arr, 3);
 assert(arr == [10, 22, 19, 6]);
Yeah, the problem is that this reallocates...
doesn't
Yeah. It just slices.
Ooooooh, I misunderstood what was happening. Thanks to both you & Andrei!
std.algorithm.remove does pretty much exactly what the STL's erase function does, only it operates on ranges rather than iterators. - Jonathan M Davis
Jul 15 2012
prev sibling parent reply Jacob Carlborg <doob me.com> writes:
On 2012-07-16 00:03, Jonathan M Davis wrote:

 Iterators have exactly the same problem for exactly the same reasons as
 std.algorithm.remove (e.g. take a look at C++'s erase function). The only way
 to do this in place would be to create a separate removeInPlace function
 specifically for arrays. But since all it takes is reassigning the result of
 std.algorithm.remove to the array that you passed in and an
 std.array.replaceInPlace would be doing exactly that, I don't think that
 adding such a function buys us much:

      auto arr = [10, 22, 19, 4, 6];
      arr = remove(arr, 3);
      assert(arr == [10, 22, 19, 6]);

 The main problem is understanding why remove (or erase in C++) works this way,
 which seems to throw off a bunch of people in both D and C++, but it's
 something that we're pretty much stuck with. You need the actual container
 (not an iterator or range) if you want to actually remove the element.
It would be really useful if std.algorithm (and similar functions) would indicate clearly if they operate in place or not. It took me a while to understand that "sort" operates in place. In Ruby this is achieved by a naming convention: a = [3, 4, 5] -- /Jacob Carlborg
Jul 16 2012
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday, July 16, 2012 09:07:06 Jacob Carlborg wrote:
 On 2012-07-16 00:03, Jonathan M Davis wrote:
 Iterators have exactly the same problem for exactly the same reasons as
 std.algorithm.remove (e.g. take a look at C++'s erase function). The only
 way to do this in place would be to create a separate removeInPlace
 function specifically for arrays. But since all it takes is reassigning
 the result of std.algorithm.remove to the array that you passed in and an
 std.array.replaceInPlace would be doing exactly that, I don't think that
 
 adding such a function buys us much:
      auto arr = [10, 22, 19, 4, 6];
      arr = remove(arr, 3);
      assert(arr == [10, 22, 19, 6]);
 
 The main problem is understanding why remove (or erase in C++) works this
 way, which seems to throw off a bunch of people in both D and C++, but
 it's something that we're pretty much stuck with. You need the actual
 container (not an iterator or range) if you want to actually remove the
 element.
It would be really useful if std.algorithm (and similar functions) would indicate clearly if they operate in place or not. It took me a while to understand that "sort" operates in place. In Ruby this is achieved by a naming convention: a = [3, 4, 5]
We do have InPlace in function names when one version of a function operates in place and another doesn't, but we haven't generally done that on functions which only have one version, and I don't expect that to change now (at least not for existing functions). In any case, _most_ range-based functions _don't_ operate in place, but it's certainly true that the ones that do should make that clear in their documentation. remove is a bit of a special case, however, in that it does the changes in place but doesn't take a ref, so while the return value is shortened to not include the removed elements, the original is just as long as it was before (which is useful in cases where you want to then set the elements at the end), and you end up with something that's sort of in place and sort of not. Regardless, remove is confusing enough to most people (just like erase in C++) that it's documentation needs to be very clear, but I don't know how good it is or isn't. Given the difficulty of explaining it properly and Merhdad's confusion, it probably stands to be improved. - Jonathan M Davis
Jul 16 2012
parent reply Jacob Carlborg <doob me.com> writes:
On 2012-07-16 09:18, Jonathan M Davis wrote:

 We do have InPlace in function names when one version of a function operates
 in place and another doesn't, but we haven't generally done that on functions
 which only have one version, and I don't expect that to change now (at least
 not for existing functions).
Yes, that's good. But we can always add that to the documentation. There can also be some general documentation about this on the top of the std.algorithm module. Something like: "No function operates in place unless it explicitly says so in the documentation or if its name has the 'inPlace' suffix."
 In any case, _most_ range-based functions _don't_ operate in place, but it's
 certainly true that the ones that do should make that clear in their
 documentation.

 remove is a bit of a special case, however, in that it does the changes in
 place but doesn't take a ref, so while the return value is shortened to not
 include the removed elements, the original is just as long as it was before
 (which is useful in cases where you want to then set the elements at the end),
 and you end up with something that's sort of in place and sort of not.
 Regardless, remove is confusing enough to most people (just like erase in C++)
 that it's documentation needs to be very clear, but I don't know how good it
 is or isn't. Given the difficulty of explaining it properly and Merhdad's
 confusion, it probably stands to be improved.
Just _because_ of how "remove" works in std.algorithm and "erase" in C++, I though "sort" behaved similar. -- /Jacob Carlborg
Jul 16 2012
parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday, July 16, 2012 10:08:11 Jacob Carlborg wrote:
 Just _because_ of how "remove" works in std.algorithm and "erase" in
 C++, I though "sort" behaved similar.
Well, it does in that it sorts in place and returns the result, but the result and the original are more in line with one another then they are with remove, since they're both sorted rather than having their lengths differ like they do with remove (though the result of sort is usually a different type from the original range, unlike with remove). But I don't dispute that the documentation needs improvement. It probably does. I haven't read through much of it recently, and in many cases, I probably already fully understand it anyway, so I'm not a good judge of how good it is. - Jonathan M Davis
Jul 16 2012
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 7/15/12 5:42 PM, Mehrdad wrote:
 Another example of how std.algorithm is so hard to use (it's almost
 tempting me to start swearing...):

 How do you remove an item from an array in place?

 It seems so darn simple, and yet it's not in std.algorithm (or
 std.range). It makes something so easy so tedious.
Look for "remove" here: http://dlang.org/phobos/std_algorithm.html Unfortunately the anchor called "remove" is swallowed by an unrelated enum value (we should fix that in ddoc). From the example: int[] a = [ 3, 5, 7, 8 ]; assert(remove(a, 1) == [ 3, 7, 8 ]); assert(a == [ 3, 7, 8, 8 ]); Therefore, to remove an element in place: int[] a = [ 3, 5, 7, 8 ]; a = remove(a, 1); You also have a less stable but faster version: a = remove!(SwapStrategy.unstable)(a, 1); Andrei
Jul 15 2012