View mode: basic / threaded / horizontal-split · Log in · Help
July 10, 2012
Re: Why is std.algorithm so complicated to use?
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
Re: Why is std.algorithm so complicated to use?
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
Re: Why is std.algorithm so complicated to use?
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
Re: Why is std.algorithm so complicated to use?
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
Re: Why is std.algorithm so complicated to use?
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
Re: Why is std.algorithm so complicated to use?
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
Re: Why is std.algorithm so complicated to use?
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
Re: Why is std.algorithm so complicated to use?
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
Re: Why is std.algorithm so complicated to use?
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
Re: Why is std.algorithm so complicated to use?
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
Top | Discussion index | About this forum | D home