On Tue, Jul 10, 2012 at 09:28:51AM -0400, Andrei Alexandrescu wrote:
> On 7/10/12 2:50 AM, Jacob Carlborg wrote:
> >On 2012-07-09 22:16, Andrei Alexandrescu wrote:
> >
> >>So foo is a range of strings, because each element of it is a string.  Then you want to chain a range of strings with a string, which is a range of dchar. That doesn't work, and I agree the error message should be more informative.
> >
> >Is that by design or something that can be fixed?
> 
> We can arrange things in the library that a custom message is issued, or in the compiler to do it once for all.

Please don't do it in the compiler. Custom messages should be in the library. Tying the compiler to phobos is a bad idea; druntime should be the only dependency.


> At any rate whenever there's an error pointing somewhere in the library's code that's an insufficient template constraint that should be fixed.
[...]

Yes.


T

-- 
Having a smoking section in a restaurant is like having a peeing section in a swimming pool. -- Edward Burr

On 2012-07-10 14:50, Nick Treleaven wrote:

> uniq needs sorted input:
>
> auto r = [5, 3, 5, 6, 8].sort.uniq.map!(x => x.to!string);
> writeln(r);
>
> Tested with dmd 2.059.
> I think the above should be one allocation (except for the strings).

But I want the result to be an array, which would require an additional allocation.

-- 
/Jacob Carlborg

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

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

How do you store your ranges in a struct or class? Most of them are voldemort types.

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

Thank you for clearing that up.

>>> Please count the number of allocations in your paste of Ruby.
>>
>> Probably four (if you count the initial allocation for the array
>> literal). Plus a couple for the "to_s" method.
>>
>
> Now scale the problem to at least ~ 10^6 ...
>
>> But I can use the same methods and modify the array in place instead:
>>
>> a = [5, 3, 5, 6, 8]
>> a.uniq!
>> a.map!{ |e| e.to_s }
>> a.sort!
>> p a
>>
>> Prints:
>>
>> ["3", "5", "6", "8"]
>>
>> The corresponding D version would be:
>>
>> auto a = [5, 3, 5, 6, 8].uniq.map!(x => x.to!(string)).array.sort.array;



> The last array is unnecessary as sort is in-place.

Again, I want an array, not a range.

> Also why would you not sort before map? It'd be faster this way as it's
> sorting integers.

Isn't it obvious that is just an example and not real code. I'm trying to keep the code as short as possible here.

> Thus it's only 2 and one of them is literal. The map can't be sorted
> because uniq produces lazy bidirectional range. Thus you turn it into
> array as simple as that.
>
> My version would be:
>
> auto a = [5, 3, 5, 6, 8].sort().uniq().map!(x => x.to!(string))();
>
> fixed?

Still need an array. Real code:

https://github.com/jacob-carlborg/dstep/blob/master/dstep/translator/IncludeHandler.d#L124

I want the end result to be sorted.

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

Yes, exactly.

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

How should I know that from the example?

-- 
/Jacob Carlborg

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

This is very inefficient.

I agree that if efficiency wasn't a concern for std.algorithm, its API would have been different. As things are, I think std.algorithm strikes a very good balance between efficiency and usability.


Andrei

On 7/10/12 5:41 AM, Jacob Carlborg wrote:
> Well, I haven't been able to use a single function from std.algorithm
> without adding a lot of calls to "array" or "to!(string)". I think the
> things I'm trying to do seems trivial and quite common. I'm I overrating
> std.algorithm or does it not fit my needs?

It may be the case you're trying to write ruby in D. I rarely need to convert stuff to arrays.

Andrei

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

Indeed map currently maps random-access ranges to random-access ranges.

Andrei

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

Yes, please file a bug. Thanks!

Andrei

On 7/10/12 8:52 AM, Simen Kjaeraas wrote:
> bearophile (who else? :p) has suggested the addition of eager and in-place
> versions of some ranges, and I think he has a very good point.

Where would good old loops not work for eager stuff?

Andrei

On 10-Jul-12 18:15, Jacob Carlborg wrote:
> On 2012-07-10 14:53, Dmitry Olshansky wrote:
>
>> Too bad, as there is no need to make an array when you map something.
>
> How do you store your ranges in a struct or class? Most of them are
> voldemort types.
>

typeof to the rescue. In fact I'm not so proud of voldemort types. As when you need to sotre range somewhere they stand in your way for no benefit.

>> Then you need something like transform. Anyway the result of map should
>> be sortable it's a bug.
>
> Thank you for clearing that up.
>

>>> The corresponding D version would be:
>>>
>>> auto a = [5, 3, 5, 6, 8].uniq.map!(x => x.to!(string)).array.sort.array;
>
>
>
>> The last array is unnecessary as sort is in-place.
>
> Again, I want an array, not a range.

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

Just use the same array, it's just that sort returns a wrapper around array (or other range) that indicates it's sorted by predicate x. It can then help to reuse this information e.g. to perforam binary search etc.

>
>> Also why would you not sort before map? It'd be faster this way as it's
>> sorting integers.
>
> Isn't it obvious that is just an example and not real code. I'm trying
> to keep the code as short as possible here.
>
Sorry, it wasn't.

>> Thus it's only 2 and one of them is literal. The map can't be sorted
>> because uniq produces lazy bidirectional range. Thus you turn it into
>> array as simple as that.
>>
>> My version would be:
>>
>> auto a = [5, 3, 5, 6, 8].sort().uniq().map!(x => x.to!(string))();
>>
>> fixed?
>
> Still need an array. Real code:
>
> https://github.com/jacob-carlborg/dstep/blob/master/dstep/translator/IncludeHandler.d#L124
>
>
> I want the end result to be sorted.

Just take an array and call sort on it like in the old days. I don't think that stuffing it into one liner is required.
Again if you need an array just call array at the end that's how it's supposed to be.

>> Because uniq work only on sorted ranges? Have you tried reading docs?
>> "
>> Iterates unique consecutive elements of the given range (functionality
>> akin to the uniq system utility). Equivalence of elements is assessed by
>> using the predicate pred, by default "a == b". If the given range is
>> bidirectional, uniq also yields a bidirectional range.
>> "
>> Though it doesn't explicitly mentions it, the example is:
>
> Yes, exactly.
>
>> int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ];
>> assert(equal(uniq(arr), [ 1, 2, 3, 4, 5 ][]));
>
> How should I know that from the example?
>
Dunno, to me it says SORTED in one big scary thought. Again it should ether check constraint or put some more useful description. e.g.
"(functionality akin to the uniq system utility)" doesn't strike me as helpful.

-- 
Dmitry Olshansky

On 10-Jul-12 17:56, Jacob Carlborg wrote:
> On 2012-07-10 15:28, Andrei Alexandrescu wrote:
>
>> We can arrange things in the library that a custom message is issued, or
>> in the compiler to do it once for all. At any rate whenever there's an
>> error pointing somewhere in the library's code that's an insufficient
>> template constraint that should be fixed.
>
> I mean, is it possible to have the original code work?
>
> auto bar = foo.chain("bar");
>
> Or perhaps more appropriate:
>
> auto bar = foo.append("bar");
>
>
>> Well I made minimal changes. Besides I don't know what the intent is.
>
> Have a look at this:
>
> https://github.com/jacob-carlborg/dstep/blob/master/dstep/translator/Translator.d#L217
>
>

I'm not sure how map can fit there. If anything you need a foreach (and you have it;) ) to build a _string_. I'd rather output ',' right there inside of loop. Thus avoiding costly join and appending to a new buffer on each iteration.

Other then doing it with Appender and generalizing to any OutputRange I fail to see a problem.

> I was going to replace the foreach-loop in the above code with a call to
> "map". But "map" returns a range, not an array. Therefor the append at
> line 245 won't work. How would I do line 245 if "params" is a range
> returned by "map"?
>
> It seems unnecessary to have to convert the range to an array before
> "join" is called on line 247.
>
>> Indeed I agree there should be no error in library code. What I meant to
>> say was, when I saw the code I thought "I bet this is an lvalue thing",
>> and then when I saw lvalue in the error I was satisfied.
>
> Jonathan has already reported these two bugs.
>
>> I understand. So you need to use array() to convert the lazy map result
>> into an eager array. I disagree this is unintuitive, if it were then
>> very little of D would make sense are lazy, non-array ranges are
>> everywhere.
>
> Tell me what is the point of std.algorithm and ranges if I have to
> convert every single result of an algorithm to an array before I can use
> it with an other algorithm? I thought the whole idea was to avoid
> allocations between different usages of algorithms.
>
Speed and generality. Think removing temporary arrays. And while a lot of folks won't every use things other then arrays power users sure as hell would.

-- 
Dmitry Olshansky