Why is std.algorithm so complicated to use?

[Jacob Carlborg]

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.

[Andrei Alexandrescu]

Post by Jacob Carlborg
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
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");
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"]);

Post by Jacob Carlborg
auto str = ["foo", "bar"].map!(x => x);
auto f = str.sort();
http://pastebin.com/BeePWQk9

The first error message is at clear as it goes:

Error: r[i2] is not an lvalue


Andrei

[Ali Çehreli]

Post by Andrei Alexandrescu

Post by Jacob Carlborg
auto str = ["foo", "bar"].map!(x => x);
auto f = str.sort();
http://pastebin.com/BeePWQk9

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

[Timon Gehr]

Post by Ali Çehreli

Post by Andrei Alexandrescu

Post by Jacob Carlborg
auto str = ["foo", "bar"].map!(x => x);
auto f = str.sort();
http://pastebin.com/BeePWQk9

Error: r[i2] is not an lvalue

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.

[Jacob Carlborg]

Post by Ali Çehreli
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.

[Jonathan M Davis]

Post by Jacob Carlborg

Post by Ali Çehreli
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.

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

- Jonathan M Davis

[Jacob Carlborg]

Post by Jonathan M Davis
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.

[Simen Kjaeraas]

On Tue, 10 Jul 2012 09:04:31 +0200, Jonathan M Davis <jmdavisProg at gmx.com>

Post by Jonathan M Davis
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

[Andrei Alexandrescu]

Post by Simen Kjaeraas
On Tue, 10 Jul 2012 09:04:31 +0200, Jonathan M Davis

Post by Jonathan M Davis
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

[Jonathan M Davis]

Post by Simen Kjaeraas
On Tue, 10 Jul 2012 09:04:31 +0200, Jonathan M Davis <jmdavisProg at gmx.com>

Post by Jonathan M Davis
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

[Manfred Nowak]

Post by Andrei Alexandrescu

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

[...]

Post by Andrei Alexandrescu
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

[Jacob Carlborg]

Post by Andrei Alexandrescu
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?

Post by Andrei Alexandrescu
To fix the example, write
auto bar = foo.chain(["bar"]);

I think that's an ugly workaround.

Post by Andrei Alexandrescu

Post by Jacob Carlborg
auto str = ["foo", "bar"].map!(x => x);
auto f = str.sort();
http://pastebin.com/BeePWQk9

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

[Andrei Alexandrescu]

Post by Jacob Carlborg

Post by Andrei Alexandrescu
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.

Post by Jacob Carlborg

Post by Andrei Alexandrescu
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.

Post by Jacob Carlborg

Post by Andrei Alexandrescu

Post by Jacob Carlborg
auto str = ["foo", "bar"].map!(x => x);
auto f = str.sort();
http://pastebin.com/BeePWQk9

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.

Post by Jacob Carlborg
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.

Post by Jacob Carlborg
This just proves that std.algorithm is complicated to use. It's very
unintuitive.
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.

Post by Jacob Carlborg
string[] str = ["foo", "bar"].map!(x => x);
string[] f = str.sort();

Same here. map() does not return arrays, and for very good reasons.


Andrei

[H. S. Teoh]

Post by Andrei Alexandrescu

Post by Jacob Carlborg

Post by Andrei Alexandrescu
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.

Post by Andrei Alexandrescu
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

[Jacob Carlborg]

Post by Andrei Alexandrescu
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");

Post by Andrei Alexandrescu
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.

Post by Andrei Alexandrescu
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.

Post by Andrei Alexandrescu
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.

[Dmitry Olshansky]

Post by Jacob Carlborg

Post by Andrei Alexandrescu
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");
auto bar = foo.append("bar");

Post by Andrei Alexandrescu
Well I made minimal changes. Besides I don't know what the intent is.

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.

Post by Jacob Carlborg
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.

Post by Andrei Alexandrescu
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.

Post by Andrei Alexandrescu
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.

[Jacob Carlborg]

Post by Dmitry Olshansky
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".

Post by Dmitry Olshansky
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.

[Christophe Travert]

Post by Jacob Carlborg
I mean, is it possible to have the original code work?
auto bar = foo.chain("bar");
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.

Post by Jacob Carlborg
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.

[Andrei Alexandrescu]

Post by Christophe Travert
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

[Daniel Murphy]

"Andrei Alexandrescu" <SeeWebsiteForEmail at erdani.org> wrote in message

Post by Andrei Alexandrescu

Post by Christophe Travert
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; }
//...
}

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.

[Christophe Travert]

Post by Daniel Murphy
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.

[Daniel Murphy]

"Christophe Travert" <travert at phare.normalesup.org> wrote in message

Post by Christophe Travert

Post by Daniel Murphy
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.

Post by Christophe Travert
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.

[Christophe Travert]

Post by Daniel Murphy
"Christophe Travert" <travert at phare.normalesup.org> wrote in message

Post by Christophe Travert

Post by Daniel Murphy
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?

[Daniel Murphy]

"Christophe Travert" <travert at phare.normalesup.org> wrote in message

Post by Christophe Travert

Post by Daniel Murphy
"Christophe Travert" <travert at phare.normalesup.org> wrote in message

Post by Christophe Travert

Post by Daniel Murphy
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.

Post by Christophe Travert
I don't like makeRange much. Would you have a better name? smallRange?
rangeOf?

rangeit

[Andrei Alexandrescu]

"Christophe Travert"<travert at phare.normalesup.org> wrote in message

Post by Christophe Travert

Post by Daniel Murphy
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

[Jonathan M Davis]

Post by Andrei Alexandrescu

"Christophe Travert"<travert at phare.normalesup.org> wrote in message

Post by Christophe Travert

Post by Daniel Murphy
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

[Andrei Alexandrescu]

Post by Jonathan M Davis

Post by Andrei Alexandrescu
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

[Simen Kjaeraas]

On Tue, 10 Jul 2012 20:09:15 +0200, Andrei Alexandrescu

Post by Andrei Alexandrescu

Post by Jonathan M Davis

Post by Andrei Alexandrescu
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.

[Timon Gehr]

Post by Andrei Alexandrescu

Post by Jonathan M Davis

Post by Andrei Alexandrescu
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.

[Christophe Travert]

Post by Andrei Alexandrescu

Post by Christophe Travert
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; }
//...
}

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.

Post by Andrei Alexandrescu
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...

[Andrei Alexandrescu]

Post by Andrei Alexandrescu

Post by Andrei Alexandrescu
auto singletonRange(E)(E value)
{
return repeat(value).takeExactly(1);
}

auto singletonRange(E)(E value)
{
return repeat(value).takeOne;
}
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

[Christophe Travert]

Post by Andrei Alexandrescu

Post by Christophe Travert
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).

[Jonathan M Davis]

Post by Andrei Alexandrescu

Post by Andrei Alexandrescu

Post by Andrei Alexandrescu
auto singletonRange(E)(E value)
{
return repeat(value).takeExactly(1);
}

auto singletonRange(E)(E value)
{
return repeat(value).takeOne;
}
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

[Jacob Carlborg]

Post by Christophe Travert
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.

Post by Christophe Travert
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*.
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.

[Christophe Travert]

Post by Jacob Carlborg

Post by Christophe Travert
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.

[Andrei Alexandrescu]

Post by Jacob Carlborg

Post by Andrei Alexandrescu
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");
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.

Post by Jacob Carlborg

Post by Andrei Alexandrescu
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

[Jacob Carlborg]

Post by Andrei Alexandrescu
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.

Post by Andrei Alexandrescu
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?

Post by Andrei Alexandrescu
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.

[Daniel Murphy]

"Jacob Carlborg" <doob at me.com> wrote in message

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.

[Jacob Carlborg]

Post by Daniel Murphy
"Jacob Carlborg" <doob at me.com> wrote in message

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.

[Christophe Travert]

Post by Jacob Carlborg

Post by Daniel Murphy
"Jacob Carlborg" <doob at me.com> wrote in message

Can't "map" and "filter" return a random-access range if that's what they
receive?

map can, and does.

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;

[Daniel Murphy]

"Jacob Carlborg" <doob at me.com> wrote in message

Post by Jacob Carlborg

Post by Daniel Murphy
"Jacob Carlborg" <doob at me.com> wrote in message

Can't "map" and "filter" return a random-access range if that's what they
receive?

map can, and does.

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.

[Timon Gehr]

Post by Jacob Carlborg

Post by Andrei Alexandrescu
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.

Post by Andrei Alexandrescu
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?

[Andrei Alexandrescu]

Post by Jacob Carlborg
Can't "map" and "filter" return a random-access range if that's what
they receive?

(replied to by others)

Post by Jacob Carlborg

Post by Andrei Alexandrescu
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

[Dmitry Olshansky]

Post by H. S. Teoh

Post by Andrei Alexandrescu

Post by Jacob Carlborg

Post by Andrei Alexandrescu
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.

[Andrei Alexandrescu]

Post by H. S. Teoh

Post by Andrei Alexandrescu

Post by Jacob Carlborg

Post by Andrei Alexandrescu
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

[Jonathan M Davis]

Post by Andrei Alexandrescu

Post by Jacob Carlborg
auto str = ["foo", "bar"].map!(x => x);
auto f = str.sort();
http://pastebin.com/BeePWQk9

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

[Andrei Alexandrescu]

Post by Jonathan M Davis

Post by Andrei Alexandrescu

auto str = ["foo", "bar"].map!(x => x);
auto f = str.sort();
http://pastebin.com/BeePWQk9

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

[Jonathan M Davis]

Post by Jacob Carlborg
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
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");
http://pastebin.com/E4LV2UBE
auto str = ["foo", "bar"].map!(x => x);
auto f = str.sort();
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

[bearophile]

Post by 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);
}

Post by Jacob Carlborg
http://pastebin.com/E4LV2UBE
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

[Timon Gehr]

Post by bearophile

Post by 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.

Post by bearophile

Post by Jacob Carlborg
http://pastebin.com/E4LV2UBE
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.

[bearophile]

Post by Timon Gehr

Post by bearophile

Post by 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.

Post by Timon Gehr
-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.

Post by Timon Gehr
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

[Jonathan M Davis]

Post by Timon Gehr

Post by bearophile

Post by 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

[Timon Gehr]

Post by Jonathan M Davis

Post by Timon Gehr

Post by bearophile

Post by 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.

Post by Jonathan M Davis
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.

Post by Jonathan M Davis
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.

Post by Jonathan M Davis
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.

[Jonathan M Davis]

Post by Timon Gehr

Post by Jonathan M Davis
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

[Ali Çehreli]

Post by Timon Gehr

Post by Jonathan M Davis
dmd is generally good about not having
useless warnings.

case 0,1: // warning: switch fallthrough (nonsense)
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

[Timon Gehr]

Post by Ali Çehreli

Post by Timon Gehr

Post by Jonathan M Davis
dmd is generally good about not having
useless warnings.

case 0,1: // warning: switch fallthrough (nonsense)
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.

Post by Ali Çehreli
I get an error
void main()
{
int i;
int j;
switch (i) {
goto case; // goto, embraced by D :)
j = 42;
break;
j = 43;
}
}
Ali

The error only shows up if -w is used.

[Timon Gehr]

Post by Jonathan M Davis

Post by Timon Gehr

Post by Jonathan M Davis
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.

Post by Jonathan M Davis
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'.

Post by Jonathan M Davis
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.

Post by Jonathan M Davis
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 '()'.

Post by Jonathan M Davis
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.

Post by Jonathan M Davis
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.

Post by Jonathan M Davis
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.

[Jacob Carlborg]

Post by Timon Gehr
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.

[Dmitry Olshansky]

Post by Jacob Carlborg

Post by Timon Gehr
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?

[Jacob Carlborg]

Post by Dmitry Olshansky
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"]

[Dmitry Olshansky]

Post by Jacob Carlborg

Post by Dmitry Olshansky
Can you do it in other languages?

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.

Post by Jacob Carlborg
["3", "5", "6", "8"]

Please count the number of allocations in your paste of Ruby.

[Jacob Carlborg]

Post by Dmitry Olshansky
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.

Post by Dmitry Olshansky
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"]

[Nick Treleaven]

Post by Jacob Carlborg
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
["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

[Dmitry Olshansky]

Post by Nick Treleaven

Post by Jacob Carlborg
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
["3", "5", "5", "6", "8"]

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.

Post by Nick Treleaven
Maybe uniq should require a SortedRange?

+1

And say so explicitly in the docs.

[Jacob Carlborg]

Post by Dmitry Olshansky

Post by Nick Treleaven
Maybe uniq should require a SortedRange?

And say so explicitly in the docs.

Than it should be enforced with a constraint (if possible).

[Timon Gehr]

Post by Nick Treleaven

Post by Jacob Carlborg
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
["3", "5", "5", "6", "8"]

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.

[Jacob Carlborg]

Post by Nick Treleaven
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.

[Andrei Alexandrescu]

Post by Nick Treleaven

Post by Jacob Carlborg
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
["3", "5", "5", "6", "8"]

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

[Andrei Alexandrescu]

Post by Andrei Alexandrescu

Post by Nick Treleaven

Post by Jacob Carlborg
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
["3", "5", "5", "6", "8"]

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

[Jacob Carlborg]

Post by Andrei Alexandrescu
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.

[Timon Gehr]

Post by Jacob Carlborg

Post by Andrei Alexandrescu
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)

[Dmitry Olshansky]

Post by Jacob Carlborg

Post by Dmitry Olshansky
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

Post by Jacob Carlborg
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.

Post by Jacob Carlborg

Post by Dmitry Olshansky
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 ...

Post by Jacob Carlborg
a = [5, 3, 5, 6, 8]
a.uniq!
a.map!{ |e| e.to_s }
a.sort!
p a
["3", "5", "6", "8"]
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?

Post by Jacob Carlborg
writeln(a);
I'm guessing that's three allocations. But that doesn't even work, it
["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).

[Jacob Carlborg]

Post by Dmitry Olshansky
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.

Post by Dmitry Olshansky
Then you need something like transform. Anyway the result of map should
be sortable it's a bug.

Thank you for clearing that up.

Post by Dmitry Olshansky

Post by Jacob Carlborg

Post by Dmitry Olshansky
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 ...

Post by Jacob Carlborg
a = [5, 3, 5, 6, 8]
a.uniq!
a.map!{ |e| e.to_s }
a.sort!
p a
["3", "5", "6", "8"]
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.

Post by Dmitry Olshansky
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.

Post by Dmitry Olshansky
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.
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.

Post by Dmitry Olshansky
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.
"

Yes, exactly.

Post by Dmitry Olshansky
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?

[Dmitry Olshansky]

Post by Jacob Carlborg

Post by Dmitry Olshansky
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.

Post by Jacob Carlborg

Post by Dmitry Olshansky
Then you need something like transform. Anyway the result of map should
be sortable it's a bug.

Thank you for clearing that up.

Post by Dmitry Olshansky

Post by Jacob Carlborg
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.

Post by Jacob Carlborg

Post by Dmitry Olshansky
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.

Post by Jacob Carlborg

Post by Dmitry Olshansky
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.
auto a = [5, 3, 5, 6, 8].sort().uniq().map!(x => x.to!(string))();
fixed?

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.

Post by Jacob Carlborg

Post by Dmitry Olshansky
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.
"

Yes, exactly.

Post by Dmitry Olshansky
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.

[Jacob Carlborg]

Post by Dmitry Olshansky
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.

Post by Dmitry Olshansky
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.

Post by Dmitry Olshansky
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.

Post by Dmitry Olshansky
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.

[Jonathan M Davis]

Post by Jacob Carlborg

Post by Dmitry Olshansky
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.

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

[Andrei Alexandrescu]

Post by Jacob Carlborg

Post by Dmitry Olshansky
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".

Post by Jacob Carlborg
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.

Post by Jacob Carlborg
You see how stupid that is.

That being what?


Andrei

[Christophe Travert]

Post by Jacob Carlborg

Post by Dmitry Olshansky
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][]));

[Simen Kjaeraas]

Post by Jacob Carlborg

Post by Dmitry Olshansky
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.

Post by Jacob Carlborg

Post by Dmitry Olshansky
"
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.
"

Yes, exactly.

Post by Dmitry Olshansky
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.

[Timon Gehr]

Post by Dmitry Olshansky

Post by Jacob Carlborg

Post by Dmitry Olshansky
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

Post by Jacob Carlborg
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?

[Dmitry Olshansky]

Post by Timon Gehr

Post by Dmitry Olshansky

Post by Jacob Carlborg

Post by Dmitry Olshansky
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

Post by Jacob Carlborg
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!(...)).

[Christophe Travert]

Post by Dmitry Olshansky
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.

[Andrei Alexandrescu]

Post by Jacob Carlborg

Post by Dmitry Olshansky
Can you do it in other languages?

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

[Jonathan M Davis]

Post by Andrei Alexandrescu

Post by Jacob Carlborg

Post by Dmitry Olshansky
Can you do it in other languages?

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

[Andrei Alexandrescu]

Post by Jonathan M Davis

Post by Andrei Alexandrescu

Post by Jacob Carlborg

Post by Dmitry Olshansky
Can you do it in other languages?

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

[Jonathan M Davis]

Post by Jacob Carlborg

Post by Timon Gehr
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

[Jacob Carlborg]

Post by Jonathan M Davis
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?

[Timon Gehr]

Post by Jacob Carlborg

Post by Jonathan M Davis
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.

[Simen Kjaeraas]

Post by Jacob Carlborg

Post by Jonathan M Davis
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.

[Andrei Alexandrescu]

Post by Simen Kjaeraas
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

[Simen Kjaeraas]

On Tue, 10 Jul 2012 16:27:31 +0200, Andrei Alexandrescu

Post by Andrei Alexandrescu

Post by Simen Kjaeraas
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.

[Christophe Travert]

Post by Simen Kjaeraas

Post by Jacob Carlborg
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();

[Jonathan M Davis]

Post by Christophe Travert

Post by Simen Kjaeraas

Post by Jacob Carlborg
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();

It's not like

auto result = 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
range, so there's no point in adding eager versions. They'd just be
duplicating code for no real benefit. Not to mention, if anyone having to call
array on ranges all of the time, you should probably rethink how they're using
ranges. It's definitely necessary some of the time, but most of the time, you
can just operate on the lazy ranges and save yourself unnecessary allocations.

- Jonathan M Davis

[Simen Kjaeraas]

On Tue, 10 Jul 2012 17:21:14 +0200, Christophe Travert

Post by Christophe Travert

Post by Simen Kjaeraas

Post by Jacob Carlborg
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.

[Andrei Alexandrescu]

Post by Simen Kjaeraas
On Tue, 10 Jul 2012 17:21:14 +0200, Christophe Travert

Post by Christophe Travert

Post by Simen Kjaeraas

Post by Jacob Carlborg
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

[Andrei Alexandrescu]

Post by Jacob Carlborg
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

[Jacob Carlborg]

Post by Andrei Alexandrescu
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.

[Andrei Alexandrescu]

Post by Jacob Carlborg

Post by Andrei Alexandrescu
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."

Andrei

[Jonathan M Davis]

Post by Jacob Carlborg
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
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");
http://pastebin.com/E4LV2UBE
auto str = ["foo", "bar"].map!(x => x);
auto f = str.sort();
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

[Jacob Carlborg]

Post by Jonathan M Davis
http://d.puremagic.com/issues/show_bug.cgi?id=8367
http://d.puremagic.com/issues/show_bug.cgi?id=8368

Thanks.