View mode: basic / threaded / horizontal-split · Log in · Help
July 10, 2012
Re: Why is std.algorithm so complicated to use?
On Tue, 10 Jul 2012 09:04:31 +0200, Jonathan M Davis <jmdavisProg@gmx.com>  
wrote:

> The problem is that map is lazy, so it can't be a random access range,

Sure it can. If the underlying range is random-access or bidirectional,
so can map be. What can't be (as easily) done is caching of elements.

--

Simen
July 10, 2012
Re: Why is std.algorithm so complicated to use?
On 10/07/2012 12:37, Jacob Carlborg wrote:
> The corresponding D version would be:
>
> auto a = [5, 3, 5, 6, 8].uniq.map!(x => x.to!(string)).array.sort.array;
> writeln(a);
>
> I'm guessing that's three allocations. But that doesn't even work, it
> prints:
>
> ["3", "5", "5", "6", "8"]

uniq needs sorted input:

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

Tested with dmd 2.059.
I think the above should be one allocation (except for the strings).

Maybe uniq should require a SortedRange?

Nick
July 10, 2012
Re: Why is std.algorithm so complicated to use?
On Tue, 10 Jul 2012 11:41:02 +0200, Jacob Carlborg <doob@me.com> wrote:

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

bearophile (who else? :p) has suggested the addition of eager and in-place
versions of some ranges, and I think he has a very good point.

-- 
Simen
July 10, 2012
Re: Why is std.algorithm so complicated to use?
On 10-Jul-12 15:37, Jacob Carlborg wrote:
> On 2012-07-10 12:05, Dmitry Olshansky wrote:
>
>> and what type has the return of map ? Let me guess - array.
>
> Yes, and that is what I _want_.

Too bad, as there is no need to make an array when you map something.

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

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

>> Please count the number of allocations in your paste of Ruby.
>
> Probably four (if you count the initial allocation for the array
> literal). Plus a couple for the "to_s" method.
>

Now scale the problem to at least ~ 10^6 ...

> But I can use the same methods and modify the array in place instead:
>
> a = [5, 3, 5, 6, 8]
> a.uniq!
> a.map!{ |e| e.to_s }
> a.sort!
> p a
>
> Prints:
>
> ["3", "5", "6", "8"]
>
> The corresponding D version would be:
>
> auto a = [5, 3, 5, 6, 8].uniq.map!(x => x.to!(string)).array.sort.array;

The last array is unnecessary as sort is in-place.
Also why would you not sort before map? It'd be faster this way as it's 
sorting integers.

Thus it's only 2 and one of them is literal. The map can't be sorted 
because uniq produces lazy bidirectional range. Thus you turn it into 
array as simple as that.

My version would be:

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

fixed?

> writeln(a);
>
> I'm guessing that's three allocations. But that doesn't even work, it
> prints:
>
> ["3", "5", "5", "6", "8"]

Because uniq work only on sorted ranges? Have you tried reading docs?
"
Iterates unique consecutive elements of the given range (functionality 
akin to the uniq system utility). Equivalence of elements is assessed by 
using the predicate pred, by default "a == b". If the given range is 
bidirectional, uniq also yields a bidirectional range.
"
Though it doesn't explicitly mentions it, the example is:

int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ];
assert(equal(uniq(arr), [ 1, 2, 3, 4, 5 ][]));

And it's a general knowledge that you can't run uniq in reasonable speed 
on unsorted sequence. (it'd take O(N^2) which is worse then sorting and 
then doing unique).

-- 
Dmitry Olshansky
July 10, 2012
Re: Why is std.algorithm so complicated to use?
On 10-Jul-12 16:50, Nick Treleaven wrote:
> On 10/07/2012 12:37, Jacob Carlborg wrote:
>> The corresponding D version would be:
>>
>> auto a = [5, 3, 5, 6, 8].uniq.map!(x => x.to!(string)).array.sort.array;
>> writeln(a);
>>
>> I'm guessing that's three allocations. But that doesn't even work, it
>> prints:
>>
>> ["3", "5", "5", "6", "8"]
>
> uniq needs sorted input:
>
> auto r = [5, 3, 5, 6, 8].sort.uniq.map!(x => x.to!string);
> writeln(r);
>
> Tested with dmd 2.059.
> I think the above should be one allocation (except for the strings).

Yup and that was my whole point.
You get fast and easy way with D
or just very easy way with any suitable scripting language.

>
> Maybe uniq should require a SortedRange?
>

+1

And say so explicitly in the docs.


-- 
Dmitry Olshansky
July 10, 2012
Re: Why is std.algorithm so complicated to use?
On 07/10/2012 02:50 PM, Nick Treleaven wrote:
> On 10/07/2012 12:37, Jacob Carlborg wrote:
>> The corresponding D version would be:
>>
>> auto a = [5, 3, 5, 6, 8].uniq.map!(x => x.to!(string)).array.sort.array;
>> writeln(a);
>>
>> I'm guessing that's three allocations. But that doesn't even work, it
>> prints:
>>
>> ["3", "5", "5", "6", "8"]
>
> uniq needs sorted input:
>
> auto r = [5, 3, 5, 6, 8].sort.uniq.map!(x => x.to!string);
> writeln(r);
>
> Tested with dmd 2.059.
> I think the above should be one allocation (except for the strings).
>
> Maybe uniq should require a SortedRange?
>
> Nick
>
>

uniq provides useful functionality even if the input is not sorted.
July 10, 2012
Re: Why is std.algorithm so complicated to use?
On 7/10/12 2:50 AM, Jacob Carlborg wrote:
> On 2012-07-09 22:16, Andrei Alexandrescu wrote:
>
>> So foo is a range of strings, because each element of it is a string.
>> Then you want to chain a range of strings with a string, which is a
>> range of dchar. That doesn't work, and I agree the error message should
>> be more informative.
>
> Is that by design or something that can be fixed?

We can arrange things in the library that a custom message is issued, or 
in the compiler to do it once for all. At any rate whenever there's an 
error pointing somewhere in the library's code that's an insufficient 
template constraint that should be fixed.

>> To fix the example, write
>>
>> auto bar = foo.chain(["bar"]);
>
> I think that's an ugly workaround.

Well I made minimal changes. Besides I don't know what the intent is.

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

To the extent any of us is somewhat nuts, yes, I am. I'm also a fan of 
civil conversation.

> It's an insanly bad error message,
> I have no "r" in my code. Is it too much to ask to be able to sort a range?

Indeed I agree there should be no error in library code. What I meant to 
say was, when I saw the code I thought "I bet this is an lvalue thing", 
and then when I saw lvalue in the error I was satisfied.

> This just proves that std.algorithm is complicated to use. It's very
> unintuitive.
>
> What I really want is this, but ranges doesn't work like that:
>
> Foo f = Foo();
> Foo[] foos = [f];
> string[] = foos.map!(x => "foo");
> string[] bar = foo ~= "foo";

I understand. So you need to use array() to convert the lazy map result 
into an eager array. I disagree this is unintuitive, if it were then 
very little of D would make sense are lazy, non-array ranges are everywhere.

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

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


Andrei
July 10, 2012
Re: Why is std.algorithm so complicated to use?
On 7/10/12 3:48 AM, Jonathan M Davis wrote:
> On Monday, July 09, 2012 16:16:42 Andrei Alexandrescu wrote:
>>> Another example:
>>>
>>> auto str = ["foo", "bar"].map!(x =>  x);
>>> auto f = str.sort();
>>>
>>> Results in:
>>>
>>> http://pastebin.com/BeePWQk9
>>
>> The first error message is at clear as it goes:
>>
>> Error: r[i2] is not an lvalue
>
> It's only clear if you go look at sort's implementation, and that failure
> isn't even in sort itself! It's in its helper function, swapAt. Either sort's
> template constraint should fail when it's given a range that won't work with
> it, or it needs a static assertion which tells the programmer exactly what's
> wrong. The fact that r[i2] isn't an lvalue means nothing without actually
> digging into the code, which the average programmer should not have to do.

Agreed, thanks for the bug reports.

Andrei
July 10, 2012
Re: Why is std.algorithm so complicated to use?
On 2012-07-10 15:28, Andrei Alexandrescu wrote:

> We can arrange things in the library that a custom message is issued, or
> in the compiler to do it once for all. At any rate whenever there's an
> error pointing somewhere in the library's code that's an insufficient
> template constraint that should be fixed.

I mean, is it possible to have the original code work?

auto bar = foo.chain("bar");

Or perhaps more appropriate:

auto bar = foo.append("bar");


> Well I made minimal changes. Besides I don't know what the intent is.

Have a look at this:

https://github.com/jacob-carlborg/dstep/blob/master/dstep/translator/Translator.d#L217

I was going to replace the foreach-loop in the above code with a call to 
"map". But "map" returns a range, not an array. Therefor the append at 
line 245 won't work. How would I do line 245 if "params" is a range 
returned by "map"?

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

> Indeed I agree there should be no error in library code. What I meant to
> say was, when I saw the code I thought "I bet this is an lvalue thing",
> and then when I saw lvalue in the error I was satisfied.

Jonathan has already reported these two bugs.

> I understand. So you need to use array() to convert the lazy map result
> into an eager array. I disagree this is unintuitive, if it were then
> very little of D would make sense are lazy, non-array ranges are
> everywhere.

Tell me what is the point of std.algorithm and ranges if I have to 
convert every single result of an algorithm to an array before I can use 
it with an other algorithm? I thought the whole idea was to avoid 
allocations between different usages of algorithms.

-- 
/Jacob Carlborg
July 10, 2012
Re: Why is std.algorithm so complicated to use?
On 2012-07-10 14:55, Dmitry Olshansky wrote:

>> Maybe uniq should require a SortedRange?
> And say so explicitly in the docs.

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

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