Re: Why is std.algorithm so complicated to use?
On Tuesday, July 17, 2012 11:47:07 Christophe Travert wrote: > The compiler could stop displaying at about 10 failed constrains and > claim there are more. It would be best if it could figure out what are > the 10 most interesting constrains, but that may not be easy! That seems like a good idea. - Jonathan M Davis
Re: Why is std.algorithm so complicated to use?
Jonathan M Davis , dans le message (digitalmars.D:172564), a écrit :
> They're likely to contain a lot of stuff negation of other template
> constraints. For instance,
>
> auto func(R)(R range)
> if(isForwardRange!R && !isBidirectionalRange!R)
> {}
>
> auto func(R)(R range)
> if(isBidirectionalRange!R)
> {}
>
> If you have a function with very many overloads, it can be very easy to end
> up
> with a bunch of different template constraints which are all slightly
> different.
> std.algorithm.find is a prime example of this.
>
> But as much as it may be a bit overwhelming to print every failed constraint,
> without doing that, you _have_ to go to the source code to see what they
> were,
> which isn't all that great (especially if it's not in a library that you
> wrote
> and don't normally look at the source of - e.g. Phobos).
>
> On the other hand, a failed instantiation of std.conv.to would print out
> reams
> of failed constraints...
The compiler could stop displaying at about 10 failed constrains and
claim there are more. It would be best if it could figure out what are
the 10 most interesting constrains, but that may not be easy!
Then it's up to the programmer to use template constrains, static if and
eventually pragma, to allow the compiler to display pleasant error
messages. The langage could help you by allowing you to make hiearchized
template constrains, but static if is a fine solution most of the time.
Re: Why is std.algorithm so complicated to use?
On Monday, July 16, 2012 22:53:36 Timon Gehr wrote:
> On 07/16/2012 05:22 PM, Don Clugston wrote:
> > On 10/07/12 16:59, Andrei Alexandrescu wrote:
> >> On 7/10/12 9:59 AM, H. S. Teoh wrote:
> >>> 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.
> >>
> >> The idea there being that the compiler could give good details about
> >> what part of a complex constraint has failed.
> >
> > However the compiler doesn't know which constraint was supposed to pass.
> > If it is lucky enough to only have one template, it can do it, but if it
> > has:
> > template1 if (A && B)
> > template2 if (C && D)
> > template3 if ( (E || F) && G)
> >
> > should it print:
> > foo.d(99): Error: no matching template
> > foo.d(10): constraint failed: A
> > foo.d(28): constraint failed: D
> > foo.d(57): constraint failed: (E || F)
> > ?
> > Could be a very long list, if there are many templates.
> >
> > Determining the minimal list of constraints seems like a nice
> > application for BDDs...
>
> Well, are template constraints likely to contain a lot of redundant
> information?
They're likely to contain a lot of stuff negation of other template
constraints. For instance,
auto func(R)(R range)
if(isForwardRange!R && !isBidirectionalRange!R)
{}
auto func(R)(R range)
if(isBidirectionalRange!R)
{}
If you have a function with very many overloads, it can be very easy to end up
with a bunch of different template constraints which are all slightly
different.
std.algorithm.find is a prime example of this.
But as much as it may be a bit overwhelming to print every failed constraint,
without doing that, you _have_ to go to the source code to see what they were,
which isn't all that great (especially if it's not in a library that you wrote
and don't normally look at the source of - e.g. Phobos).
On the other hand, a failed instantiation of std.conv.to would print out reams
of failed constraints...
Getting the compiler to print out the constraints come out to if combined
could be very useful, but in some ways, it would be worse, since it would
generally result in one big constraint with a bunch of ||s between them -
particularly since it can't understand how the various templates involved work
(e.g. isForwardRange vs isBidirectionalRange). I've considered taking up the
practice of putting all template function overloads inside of a single
template which has a constraint for them all (with each individual function
still having its own of course). The programmer would likely do a better job
at simplifying it than the compiler, but often you can't do that, especially
when different overloads require drastically different stuff (e.g. the
constraints on needle often depend on the constraints on haystack for find).
So, in a lot of cases, you'd just end up with a really nasty looking and hard
to understand template constraint.
If it weren't for the case of std.conv, I'd argue for just displaying all of
the failed constraints, but I don't know.
- Jonathan M Davis
Re: Why is std.algorithm so complicated to use?
On 07/16/2012 05:22 PM, Don Clugston wrote: On 10/07/12 16:59, Andrei Alexandrescu wrote: On 7/10/12 9:59 AM, H. S. Teoh wrote: 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. The idea there being that the compiler could give good details about what part of a complex constraint has failed. However the compiler doesn't know which constraint was supposed to pass. If it is lucky enough to only have one template, it can do it, but if it has: template1 if (A && B) template2 if (C && D) template3 if ( (E || F) && G) should it print: foo.d(99): Error: no matching template foo.d(10): constraint failed: A foo.d(28): constraint failed: D foo.d(57): constraint failed: (E || F) ? Could be a very long list, if there are many templates. Determining the minimal list of constraints seems like a nice application for BDDs... Well, are template constraints likely to contain a lot of redundant information?
Re: Why is std.algorithm so complicated to use?
On 10/07/12 16:59, Andrei Alexandrescu wrote: On 7/10/12 9:59 AM, H. S. Teoh wrote: 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. The idea there being that the compiler could give good details about what part of a complex constraint has failed. However the compiler doesn't know which constraint was supposed to pass. If it is lucky enough to only have one template, it can do it, but if it has: template1 if (A && B) template2 if (C && D) template3 if ( (E || F) && G) should it print: foo.d(99): Error: no matching template foo.d(10):constraint failed: A foo.d(28):constraint failed: D foo.d(57):constraint failed: (E || F) ? Could be a very long list, if there are many templates. Determining the minimal list of constraints seems like a nice application for BDDs...
Re: Why is std.algorithm so complicated to use?
On Monday, July 16, 2012 10:08:11 Jacob Carlborg wrote: > Just _because_ of how "remove" works in std.algorithm and "erase" in > C++, I though "sort" behaved similar. Well, it does in that it sorts in place and returns the result, but the result and the original are more in line with one another then they are with remove, since they're both sorted rather than having their lengths differ like they do with remove (though the result of sort is usually a different type from the original range, unlike with remove). But I don't dispute that the documentation needs improvement. It probably does. I haven't read through much of it recently, and in many cases, I probably already fully understand it anyway, so I'm not a good judge of how good it is. - Jonathan M Davis
Re: Why is std.algorithm so complicated to use?
On 2012-07-16 09:18, Jonathan M Davis wrote: We do have InPlace in function names when one version of a function operates in place and another doesn't, but we haven't generally done that on functions which only have one version, and I don't expect that to change now (at least not for existing functions). Yes, that's good. But we can always add that to the documentation. There can also be some general documentation about this on the top of the std.algorithm module. Something like: "No function operates in place unless it explicitly says so in the documentation or if its name has the 'inPlace' suffix." In any case, _most_ range-based functions _don't_ operate in place, but it's certainly true that the ones that do should make that clear in their documentation. remove is a bit of a special case, however, in that it does the changes in place but doesn't take a ref, so while the return value is shortened to not include the removed elements, the original is just as long as it was before (which is useful in cases where you want to then set the elements at the end), and you end up with something that's sort of in place and sort of not. Regardless, remove is confusing enough to most people (just like erase in C++) that it's documentation needs to be very clear, but I don't know how good it is or isn't. Given the difficulty of explaining it properly and Merhdad's confusion, it probably stands to be improved. Just _because_ of how "remove" works in std.algorithm and "erase" in C++, I though "sort" behaved similar. -- /Jacob Carlborg
Re: Why is std.algorithm so complicated to use?
On Monday, July 16, 2012 09:07:06 Jacob Carlborg wrote: > On 2012-07-16 00:03, Jonathan M Davis wrote: > > Iterators have exactly the same problem for exactly the same reasons as > > std.algorithm.remove (e.g. take a look at C++'s erase function). The only > > way to do this in place would be to create a separate removeInPlace > > function specifically for arrays. But since all it takes is reassigning > > the result of std.algorithm.remove to the array that you passed in and an > > std.array.replaceInPlace would be doing exactly that, I don't think that > > > > adding such a function buys us much: > > auto arr = [10, 22, 19, 4, 6]; > > arr = remove(arr, 3); > > assert(arr == [10, 22, 19, 6]); > > > > The main problem is understanding why remove (or erase in C++) works this > > way, which seems to throw off a bunch of people in both D and C++, but > > it's something that we're pretty much stuck with. You need the actual > > container (not an iterator or range) if you want to actually remove the > > element. > It would be really useful if std.algorithm (and similar functions) would > indicate clearly if they operate in place or not. It took me a while to > understand that "sort" operates in place. In Ruby this is achieved by a > naming convention: > > a = [3, 4, 5] > a = a.sort # returns a new array > a.sort! # sorts in place We do have InPlace in function names when one version of a function operates in place and another doesn't, but we haven't generally done that on functions which only have one version, and I don't expect that to change now (at least not for existing functions). In any case, _most_ range-based functions _don't_ operate in place, but it's certainly true that the ones that do should make that clear in their documentation. remove is a bit of a special case, however, in that it does the changes in place but doesn't take a ref, so while the return value is shortened to not include the removed elements, the original is just as long as it was before (which is useful in cases where you want to then set the elements at the end), and you end up with something that's sort of in place and sort of not. Regardless, remove is confusing enough to most people (just like erase in C++) that it's documentation needs to be very clear, but I don't know how good it is or isn't. Given the difficulty of explaining it properly and Merhdad's confusion, it probably stands to be improved. - Jonathan M Davis
Re: Why is std.algorithm so complicated to use?
On 2012-07-16 00:03, Jonathan M Davis wrote: Iterators have exactly the same problem for exactly the same reasons as std.algorithm.remove (e.g. take a look at C++'s erase function). The only way to do this in place would be to create a separate removeInPlace function specifically for arrays. But since all it takes is reassigning the result of std.algorithm.remove to the array that you passed in and an std.array.replaceInPlace would be doing exactly that, I don't think that adding such a function buys us much: auto arr = [10, 22, 19, 4, 6]; arr = remove(arr, 3); assert(arr == [10, 22, 19, 6]); The main problem is understanding why remove (or erase in C++) works this way, which seems to throw off a bunch of people in both D and C++, but it's something that we're pretty much stuck with. You need the actual container (not an iterator or range) if you want to actually remove the element. It would be really useful if std.algorithm (and similar functions) would indicate clearly if they operate in place or not. It took me a while to understand that "sort" operates in place. In Ruby this is achieved by a naming convention: a = [3, 4, 5] a = a.sort # returns a new array a.sort! # sorts in place -- /Jacob Carlborg
Re: Why is std.algorithm so complicated to use?
On Monday, July 16, 2012 01:47:15 Mehrdad wrote: > On Sunday, 15 July 2012 at 22:39:47 UTC, Jonathan M Davis wrote: > > On Sunday, July 15, 2012 18:24:47 Andrei Alexandrescu wrote: > >> On 7/15/12 6:22 PM, Mehrdad wrote: > >> > On Sunday, 15 July 2012 at 22:03:33 UTC, Jonathan M Davis > >> > > >> > wrote: > >> >> auto arr = [10, 22, 19, 4, 6]; > >> >> arr = remove(arr, 3); > >> >> assert(arr == [10, 22, 19, 6]); > >> > > >> > Yeah, the problem is that this reallocates... > >> > >> doesn't > > > > Yeah. It just slices. > > Ooh, I misunderstood what was happening. Thanks to both you & > Andrei! std.algorithm.remove does pretty much exactly what the STL's erase function does, only it operates on ranges rather than iterators. - Jonathan M Davis
Re: Why is std.algorithm so complicated to use?
On Sunday, 15 July 2012 at 22:39:47 UTC, Jonathan M Davis wrote: On Sunday, July 15, 2012 18:24:47 Andrei Alexandrescu wrote: On 7/15/12 6:22 PM, Mehrdad wrote: > On Sunday, 15 July 2012 at 22:03:33 UTC, Jonathan M Davis > wrote: >> auto arr = [10, 22, 19, 4, 6]; >> arr = remove(arr, 3); >> assert(arr == [10, 22, 19, 6]); > > Yeah, the problem is that this reallocates... doesn't Yeah. It just slices. Ooh, I misunderstood what was happening. Thanks to both you & Andrei!
Re: Why is std.algorithm so complicated to use?
On Sunday, July 15, 2012 18:24:47 Andrei Alexandrescu wrote: > On 7/15/12 6:22 PM, Mehrdad wrote: > > On Sunday, 15 July 2012 at 22:03:33 UTC, Jonathan M Davis wrote: > >> auto arr = [10, 22, 19, 4, 6]; > >> arr = remove(arr, 3); > >> assert(arr == [10, 22, 19, 6]); > > > > Yeah, the problem is that this reallocates... > > doesn't Yeah. It just slices. remove moves the elements over by one, and returns a slice of the range which is shorter by the number of elements removed. And since assigning one array is just assigning the ptr and length properties, there's no copying of the elements there, and no reallocations are required anywhere. Now, if you want to append to the array afterwards, then you're going to get a reallocation (unless you know that there are no other arrays referring to anything after the returned slice, in which case, you can use assumeSafeAppend make it so that it doesn't reallocate). But the removal involves no reallocations at all. - Jonathan M Davis
Re: Why is std.algorithm so complicated to use?
On 7/15/12 6:22 PM, Mehrdad wrote: On Sunday, 15 July 2012 at 22:03:33 UTC, Jonathan M Davis wrote: auto arr = [10, 22, 19, 4, 6]; arr = remove(arr, 3); assert(arr == [10, 22, 19, 6]); Yeah, the problem is that this reallocates... doesn't
Re: Why is std.algorithm so complicated to use?
On 7/15/12 5:42 PM, Mehrdad wrote: Another example of how std.algorithm is so hard to use (it's almost tempting me to start swearing...): How do you remove an item from an array in place? It seems so darn simple, and yet it's not in std.algorithm (or std.range). It makes something so easy so tedious. Look for "remove" here: http://dlang.org/phobos/std_algorithm.html Unfortunately the anchor called "remove" is swallowed by an unrelated enum value (we should fix that in ddoc). From the example: int[] a = [ 3, 5, 7, 8 ]; assert(remove(a, 1) == [ 3, 7, 8 ]); assert(a == [ 3, 7, 8, 8 ]); Therefore, to remove an element in place: int[] a = [ 3, 5, 7, 8 ]; a = remove(a, 1); You also have a less stable but faster version: a = remove!(SwapStrategy.unstable)(a, 1); Andrei
Re: Why is std.algorithm so complicated to use?
On Sunday, 15 July 2012 at 22:03:33 UTC, Jonathan M Davis wrote: auto arr = [10, 22, 19, 4, 6]; arr = remove(arr, 3); assert(arr == [10, 22, 19, 6]); Yeah, the problem is that this reallocates... (not claiming remove() itself is supposed to be efficient, but this is making it even worse) The main problem is understanding why remove (or erase in C++) works this way, which seems to throw off a bunch of people in both D and C++, but it's something that we're pretty much stuck with. You need the actual container (not an iterator or range) if you want to actually remove the element. Well, for arrays, the "actual container" is the array, so that doesn't work either. :\ On the other hand, even C++ has vector::erase()!
Re: Why is std.algorithm so complicated to use?
On Sunday, July 15, 2012 23:42:29 Mehrdad wrote: > Another example of how std.algorithm is so hard to use (it's > almost tempting me to start swearing...): > > How do you remove an item from an array in place? > > It seems so darn simple, and yet it's not in std.algorithm (or > std.range). It makes something so easy so tedious. Iterators have exactly the same problem for exactly the same reasons as std.algorithm.remove (e.g. take a look at C++'s erase function). The only way to do this in place would be to create a separate removeInPlace function specifically for arrays. But since all it takes is reassigning the result of std.algorithm.remove to the array that you passed in and an std.array.replaceInPlace would be doing exactly that, I don't think that adding such a function buys us much: auto arr = [10, 22, 19, 4, 6]; arr = remove(arr, 3); assert(arr == [10, 22, 19, 6]); The main problem is understanding why remove (or erase in C++) works this way, which seems to throw off a bunch of people in both D and C++, but it's something that we're pretty much stuck with. You need the actual container (not an iterator or range) if you want to actually remove the element. - Jonathan M Davis
Re: Why is std.algorithm so complicated to use?
Another example of how std.algorithm is so hard to use (it's almost tempting me to start swearing...): How do you remove an item from an array in place? It seems so darn simple, and yet it's not in std.algorithm (or std.range). It makes something so easy so tedious.
Re: Why is std.algorithm so complicated to use?
On 07/10/2012 10:48 AM, Simen Kjaeraas wrote:
> On Tue, 10 Jul 2012 16:15:09 +0200, Jacob Carlborg wrote:
>> How do you store your ranges in a struct or class? Most of them are
>> voldemort types.
>
> Well, there is std.range.inputRangeObject, but as the name indicates
As the name "misleads"... :)
>, it's
> only an input range.
... it can be used as any one of the non-OutputRanges:
import std.algorithm;
import std.range;
import std.stdio;
void main() {
int[] a1 = [1, 2, 3];
ForwardRange!int r1 = inputRangeObject(map!"2 * a"(a1));
ForwardRange!int r2 = inputRangeObject(map!"a ^^ 2"(a1));
auto a2 = [r1, r2];
writeln(a2);
}
Replace ForwardRange!int above with any other non-OutputRange, and as
long as the input to inputRangeObject() is compatible, it will work.
(static if magic).
Ali
Re: Why is std.algorithm so complicated to use?
On 2012-07-10 22:13, Christophe Travert wrote: Then, if the purpose is to make the code efficient, I would use the loop and append everything to the result without creating the params array, and even without creating the string p. Appender is made to append everything directly to it efficiently. Yeah, I've been thinking about doing that more. -- /Jacob Carlborg
Re: Why is std.algorithm so complicated to use?
On 11-Jul-12 00:07, Tobias Pankrath wrote:
Given:
@property int delegate() foo(){ ... }
@property int bar(){ ... }
int baz(){ ... }
foo(); // calls the delegate.
bar(); // illegal
baz; // ok, call baz
dmd -property gets every single one of these wrong. -property does _not_
enforce @property semantics. It only adds a silly rule that was never
part of the @property design. I am astonished that it made it into the
compiler.
+1
Same here. Still no idea what they were smoking at the time.
--
Dmitry Olshansky
Re: Why is std.algorithm so complicated to use?
Jacob Carlborg , dans le message (digitalmars.D:171769), a écrit : > On 2012-07-10 20:04, Andrei Alexandrescu wrote: > >> Then store an array. "No one's put a gun to yer head." >> http://youtu.be/CB1Pij54gTw?t=2m29s > > That's what I'm doing. > And that's what you should do. Algorithm are not made to be stored in struct or class instance. You could use InputRange(E) and friends to do that, but that's often not optimal. Algorithm are here to do their job and output non-lazy result in the end.
Re: Why is std.algorithm so complicated to use?
"Jonathan M Davis" wrote in message
news:mailman.249.1341951069.31962.digitalmar...@puremagic.com...
> On Tuesday, July 10, 2012 21:07:51 Jacob Carlborg wrote:
>> Second, it would be much easier if it would be possible to better name
>> these ranges, something like interfaces but without polymorphism. This
>> as been mentioned several times before.
>
> They're templated types. They have to be templated types. And since
> they're
> templated types, better names do you no good whatsoever as far as
> declaring a
> variable goes. You'll _never_ be able to do something like
>
> NiceName range;
>
This isn't really true. You can still in some cases the type relative to
some other type. (warning: old code, may not compile any more)
Sure, you can use auto and typeof, but that doesn't make it clearer.
struct SubSequences(R)
{
R r;
R s;
Take!R c;
int n;
this(R r)
{
this.r = r;
s = r;
n = 0;
c = take(r, 1);
popFront();
}
void popFront()
{
c.popFront();
if (c.empty)
{
c = take(r, ++n);
s.popFront();
}
}
Take!R front() { return c; }
bool empty() { return s.empty; }
typeof(this) save() { return this; }
};
SubSequences!R subSequences(R)(R r) { return SubSequences!R(r); }
Re: Why is std.algorithm so complicated to use?
Jacob Carlborg , dans le message (digitalmars.D:171725), a écrit : >> To make the best implementation would require to know how the String >> context works. >> > String is a wrapper around str.array.Appender. Then, if the purpose is to make the code efficient, I would use the loop and append everything to the result without creating the params array, and even without creating the string p. Appender is made to append everything directly to it efficiently.
Re: Why is std.algorithm so complicated to use?
On Tuesday, July 10, 2012 21:07:51 Jacob Carlborg wrote:
> Second, it would be much easier if it would be possible to better name
> these ranges, something like interfaces but without polymorphism. This
> as been mentioned several times before.
They're templated types. They have to be templated types. And since they're
templated types, better names do you no good whatsoever as far as declaring a
variable goes. You'll _never_ be able to do something like
NiceName range;
NiceName will always be templated. The _closest_ that you get is with
Voldemort types. Since they're templated as part of the function that they're
in rather than separately, they end up with names such as Result or
FilteredRange, but you couldn't do
FilteredRange range;
because that type depends on its outer scope (in this case, filter). You'd
_still_ have to use typeof or ReturnType if you need to declare such a
variable without directly assigning it (in which case, you can use auto). And
if you have a separate range type rather than a Voldemort Type, you end up
with stuff like Until!("a == b", string, dchar). The templated nature of ranges
makes it impossible to have friendly names which you can use to simply declare
variables of a particular range type. auto, ReturnType, and typeof are
required tools for dealing with templated types like this.
- Jonathan M Davis
Re: Why is std.algorithm so complicated to use?
On Tuesday, July 10, 2012 22:04:17 Timon Gehr wrote:
> @property int delegate() foo(){ ... }
> @property int bar(){ ... }
> int baz(){ ... }
>
> foo(); // calls the delegate.
> bar(); // illegal
> baz; // ok, call baz
>
> dmd -property gets every single one of these wrong. -property does _not_
> enforce @property semantics.
The current implementation of -property is horribly broken:
http://d.puremagic.com/issues/show_bug.cgi?id=4183
http://d.puremagic.com/issues/show_bug.cgi?id=8162
It's not actually enforcing what it's supposed to enforce, and it needs to be
fixed.
- Jonathan M Davis
Re: Why is std.algorithm so complicated to use?
Given:
@property int delegate() foo(){ ... }
@property int bar(){ ... }
int baz(){ ... }
foo(); // calls the delegate.
bar(); // illegal
baz; // ok, call baz
dmd -property gets every single one of these wrong. -property
does _not_
enforce @property semantics. It only adds a silly rule that was
never
part of the @property design. I am astonished that it made it
into the
compiler.
+1
Re: Why is std.algorithm so complicated to use?
"Andrei Alexandrescu" wrote in message news:jthr4a$3f3$1...@digitalmars.com... > > I swear I'd just call it "range". > > Andrei > Sure, why not. http://d.puremagic.com/issues/show_bug.cgi?id=8371
Re: Why is std.algorithm so complicated to use?
On 07/10/2012 09:36 PM, Jesse Phillips wrote:
On Tuesday, 10 July 2012 at 00:17:12 UTC, Timon Gehr wrote:
I have heard that rumour, but TDPL wisely specifies the behaviour of
the @property attribute as follows:
'In particular "property" is recognized by the the compiler
and signals the fact that the function bearing such an attribute must
be called without the trailing ().'
That is exactly the behaviour I described.
Note that this sentence includes the notion of _calling a function_
without the trailing () and it even seems to express that the trailing
() is usually optional.
No it doesn't. It does have emphasis with 'must' and this likely comes
from D having such a long history of the optional (), but that does not
make this statement include such a notion.
I'm sure a lawyer could make a good case out of it. Anyway, TDPL
clearly does not document the broken -property behaviour.
So TDPL actually describes a subset of what I have in mind. (it seems
to leave out the function = argument case completely.) We should
therefore change where we are headed.
The -property is an implementation of what is to come. I was never
greatly for property but since we have it it should be fully enforced,
otherwise we may as well just drop it.
I think you may be misunderstanding what @property is about.
Given:
@property int delegate() foo(){ ... }
@property int bar(){ ... }
int baz(){ ... }
foo(); // calls the delegate.
bar(); // illegal
baz; // ok, call baz
dmd -property gets every single one of these wrong. -property does _not_
enforce @property semantics. It only adds a silly rule that was never
part of the @property design. I am astonished that it made it into the
compiler.
Re: Why is std.algorithm so complicated to use?
On Tue, Jul 10, 2012 at 1:22 PM, Jacob Carlborg wrote:
> On 2012-07-10 20:53, Brad Anderson wrote:
>
> For what it's worth:
>>
>> e = 10_000_000
>> a = ((1..e).to_a + (1..e).to_a).sort.uniq.map{ |e| e }
>>
>> Runs in 21,320 ms on my machine with Ruby 1.9.3 whereas:
>>
>> auto end = 10_000_000;
>> auto a = chain(iota(1, end), iota(1, end)).array()
>> .sort()
>> .uniq()
>> .map!(n=>n).array();
>>
>> Runs in 3,057ms with DMD 2.059. I believe they are largely equivalent
>> but there is probably room for improvement on both. I removed
>> to_s/to!string because I didn't want it allocation bound since we are
>> talking about algorithm and not the GC or string conversion (with string
>> conversion the numbers are 28,646ms for Ruby and 14,113ms for D).
>>
>>
> For me, using Ruby 1.9.2 and DMD 2.059, D is only just under 10 seconds
> faster.
>
> --
> /Jacob Carlborg
>
>
>
I used -O -inline -noboundscheck -release -d to build.
Regards,
Brad Anderson
Re: Why is std.algorithm so complicated to use?
On Tuesday, 10 July 2012 at 00:17:12 UTC, Timon Gehr wrote: I have heard that rumour, but TDPL wisely specifies the behaviour of the @property attribute as follows: 'In particular "property" is recognized by the the compiler and signals the fact that the function bearing such an attribute must be called without the trailing ().' That is exactly the behaviour I described. Note that this sentence includes the notion of _calling a function_ without the trailing () and it even seems to express that the trailing () is usually optional. No it doesn't. It does have emphasis with 'must' and this likely comes from D having such a long history of the optional (), but that does not make this statement include such a notion. So TDPL actually describes a subset of what I have in mind. (it seems to leave out the function = argument case completely.) We should therefore change where we are headed. The -property is an implementation of what is to come. I was never greatly for property but since we have it it should be fully enforced, otherwise we may as well just drop it.
Re: Why is std.algorithm so complicated to use?
On 2012-07-10 20:53, Brad Anderson wrote:
For what it's worth:
e = 10_000_000
a = ((1..e).to_a + (1..e).to_a).sort.uniq.map{ |e| e }
Runs in 21,320 ms on my machine with Ruby 1.9.3 whereas:
auto end = 10_000_000;
auto a = chain(iota(1, end), iota(1, end)).array()
.sort()
.uniq()
.map!(n=>n).array();
Runs in 3,057ms with DMD 2.059. I believe they are largely equivalent
but there is probably room for improvement on both. I removed
to_s/to!string because I didn't want it allocation bound since we are
talking about algorithm and not the GC or string conversion (with string
conversion the numbers are 28,646ms for Ruby and 14,113ms for D).
For me, using Ruby 1.9.2 and DMD 2.059, D is only just under 10 seconds
faster.
--
/Jacob Carlborg
Re: Why is std.algorithm so complicated to use?
On 2012-07-10 20:04, Andrei Alexandrescu wrote: Then store an array. "No one's put a gun to yer head." http://youtu.be/CB1Pij54gTw?t=2m29s That's what I'm doing. -- /Jacob Carlborg
Re: Why is std.algorithm so complicated to use?
On 2012-07-10 19:30, Jonathan M Davis wrote:
typeof(bar()) x;
works. But regardless, given that you're dealing with a return type which is
auto, there's really no other choice. Even if we weren't using voldemort types
for stuff like map, the return type would still be templated and depend on the
actual arguments to map, making writing the type a pain - especially if it's
complicated; until (which _doesn't_ use a voldemort type) is a prime example
of this. You end up with something like Until!("a == b",int[],int) for a basic
call to until, and it gets really nasty if you start chaining function calls
so that the range passed to Until is far more complicated than int[]. Using
ReturnType and typeof becames the sane thing to do (and much more maintainable
too, since you don't have to change it if/when you change the call to map
enough that it's return type changes). It does take some getting used to, but
it works very well. You just have to realize that if you're operating on
ranges, you're generally _not_ caring what they exact type is, and you use
auto and templates a lot. Sometimes converting the result to an array is
exactly what you want to do, but the less you do that, the more efficient your
code will be.
First, both using typeof and ReturnType forces me to have the instance
variable below the method due to otherwise forward reference errors.
Which I really, really don't like.
Second, it would be much easier if it would be possible to better name
these ranges, something like interfaces but without polymorphism. This
as been mentioned several times before.
--
/Jacob Carlborg
Re: Why is std.algorithm so complicated to use?
On 2012-07-10 19:55, Andrei Alexandrescu wrote: Clearly this and any documentation can be improved, but I'd say if it says "range" there there's no assumption "sorted range" there. I think the main thing that could be expressed better is "unique consecutive". Fair enough. I think it would be onerous to mention for each algorithm, although clearly they all are generic, that they can handle ranges with any element type. You see how stupid that is. That being what? I was trying to point out that one cannot assume how a function behaves just by looking at one example. Specially not a template function. -- /Jacob Carlborg
Re: Why is std.algorithm so complicated to use?
On 2012-07-10 19:23, Daniel Murphy wrote: writeln([1, 2, 3].map!"a"()[2]); Sort is in place, and therefore requires more than random access, you need to be able to modify the data you're operating on. Something like [3, 4].map!func().selectionSort() could work lazily without needing to modify the original range, but urrgh. Ok, I think I get it now. -- /Jacob Carlborg
Re: Why is std.algorithm so complicated to use?
On Tue, Jul 10, 2012 at 3: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
>
> Prints:
>
> ["3", "5", "6", "8"]
>
> --
> /Jacob Carlborg
>
For what it's worth:
e = 10_000_000
a = ((1..e).to_a + (1..e).to_a).sort.uniq.map{ |e| e }
Runs in 21,320 ms on my machine with Ruby 1.9.3 whereas:
auto end = 10_000_000;
auto a = chain(iota(1, end), iota(1, end)).array()
.sort()
.uniq()
.map!(n=>n).array();
Runs in 3,057ms with DMD 2.059. I believe they are largely equivalent but
there is probably room for improvement on both. I removed to_s/to!string
because I didn't want it allocation bound since we are talking about
algorithm and not the GC or string conversion (with string conversion the
numbers are 28,646ms for Ruby and 14,113ms for D).
Regards,
Brad Anderson
Re: Why is std.algorithm so complicated to use?
"Andrei Alexandrescu" wrote in message news:jthr4a$3f3$1...@digitalmars.com... > On 7/10/12 2:08 PM, Jonathan M Davis wrote: >>> That does seem good to have. What would be a better name than makeRange? >> >> I see no problem with makeRange. It seems like a sensible name to me. >> You're >> taking a sequence of elements and making a range out of them. > > I swear I'd just call it "range". > > Andrei > tuple(1, 2, 3).rangeOf
Re: Why is std.algorithm so complicated to use?
On 07/10/2012 08:09 PM, Andrei Alexandrescu wrote: On 7/10/12 2:08 PM, Jonathan M Davis wrote: That does seem good to have. What would be a better name than makeRange? I see no problem with makeRange. It seems like a sensible name to me. You're taking a sequence of elements and making a range out of them. I swear I'd just call it "range". Andrei This was my thinking as well.
Re: Why is std.algorithm so complicated to use?
On Tue, 10 Jul 2012 16:27:31 +0200, Andrei Alexandrescu wrote: 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? Mostly because I like the std.algorithm way of writing stuff, now we have UFCS. But yes, could not come up with a good case for not using loops beyond that. -- Simen
Re: Why is std.algorithm so complicated to use?
On Tue, 10 Jul 2012 20:09:15 +0200, Andrei Alexandrescu wrote: On 7/10/12 2:08 PM, Jonathan M Davis wrote: That does seem good to have. What would be a better name than makeRange? I see no problem with makeRange. It seems like a sensible name to me. You're taking a sequence of elements and making a range out of them. I swear I'd just call it "range". Andrei I'm with Andy on this. -- Simen
Re: Why is std.algorithm so complicated to use?
On 7/10/12 2:02 PM, Simen Kjaeraas wrote: On Tue, 10 Jul 2012 17:21:14 +0200, Christophe Travert wrote: "Simen Kjaeraas" , dans le message (digitalmars.D:171678), a écrit : 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. That would have been useful before UFSC. Now, writing .array() at the end of an algorithm call is not a pain. int[] = [1, 2, 2, 3].uniq().map!toString().array(); Please tell me how that is in-place. Let's say it doesn't perform unnecessary allocations. It's like you'd create the array ["1", "2", "3"] from the array [1, 2, 2, 3] using a loop and a couple of state variables. Andrei
Re: Why is std.algorithm so complicated to use?
On 7/10/12 2:08 PM, Jonathan M Davis wrote: That does seem good to have. What would be a better name than makeRange? I see no problem with makeRange. It seems like a sensible name to me. You're taking a sequence of elements and making a range out of them. I swear I'd just call it "range". Andrei
Re: Why is std.algorithm so complicated to use?
On Tuesday, July 10, 2012 13:58:50 Andrei Alexandrescu wrote:
> On 7/10/12 1:17 PM, Daniel Murphy wrote:
> > "Christophe Travert" wrote in message
> > news:jthmu8$2s5b$1...@digitalmars.com...
> >
> >> "Daniel Murphy" , dans le message (digitalmars.D:171720), a écrit :
> >>> Could it be extended to accept multiple values? (sort of like chain)
> >>> eg.
> >>> foreach(x; makeRange(23, 7, 1990)) // NO allocations!
> >>> {
> >>>
> >>>
> >>>
> >>> }
> >>> I would use this in a lot of places I currently jump through hoops to
> >>> get
> >>> a
> >>> static array without allocating.
> >>
> >> That's a good idea. IMHO, the real solution would be to make an easy way
> >> to create static arrays, and slice them when you want a range.
> >
> > It's not quite the same thing, static arrays are not ranges and once you
> > slice them you no longer have a value type, and might be referring to
> > stack
> > allocated data. With... this thing, the length/progress is not encoded in
> > the type (making it rangeable) but the data _is_ contained in the type,
> > making it safe to pass around. The best of both worlds, in some
> > situations.
> That does seem good to have. What would be a better name than makeRange?
I see no problem with makeRange. It seems like a sensible name to me. You're
taking a sequence of elements and making a range out of them.
- Jonathan M Davis
Re: Why is std.algorithm so complicated to use?
On 7/10/12 1:05 PM, Jacob Carlborg wrote: On 2012-07-10 16:22, Andrei Alexandrescu wrote: It may be the case you're trying to write ruby in D. I rarely need to convert stuff to arrays. Mostly I receive an array, do some operations on it and then want to store the result in an instance variable in a class or struct. It's quite awkward to store a range in an instance variable. Then store an array. "No one's put a gun to yer head." http://youtu.be/CB1Pij54gTw?t=2m29s Andrei
Re: Why is std.algorithm so complicated to use?
On Tue, 10 Jul 2012 17:21:14 +0200, Christophe Travert wrote: "Simen Kjaeraas" , dans le message (digitalmars.D:171678), a écrit : 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. That would have been useful before UFSC. Now, writing .array() at the end of an algorithm call is not a pain. int[] = [1, 2, 2, 3].uniq().map!toString().array(); Please tell me how that is in-place. -- Simen
Re: Why is std.algorithm so complicated to use?
On 7/10/12 12:57 PM, Jacob Carlborg wrote: On 2012-07-10 16:36, Dmitry Olshansky wrote: 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. Sure, this particular example uses a sorted array, but nothing says an unsorted array won't work. Clearly this and any documentation can be improved, but I'd say if it says "range" there there's no assumption "sorted range" there. I think the main thing that could be expressed better is "unique consecutive". Does it only handle ints. It doesn't say anything about that in the documentation and the example uses ints. Then it must only accept ints. I think it would be onerous to mention for each algorithm, although clearly they all are generic, that they can handle ranges with any element type. You see how stupid that is. That being what? Andrei
Re: Why is std.algorithm so complicated to use?
On 7/10/12 1:17 PM, Daniel Murphy wrote:
"Christophe Travert" wrote in message
news:jthmu8$2s5b$1...@digitalmars.com...
"Daniel Murphy" , dans le message (digitalmars.D:171720), a écrit :
Could it be extended to accept multiple values? (sort of like chain)
eg.
foreach(x; makeRange(23, 7, 1990)) // NO allocations!
{
}
I would use this in a lot of places I currently jump through hoops to get
a
static array without allocating.
That's a good idea. IMHO, the real solution would be to make an easy way
to create static arrays, and slice them when you want a range.
It's not quite the same thing, static arrays are not ranges and once you
slice them you no longer have a value type, and might be referring to stack
allocated data. With... this thing, the length/progress is not encoded in
the type (making it rangeable) but the data _is_ contained in the type,
making it safe to pass around. The best of both worlds, in some situations.
That does seem good to have. What would be a better name than makeRange?
Andrei
Re: Why is std.algorithm so complicated to use?
On 7/10/12 12:38 PM, Jacob Carlborg wrote: Can't "map" and "filter" return a random-access range if that's what they receive? (replied to by others) Now I understand if you come from a place where there's no concern over hidden allocations and extra work for the benefit of convenience, you may find std.algorithm less easy to work with. But drawing the conclusion that std.algorithm is badly designed or gratuitously difficult to use would be a mistake. I opine I can recognize a good vs. bad design even when it's mine, and in my opinion std.algorithm is a good design and that most of your opposing impressions derive from a misunderstanding of its charter. I don't think I've struggled as much with any other API I've used. In many cases I had to resort to foreach-loops because that was more convenient than using std.algorithm. That's fine. I don't see std.algorithm as a competitor against simple loops, but instead of work that would be very verbose and difficult to do with loops. I mean I clearly recall at a point I wanted to define a forAll algorithm, but then I was like, "people can use foreach for that". Andrei
Re: Why is std.algorithm so complicated to use?
On Tue, 10 Jul 2012 16:15:09 +0200, 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. Well, there is std.range.inputRangeObject, but as the name indicates, it's only an input range. " 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? You shouldn't. The description however, says 'unique consecutive elements', which *does* explain it. -- Simen
Re: Why is std.algorithm so complicated to use?
"Christophe Travert" wrote in message
news:jthp14$30em$1...@digitalmars.com...
> "Daniel Murphy" , dans le message (digitalmars.D:171741), a écrit :
>> "Christophe Travert" wrote in message
>> news:jthmu8$2s5b$1...@digitalmars.com...
>>> "Daniel Murphy" , dans le message (digitalmars.D:171720), a écrit :
Could it be extended to accept multiple values? (sort of like chain)
eg.
foreach(x; makeRange(23, 7, 1990)) // NO allocations!
{
}
I would use this in a lot of places I currently jump through hoops to
get
a
static array without allocating.
>>>
>>> That's a good idea. IMHO, the real solution would be to make an easy way
>>> to create static arrays, and slice them when you want a range.
>>
>> It's not quite the same thing, static arrays are not ranges and once you
>> slice them you no longer have a value type, and might be referring to
>> stack
>> allocated data. With... this thing, the length/progress is not encoded
>> in
>> the type (making it rangeable) but the data _is_ contained in the type,
>> making it safe to pass around. The best of both worlds, in some
>> situations.
>
> OK, I see. This goes against the principle that ranges are small and
> easy to copy arround, but it can be useful when you know what you are
> doing, or when the number of items is small.
>
Yeah, it works where you'd pass a tuple of elements of the same type, but
want to iterate over it.
> I don't like makeRange much. Would you have a better name? smallRange?
> rangeOf?
>
>
rangeit
Re: Why is std.algorithm so complicated to use?
"Daniel Murphy" , dans le message (digitalmars.D:171741), a écrit :
> "Christophe Travert" wrote in message
> news:jthmu8$2s5b$1...@digitalmars.com...
>> "Daniel Murphy" , dans le message (digitalmars.D:171720), a écrit :
>>> Could it be extended to accept multiple values? (sort of like chain)
>>> eg.
>>> foreach(x; makeRange(23, 7, 1990)) // NO allocations!
>>> {
>>>
>>> }
>>> I would use this in a lot of places I currently jump through hoops to get
>>> a
>>> static array without allocating.
>>
>> That's a good idea. IMHO, the real solution would be to make an easy way
>> to create static arrays, and slice them when you want a range.
>
> It's not quite the same thing, static arrays are not ranges and once you
> slice them you no longer have a value type, and might be referring to stack
> allocated data. With... this thing, the length/progress is not encoded in
> the type (making it rangeable) but the data _is_ contained in the type,
> making it safe to pass around. The best of both worlds, in some situations.
OK, I see. This goes against the principle that ranges are small and
easy to copy arround, but it can be useful when you know what you are
doing, or when the number of items is small.
I don't like makeRange much. Would you have a better name? smallRange?
rangeOf?
Re: Why is std.algorithm so complicated to use?
On Tuesday, July 10, 2012 14:27:14 Simen Kjaeraas wrote: > On Tue, 10 Jul 2012 09:04:31 +0200, Jonathan M Davis > > 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. Ah, you're right. I'm too used to thinking about filter, but map doesn't change the number of elements, so it works just fine as random access (though it risks being an efficient way of doing things if the function using it accessing its elements multiple times, since it's going to have to call the predicate every time that the element is accessed, whereas if you just iterate over the range, then odds are that you only access the element once). - Jonathan M Davis
Re: Why is std.algorithm so complicated to use?
On Tuesday, July 10, 2012 12:22:30 Andrei Alexandrescu wrote:
> On 7/10/12 12:01 PM, Christophe Travert wrote:
> > Andrei Alexandrescu , dans le message (digitalmars.D:171717), a écrit :
> >> auto singletonRange(E)(E value)
> >> {
> >>
> >> return repeat(value).takeExactly(1);
> >>
> >> }
> >
> > It would be much better to use:
> >
> > auto singletonRange(E)(E value)
> > {
> >
> > return repeat(value).takeOne;
> >
> > }
> >
> > as well as:
> >
> > auto emptyRange(E)(E value)
> > {
> >
> > return repeat(value).takeNone;
> >
> > }
> >
> > to have the advantages of takeOne and takeNone over takeExactly.
>
> Ah, such as them being random access. Cool!
>
> That also seems to answer Jonathan's quest about defining emptyRange.
> Just use takeNone(R.init).
Actually, it doesn't, because find needs the ability to get an empty range of
the exact same type as the original. It's a nice idea for cases where the
resultant range doesn't matter though.
- Jonathan M Davis
Re: Why is std.algorithm so complicated to use?
On Tuesday, July 10, 2012 18:57:25 Jacob Carlborg wrote:
> On 2012-07-10 16:36, Dmitry Olshansky wrote:
> > 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.
>
> I'm not exactly sure how you mean but this is what I came up with:
>
> import std.algorithm;
> import std.traits;
> import std.conv;
>
> class Foo
> {
> auto bar ()
> {
> return [3, 4].map!(x => x.to!(string));
> }
>
> ReturnType!(bar) x;
> }
typeof(bar()) x;
works. But regardless, given that you're dealing with a return type which is
auto, there's really no other choice. Even if we weren't using voldemort types
for stuff like map, the return type would still be templated and depend on the
actual arguments to map, making writing the type a pain - especially if it's
complicated; until (which _doesn't_ use a voldemort type) is a prime example
of this. You end up with something like Until!("a == b",int[],int) for a basic
call to until, and it gets really nasty if you start chaining function calls
so that the range passed to Until is far more complicated than int[]. Using
ReturnType and typeof becames the sane thing to do (and much more maintainable
too, since you don't have to change it if/when you change the call to map
enough that it's return type changes). It does take some getting used to, but
it works very well. You just have to realize that if you're operating on
ranges, you're generally _not_ caring what they exact type is, and you use
auto and templates a lot. Sometimes converting the result to an array is
exactly what you want to do, but the less you do that, the more efficient your
code will be.
- Jonathan M Davis
Re: Why is std.algorithm so complicated to use?
"Jacob Carlborg" wrote in message news:jthnlo$2tjg$1...@digitalmars.com... > On 2012-07-10 18:42, Daniel Murphy wrote: >> "Jacob Carlborg" wrote in message >> news:jthlpf$2pnb$1...@digitalmars.com... >>> >>> Can't "map" and "filter" return a random-access range if that's what >>> they >>> receive? >>> >> map can, and does. > > It doesn't seem to: > > auto a = [3, 4].map!(x => x); > auto b = a.sort; > > Result in one of the original errors I started this thread with. > > -- > /Jacob Carlborg > > writeln([1, 2, 3].map!"a"()[2]); Sort is in place, and therefore requires more than random access, you need to be able to modify the data you're operating on. Something like [3, 4].map!func().selectionSort() could work lazily without needing to modify the original range, but urrgh.
Re: Why is std.algorithm so complicated to use?
Jacob Carlborg , dans le message (digitalmars.D:171739), a écrit :
> On 2012-07-10 18:42, Daniel Murphy wrote:
>> "Jacob Carlborg" wrote in message
>> news:jthlpf$2pnb$1...@digitalmars.com...
>>>
>>> Can't "map" and "filter" return a random-access range if that's what they
>>> receive?
>>>
>> map can, and does.
>
> It doesn't seem to:
>
> auto a = [3, 4].map!(x => x);
> auto b = a.sort;
>
> Result in one of the original errors I started this thread with.
here, map is random-access. But random access is not enough to call
sort: you need to have assignable (well, swapable) elements in the
range, if you want to be able to sort it. values accessed via a map are
not always assignable, since they are the result of a function.
It seems the map resulting from (x => x) is not assignable. This is
debatable, but since (x => x) is just a stupid function to test.
Otherwise, you could try the folowing:
auto a = [3, 4].map!(ref int (ref int x) { return x; })();
a.sort;
Re: Why is std.algorithm so complicated to use?
"Christophe Travert" wrote in message
news:jthmu8$2s5b$1...@digitalmars.com...
> "Daniel Murphy" , dans le message (digitalmars.D:171720), a écrit :
>> Could it be extended to accept multiple values? (sort of like chain)
>> eg.
>> foreach(x; makeRange(23, 7, 1990)) // NO allocations!
>> {
>>
>> }
>> I would use this in a lot of places I currently jump through hoops to get
>> a
>> static array without allocating.
>
> That's a good idea. IMHO, the real solution would be to make an easy way
> to create static arrays, and slice them when you want a range.
>
It's not quite the same thing, static arrays are not ranges and once you
slice them you no longer have a value type, and might be referring to stack
allocated data. With... this thing, the length/progress is not encoded in
the type (making it rangeable) but the data _is_ contained in the type,
making it safe to pass around. The best of both worlds, in some situations.
An easy way to get static arrays would be great too.
>
> I it were just me, array litterals would be static, and people
> should use .dup when they want a a surviving slice.
>
It used to be like that. Most of the time you don't really want a static
array.
Re: Why is std.algorithm so complicated to use?
On 2012-07-10 18:42, Daniel Murphy wrote: "Jacob Carlborg" wrote in message news:jthlpf$2pnb$1...@digitalmars.com... Can't "map" and "filter" return a random-access range if that's what they receive? map can, and does. It doesn't seem to: auto a = [3, 4].map!(x => x); auto b = a.sort; Result in one of the original errors I started this thread with. -- /Jacob Carlborg
Re: Why is std.algorithm so complicated to use?
On 2012-07-10 16:22, Andrei Alexandrescu wrote: It may be the case you're trying to write ruby in D. I rarely need to convert stuff to arrays. Mostly I receive an array, do some operations on it and then want to store the result in an instance variable in a class or struct. It's quite awkward to store a range in an instance variable. -- /Jacob Carlborg
Re: Why is std.algorithm so complicated to use?
Jacob Carlborg , dans le message (digitalmars.D:171725), a écrit : > On 2012-07-10 17:11, Christophe Travert wrote: > >> What is wrong with foo.chain(["bar"])? > > I think it conceptually wrong for what I want to do. I don't know if I > misunderstood ranges completely but I'm seeing them as an abstraction > over a collection. With most mutable collection you can add/append an > element. That may be the source of your problem. ranges are not collections. They do not own data. They just show data. You can't make them grow. You can only consume what you have already read.
Re: Why is std.algorithm so complicated to use?
"Daniel Murphy" , dans le message (digitalmars.D:171720), a écrit :
> Could it be extended to accept multiple values? (sort of like chain)
> eg.
> foreach(x; makeRange(23, 7, 1990)) // NO allocations!
> {
>
> }
> I would use this in a lot of places I currently jump through hoops to get a
> static array without allocating.
That's a good idea. IMHO, the real solution would be to make an easy way
to create static arrays, and slice them when you want a range.
--
Christophe
I it were just me, array litterals would be static, and people
should use .dup when they want a a surviving slice.
Well, if it were just me, all function signature should tell when
references to data escape the scope of the function, and all data would
be allocated automatically where it should by the compiler.
Re: Why is std.algorithm so complicated to use?
On 2012-07-10 16:36, Dmitry Olshansky wrote:
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.
I'm not exactly sure how you mean but this is what I came up with:
import std.algorithm;
import std.traits;
import std.conv;
class Foo
{
auto bar ()
{
return [3, 4].map!(x => x.to!(string));
}
ReturnType!(bar) x;
}
Which is just the worst idea ever. BTW I can't see how "typeof" would work.
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.
Aha, I didn't know that it sorted in place.
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.
See above.
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.
Sure, this particular example uses a sorted array, but nothing says an
unsorted array won't work.
Does it only handle ints. It doesn't say anything about that in the
documentation and the example uses ints. Then it must only accept ints.
You see how stupid that is.
--
/Jacob Carlborg
Re: Why is std.algorithm so complicated to use?
Andrei Alexandrescu , dans le message (digitalmars.D:171723), a écrit :
>> auto emptyRange(E)(E value)
>> {
>>return repeat(value).takeNone;
>> }
> That also seems to answer Jonathan's quest about defining emptyRange.
> Just use takeNone(R.init).
err, that should be more like:
auto singletonRange(E)() // with no parameters
{
return takeNone!type_of(repeat(E.init))();
}
An emptyRange compatible with singletonRange should be called
singletonRange and take no parameter, so that emptyRange name could be
reserved to a real statically empty range (which is pretty easy to
implement).
--
Christophe
Re: Why is std.algorithm so complicated to use?
On 07/10/2012 06:40 PM, Jacob Carlborg wrote: On 2012-07-10 16:54, Andrei Alexandrescu wrote: Actually I take that back. One may use uniq to remove duplicates in unsorted ranges. How does that work? It didn't work in my example. It works. It removes consecutive duplicates. 'uniq' in ruby is different, which is strange as the name was taken from the command-line facility. (that also removes consecutive duplicates)
Re: Why is std.algorithm so complicated to use?
"Jacob Carlborg" wrote in message news:jthlpf$2pnb$1...@digitalmars.com... > > Can't "map" and "filter" return a random-access range if that's what they > receive? > map can, and does. filter cannot, because it doesn't know which element is number 4 until it knows if element 3 is included or not.
Re: Why is std.algorithm so complicated to use?
On 07/10/2012 06:38 PM, Jacob Carlborg wrote: On 2012-07-10 17:30, Andrei Alexandrescu wrote: It would be possible to chain a single element to the end of a range. One related thing to do is to define singletonRange(x) that returns a range with exactly one element, namely x. Ok, I saw that suggestion in another post. Ranges and std.algorithm obey simple, mathematical realities deriving from algorithm and storage topology constraints. For example sort works in place so it generally can't work on mapped stuff because there's no place to put the sorted contents. Also sort needs a random-access range to work with so it can't work e.g. with the result of filter, which necessarily yields a non-random-access range. And so on. Can't "map" and "filter" return a random-access range if that's what they receive? Map can do that and does do that. How would it work for filter?
Re: Why is std.algorithm so complicated to use?
On 2012-07-10 16:54, Andrei Alexandrescu wrote: Actually I take that back. One may use uniq to remove duplicates in unsorted ranges. How does that work? It didn't work in my example. -- /Jacob Carlborg
Re: Why is std.algorithm so complicated to use?
On 2012-07-10 17:30, Andrei Alexandrescu wrote: It would be possible to chain a single element to the end of a range. One related thing to do is to define singletonRange(x) that returns a range with exactly one element, namely x. Ok, I saw that suggestion in another post. Ranges and std.algorithm obey simple, mathematical realities deriving from algorithm and storage topology constraints. For example sort works in place so it generally can't work on mapped stuff because there's no place to put the sorted contents. Also sort needs a random-access range to work with so it can't work e.g. with the result of filter, which necessarily yields a non-random-access range. And so on. Can't "map" and "filter" return a random-access range if that's what they receive? Now I understand if you come from a place where there's no concern over hidden allocations and extra work for the benefit of convenience, you may find std.algorithm less easy to work with. But drawing the conclusion that std.algorithm is badly designed or gratuitously difficult to use would be a mistake. I opine I can recognize a good vs. bad design even when it's mine, and in my opinion std.algorithm is a good design and that most of your opposing impressions derive from a misunderstanding of its charter. I don't think I've struggled as much with any other API I've used. In many cases I had to resort to foreach-loops because that was more convenient than using std.algorithm. -- /Jacob Carlborg
Re: Why is std.algorithm so complicated to use?
On 2012-07-10 17:11, Christophe Travert wrote:
What is wrong with foo.chain(["bar"])?
I think it conceptually wrong for what I want to do. I don't know if I
misunderstood ranges completely but I'm seeing them as an abstraction
over a collection. With most mutable collection you can add/append an
element.
you might try this (untested)
string function(Parameter) stringify = (x)
{
return (x.isConst? "const("~x.type~")": x.type)
~ (x.name.any?" "~translateIdentifier(x.name):"");
}
auto params = parameters
.map!stringify()
.chain(variadic? []: ["..."])
.joiner(", ");
context ~= params;
I am not sure this will be more efficient. joiner may be slowed down by
the fact that it is called with a chain result, which is slower on
front. But at leat you save yourself the heap-allocation of the params
array*.
I would use:
context ~= parameters.map!stringify().joiner(", ");
if (variadic) context ~= ", ...";
To make the best implementation would require to know how the String
context works.
*Note that here, stringify is not lazy, and thus allocates. It
could be a chain or a joiner, but I'm not sure the result would really
be more efficient.
String is a wrapper around str.array.Appender.
--
/Jacob Carlborg
Re: Why is std.algorithm so complicated to use?
On 2012-07-10 16:49, Dmitry Olshansky wrote: 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. Sure if remove the call to "join" and build a single string from the beginning, then a foreach would be the right approach. But if you look at the code as it is now the foreach-loop maps an array of "Parameter" to an array of "string". 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. I have only been able to remove very few temporary arrays. -- /Jacob Carlborg
Re: Why is std.algorithm so complicated to use?
On 7/10/12 12:01 PM, Christophe Travert wrote:
Andrei Alexandrescu , dans le message (digitalmars.D:171717), a écrit :
auto singletonRange(E)(E value)
{
return repeat(value).takeExactly(1);
}
It would be much better to use:
auto singletonRange(E)(E value)
{
return repeat(value).takeOne;
}
as well as:
auto emptyRange(E)(E value)
{
return repeat(value).takeNone;
}
to have the advantages of takeOne and takeNone over takeExactly.
Ah, such as them being random access. Cool!
That also seems to answer Jonathan's quest about defining emptyRange.
Just use takeNone(R.init).
Andrei
Re: Why is std.algorithm so complicated to use?
Andrei Alexandrescu , dans le message (digitalmars.D:171717), a écrit :
> On 7/10/12 11:11 AM, Christophe Travert wrote:
>> If you do not want the heap allocation of the array, you can create a
>> one-element range to feed to chain (maybe such a thing could be placed
>> in phobos, next to takeOne).
>>
>> struct OneElementRange(E)
>> {
>>E elem;
>>bool passed;
>>@property ref E front() { return elem; }
>>void popFront() { passed = true; }
>>@property bool empty() { return passed; }
>>@property size_t length() { return 1-passed; }
>>//...
>> }
>
> Yah, probably we should add something like this:
>
> auto singletonRange(E)(E value)
> {
> return repeat(value).takeExactly(1);
> }
It would be much better to use:
auto singletonRange(E)(E value)
{
return repeat(value).takeOne;
}
as well as:
auto emptyRange(E)(E value)
{
return repeat(value).takeNone;
}
to have the advantages of takeOne and takeNone over takeExactly.
> I don't think it would be considerably less efficient than a handwritten
> specialization. But then I've been wrong before in assessing efficiency.
Error message displaying the type of singletonRange(E) will be weird,
but that's far from being the first place where it will be. Simplicity
and maintainance of phobos seems more important to me. At least until
these algorithm get stable, meaning open bug reports on algorithm and
range are solved, and new bugs appears rarely. Optimisers should have no
trouble inlining calls to Repeat's methods...
Re: Why is std.algorithm so complicated to use?
"Andrei Alexandrescu" wrote in message
news:jthiba$2cg0$1...@digitalmars.com...
> On 7/10/12 11:11 AM, Christophe Travert wrote:
>> If you do not want the heap allocation of the array, you can create a
>> one-element range to feed to chain (maybe such a thing could be placed
>> in phobos, next to takeOne).
>>
>> struct OneElementRange(E)
>> {
>>E elem;
>>bool passed;
>>@property ref E front() { return elem; }
>>void popFront() { passed = true; }
>>@property bool empty() { return passed; }
>>@property size_t length() { return 1-passed; }
>>//...
>> }
>
> Yah, probably we should add something like this:
>
> auto singletonRange(E)(E value)
> {
> return repeat(value).takeExactly(1);
> }
>
> I don't think it would be considerably less efficient than a handwritten
> specialization. But then I've been wrong before in assessing efficiency.
>
>
> Andrei
Could it be extended to accept multiple values? (sort of like chain)
eg.
foreach(x; makeRange(23, 7, 1990)) // NO allocations!
{
}
I would use this in a lot of places I currently jump through hoops to get a
static array without allocating.
Re: Why is std.algorithm so complicated to use?
On Tuesday, July 10, 2012 15:21:14 Christophe Travert wrote: > "Simen Kjaeraas" , dans le message (digitalmars.D:171678), a écrit : > >> 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. > > That would have been useful before UFSC. > Now, writing .array() at the end of an algorithm call is not a pain. > > int[] = [1, 2, 2, 3].uniq().map!toString().array(); It's not like auto result = array(map!"to!string(a)"(uniq([1, 2, 2, 3]))); is a pain either. It's just ordered differently. But regardless, it's easy to get an eager result by calling array on a lazy range, so there's no point in adding eager versions. They'd just be duplicating code for no real benefit. Not to mention, if anyone having to call array on ranges all of the time, you should probably rethink how they're using ranges. It's definitely necessary some of the time, but most of the time, you can just operate on the lazy ranges and save yourself unnecessary allocations. - Jonathan M Davis
Re: Why is std.algorithm so complicated to use?
On 7/10/12 11:11 AM, Christophe Travert wrote:
If you do not want the heap allocation of the array, you can create a
one-element range to feed to chain (maybe such a thing could be placed
in phobos, next to takeOne).
struct OneElementRange(E)
{
E elem;
bool passed;
@property ref E front() { return elem; }
void popFront() { passed = true; }
@property bool empty() { return passed; }
@property size_t length() { return 1-passed; }
//...
}
Yah, probably we should add something like this:
auto singletonRange(E)(E value)
{
return repeat(value).takeExactly(1);
}
I don't think it would be considerably less efficient than a handwritten
specialization. But then I've been wrong before in assessing efficiency.
Andrei
Re: Why is std.algorithm so complicated to use?
Jacob Carlborg , dans le message (digitalmars.D:171690), a écrit : >> 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? Maybe there should be an example with an unsorted range, and a better explanation: | auto uniq(...) | Iterates unique consecutive elements of a given range (...) | Note that equivalent elements are kept if they are not consecutive. | | Example: | int[] arr = [ 1, 2, 2, 3, 4, 4, 4, 2, 4, 4]; | assert(equal(uniq(arr), [ 1, 2, 3, 4, 2, 4][]));
Re: Why is std.algorithm so complicated to use?
On 7/10/12 11:17 AM, Jonathan M Davis wrote:
On Tuesday, July 10, 2012 10:21:23 Andrei Alexandrescu wrote:
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.
The other thing that affects a lot is infinite ranges. The functions with lazy
results work wonderfully with infinite ranges but would generally result in
infinite loops if used with functions with eager results.
auto vals = map!"a % 10"(rndGen());
works great, but you'd be forced to use take directly on rndGen pretty much
all the time you wanted to do something like that if functions like map were
lazy.
But I suspect that the sort of people who will be complaining about map not
returning an array are also the sort of people who won't be all that familar
with operating on infinite lists and at least initially probably won't care.
- Jonathan M Davis
It's also about the unnecessary work done eagerly on finite but long inputs.
Andrei
Re: Why is std.algorithm so complicated to use?
On 7/10/12 9:56 AM, 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");
It would be possible to chain a single element to the end of a range.
One related thing to do is to define singletonRange(x) that returns a
range with exactly one element, namely x.
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.
Ranges and std.algorithm obey simple, mathematical realities deriving
from algorithm and storage topology constraints. For example sort works
in place so it generally can't work on mapped stuff because there's no
place to put the sorted contents. Also sort needs a random-access range
to work with so it can't work e.g. with the result of filter, which
necessarily yields a non-random-access range. And so on.
Now I understand if you come from a place where there's no concern over
hidden allocations and extra work for the benefit of convenience, you
may find std.algorithm less easy to work with. But drawing the
conclusion that std.algorithm is badly designed or gratuitously
difficult to use would be a mistake. I opine I can recognize a good vs.
bad design even when it's mine, and in my opinion std.algorithm is a
good design and that most of your opposing impressions derive from a
misunderstanding of its charter.
Andrei
Re: Why is std.algorithm so complicated to use?
"Simen Kjaeraas" , dans le message (digitalmars.D:171678), a écrit : >> 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. That would have been useful before UFSC. Now, writing .array() at the end of an algorithm call is not a pain. int[] = [1, 2, 2, 3].uniq().map!toString().array();
Re: Why is std.algorithm so complicated to use?
Dmitry Olshansky , dans le message (digitalmars.D:171679), a écrit : > 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. > " Not, as the doc says, uniq work on any range, but remove only the consecutive elements. It you want to remove all duplicates, then you need a sorted range.
Re: Why is std.algorithm so complicated to use?
On Tuesday, July 10, 2012 10:21:23 Andrei Alexandrescu wrote:
> 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.
The other thing that affects a lot is infinite ranges. The functions with lazy
results work wonderfully with infinite ranges but would generally result in
infinite loops if used with functions with eager results.
auto vals = map!"a % 10"(rndGen());
works great, but you'd be forced to use take directly on rndGen pretty much
all the time you wanted to do something like that if functions like map were
lazy.
But I suspect that the sort of people who will be complaining about map not
returning an array are also the sort of people who won't be all that familar
with operating on infinite lists and at least initially probably won't care.
- Jonathan M Davis
Re: Why is std.algorithm so complicated to use?
Jacob Carlborg , dans le message (digitalmars.D:171685), a écrit :
> 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");
What is wrong with foo.chain(["bar"])?
If you do not want the heap allocation of the array, you can create a
one-element range to feed to chain (maybe such a thing could be placed
in phobos, next to takeOne).
struct OneElementRange(E)
{
E elem;
bool passed;
@property ref E front() { return elem; }
void popFront() { passed = true; }
@property bool empty() { return passed; }
@property size_t length() { return 1-passed; }
//...
}
You can't expect chain to work the same way as run-time append. A
compile-time append would be very inefficient if misused.
> https://github.com/jacob-carlborg/dstep/blob/master/dstep/translator/Translator.d#L217
you might try this (untested)
string function(Parameter) stringify = (x)
{
return (x.isConst? "const("~x.type~")": x.type)
~ (x.name.any?" "~translateIdentifier(x.name):"");
}
auto params = parameters
.map!stringify()
.chain(variadic? []: ["..."])
.joiner(", ");
context ~= params;
I am not sure this will be more efficient. joiner may be slowed down by
the fact that it is called with a chain result, which is slower on
front. But at leat you save yourself the heap-allocation of the params
array*.
I would use:
context ~= parameters.map!stringify().joiner(", ");
if (variadic) context ~= ", ...";
To make the best implementation would require to know how the String
context works.
*Note that here, stringify is not lazy, and thus allocates. It
could be a chain or a joiner, but I'm not sure the result would really
be more efficient.
Re: Why is std.algorithm so complicated to use?
On 10-Jul-12 19:00, Timon Gehr wrote: On 07/10/2012 02:53 PM, Dmitry Olshansky wrote: 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. What would sort do? Special case the result of map and then call schwartzSort on the underlying range? It may be a good idea actually. I once found myself in a need to sort mapped range. I think I just sorted original with "mapped" predicate it could get slow but in my case it was ok. Then assumeSorted(map!(...)). -- Dmitry Olshansky
Re: Why is std.algorithm so complicated to use?
On 07/10/2012 02:53 PM, Dmitry Olshansky wrote: 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. What would sort do? Special case the result of map and then call schwartzSort on the underlying range?
Re: Why is std.algorithm so complicated to use?
On 7/10/12 9:59 AM, H. S. Teoh wrote: 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. The idea there being that the compiler could give good details about what part of a complex constraint has failed. Andrei
Re: Why is std.algorithm so complicated to use?
On 7/10/12 10:26 AM, Andrei Alexandrescu wrote: 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 Actually I take that back. One may use uniq to remove duplicates in unsorted ranges. Andrei
Re: Why is std.algorithm so complicated to use?
On 10-Jul-12 17:59, H. S. Teoh wrote:
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.
Time and again I think of
T func(Blah)(Blah param)
if(isMagic!Blah, Blah.stringof~" is not magic") //second param is an
error hint
{
}
The idea is that when all functions from overload set fail to meet
constraints the error on "doesn't match template parameters" should
contain this extra HINTs on what's wrong.
HINT in general must be short, and clear. No need to do elobarate a
statements.
--
Dmitry Olshansky
Re: Why is std.algorithm so complicated to use?
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
Re: Why is std.algorithm so complicated to use?
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
Re: Why is std.algorithm so complicated to use?
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
Re: Why is std.algorithm so complicated to use?
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
Re: Why is std.algorithm so complicated to use?
On 7/10/12 8:27 AM, Simen Kjaeraas wrote: On Tue, 10 Jul 2012 09:04:31 +0200, Jonathan M Davis 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
Re: Why is std.algorithm so complicated to use?
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
Re: Why is std.algorithm so complicated to use?
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
Re: Why is std.algorithm so complicated to use?
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
Re: Why is std.algorithm so complicated to use?
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
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
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
Re: Why is std.algorithm so complicated to use?
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
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
