July 10, 2012
On Tuesday, July 10, 2012 08:54:18 Jacob Carlborg wrote:
> On 2012-07-09 23:00, Timon Gehr wrote:
> > Actually you need a random-access range with assignable elements. Map would need to be provided with an inverse mapping to support that.
> > 
> > zip has assignable elements when the source ranges do.
> 
> Are you saying I can't sort a range that comes from "map"? To me it seems like std.algorithm and ranges are a complete failure.

It's a complete failure because not every range works with every range-based function? We have isInputRange, isForwardRange, isRandomAccessRange, hasSlicing, etc. for a reason. Different ranges have different capabilities, and different algorithms generate different types of ranges based on what they do. For instance, filter cannot possibly have slicing, because it's on O(n) operation to determine which elements match the predicate. You have to iterate through _all_ of the elements. Rather than doing that (and therefore not working with infinite ranges and being inefficient with non-infinite ranges), it's lazy, and if you _do_ want to process all of the elements to know filter's length and therefore make it slicable, you generate a new range from it - generally with std.array.array. map is in the same boat. It has to generate new range type, and the choice is between being lazy and efficient (and therefore require a call to array) or being inefficient and calling array internally.

- Jonathan M Davis
July 10, 2012
On Monday, July 09, 2012 22:09:54 Jacob Carlborg wrote:
> Almost every time I'm trying to use std.algorithm I run into some kind of error, for what seems to be fairly trivial and what one would expect to work. It feels like I'm constantly fighting with std.algorithm. For example:
> 
> import std.algorithm;
> import std.range;
> 
> struct Foo {}
> 
> auto f = Foo();
> auto foos = [f];
> auto foo = foos.map!(x => "foo");
> auto bar = foo.chain("bar");
> 
> This simple example result in the follow error:
> 
> http://pastebin.com/E4LV2UBE
> 
> Another example:
> 
> auto str = ["foo", "bar"].map!(x => x);
> auto f = str.sort();
> 
> Results in:
> 
> http://pastebin.com/BeePWQk9
> 
> I'm using DMD 2.059.

http://d.puremagic.com/issues/show_bug.cgi?id=8367 http://d.puremagic.com/issues/show_bug.cgi?id=8368

- Jonathan M Davis
July 10, 2012
On Monday, July 09, 2012 16:16:42 Andrei Alexandrescu wrote:
> > Another example:
> > 
> > auto str = ["foo", "bar"].map!(x => x);
> > auto f = str.sort();
> > 
> > Results in:
> > 
> > http://pastebin.com/BeePWQk9
> 
> The first error message is at clear as it goes:
> 
> Error: r[i2] is not an lvalue

It's only clear if you go look at sort's implementation, and that failure isn't even in sort itself! It's in its helper function, swapAt. Either sort's template constraint should fail when it's given a range that won't work with it, or it needs a static assertion which tells the programmer exactly what's wrong. The fact that r[i2] isn't an lvalue means nothing without actually digging into the code, which the average programmer should not have to do.

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

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

So it's basically what I said. Sine I want an array as the result of the operation I do need to convert it to an array again. For my need, it just seem to be more trouble to use std.algorithm.

-- 
/Jacob Carlborg
July 10, 2012
On 2012-07-10 08:59, Dmitry Olshansky wrote:

> Can you do it in other languages?

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

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

Prints:

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

-- 
/Jacob Carlborg
July 10, 2012
On 2012-07-10 09:09, Jonathan M Davis wrote:

> It's a complete failure because not every range works with every range-based
> function? We have isInputRange, isForwardRange, isRandomAccessRange,
> hasSlicing, etc. for a reason. Different ranges have different capabilities, and
> different algorithms generate different types of ranges based on what they do.
> For instance, filter cannot possibly have slicing, because it's on O(n)
> operation to determine which elements match the predicate. You have to iterate
> through _all_ of the elements. Rather than doing that (and therefore not
> working with infinite ranges and being inefficient with non-infinite ranges), it's
> lazy, and if you _do_ want to process all of the elements to know filter's
> length and therefore make it slicable, you generate a new range from it -
> generally with std.array.array. map is in the same boat. It has to generate
> new range type, and the choice is between being lazy and efficient (and
> therefore require a call to array) or being inefficient and calling array
> internally.

Well, I haven't been able to use a single function from std.algorithm without adding a lot of calls to "array" or "to!(string)". I think the things I'm trying to do seems trivial and quite common. I'm I overrating std.algorithm or does it not fit my needs?

-- 
/Jacob Carlborg
July 10, 2012
On 2012-07-10 09:25, Jonathan M Davis wrote:

> http://d.puremagic.com/issues/show_bug.cgi?id=8367
> http://d.puremagic.com/issues/show_bug.cgi?id=8368

Thanks.

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

and what type has the return of map ? Let me guess - array.
> Prints:
>
> ["3", "5", "6", "8"]
>
Please count the number of allocations in your paste of Ruby.

-- 
Dmitry Olshansky


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

If you consider it a problem to call array or to!string when you want
to get an array, then it does not fit your needs.
July 10, 2012
On 2012-07-10 12:05, Dmitry Olshansky wrote:

> and what type has the return of map ? Let me guess - array.

Yes, and that is what I _want_. I have no need for streaming data from the network into a linked list, filter it and then convert it to an array (or something similar). I want to start with an array and end with an array.

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

Probably four (if you count the initial allocation for the array literal). Plus a couple for the "to_s" method.

But I can use the same methods and modify the array in place instead:

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

Prints:

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

The corresponding D version would be:

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

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

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

-- 
/Jacob Carlborg
1 2 3 4 5 6 7 8 9 10 11 12 13
Top | Discussion index | About this forum | D home