July 10, 2012
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
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
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
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
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
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
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
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
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
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