digitalmars.D - Add these to Phobos?
- "Mehrdad" <wfunction hotmail.com> Oct 15 2012
- "bearophile" <bearophileHUGS lycos.com> Oct 15 2012
- Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> Oct 15 2012
- "Mehrdad" <wfunction hotmail.com> Oct 15 2012
- "Jonathan M Davis" <jmdavisProg gmx.com> Oct 15 2012
- Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> Oct 17 2012
- Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> Oct 17 2012
- Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> Oct 17 2012
- "Mehrdad" <wfunction hotmail.com> Oct 15 2012
- "Jonathan M Davis" <jmdavisProg gmx.com> Oct 15 2012
- "Mehrdad" <wfunction hotmail.com> Oct 15 2012
- Jonathan M Davis <jmdavisProg gmx.com> Oct 15 2012
I think we need something like these in Phobos -- I was quite
surprised that I didn't find these in Phobos. They're really
handy in Python.
auto groupby(alias Key = k => k, alias Value = v => v, alias
Equal = (a, b) => a == b, R)(R range)
if (isInputRange!(R))
{
struct GroupBy
{
alias typeof(Key(R.init.front)) TKey;
R r;
property bool empty() { return this.r.empty; }
void popFront()
{
auto k = Key(this.r.front);
this.r.popFront();
while (!this.r.empty && Equal(k, Key(this.r.front)))
{ this.r.popFront(); }
}
property auto front()
{
TKey k = Key(this.r.front);
struct Grouper
{
TKey k;
R r;
property bool empty()
{ return this.r.empty || !Equal(this.k, Key(this.r.front)); }
void popFront() { this.r.popFront(); }
property auto front()
{ return Value(this.r.front); }
}
return Grouper(k, this.r);
}
static if (isForwardRange!(R))
{ property typeof(this) save() { return
typeof(this)(this.r.save()); } }
}
return GroupBy(range);
}
auto dict(R)(R range)
{
ElementType!(R)[typeof(ElementType!(R).init[0])] result;
foreach (t; range) { result[t[0]] = t /* or t[1]? */; }
return result;
}
auto sorted(alias F = q{a < b}, SwapStrategy S =
SwapStrategy.unstable, R)(R range)
{
auto arr = range.array();
arr.sort!(F, S)();
return arr;
}
Ideas?
Oct 15 2012
"bearophile" <bearophileHUGS lycos.com> Mehrdad:auto groupby(alias Key = k => k, alias Value = v => v, alias Equal = (a, b) => a == b, R)(R range) if (isInputRange!(R))
I have not studied the semantics of this groupby, but Phobos contains a std.algorithm.group that is not too much different from the Python itertools function (there are some differences, but they are often acceptable).auto dict(R)(R range) { ElementType!(R)[typeof(ElementType!(R).init[0])] result; foreach (t; range) { result[t[0]] = t /* or t[1]? */; } return result; }
There are various ways to design a similar function, and I think something similar is handy to have. I think I have already put an enhancement request for it in Bugzilla.auto sorted(alias F = q{a < b}, SwapStrategy S = SwapStrategy.unstable, R)(R range) { auto arr = range.array(); arr.sort!(F, S)(); return arr; }
http://d.puremagic.com/issues/show_bug.cgi?id=5076 Bye, bearophile
Oct 15 2012
On 10/15/12 5:35 PM, Mehrdad wrote:I think we need something like these in Phobos -- I was quite surprised that I didn't find these in Phobos. They're really handy in Python.
Ideas?
Yes, I wanted to add some relational operators forever! There's a group() function in std.algorithm but doesn't offer a range of ranges. Andrei
Oct 15 2012
On 10/15/12 7:39 PM, Mehrdad wrote:On Monday, 15 October 2012 at 22:35:41 UTC, Andrei Alexandrescu wrote:On 10/15/12 5:35 PM, Mehrdad wrote:I think we need something like these in Phobos -- I was quite surprised that I didn't find these in Phobos. They're really handy in Python.
Ideas?
Yes, I wanted to add some relational operators forever! There's a group() function in std.algorithm but doesn't offer a range of ranges. Andrei
+1 yeah, group() was useless for me. I wanted to group consecutive items together by some criterion, which it (ironically) explicitly doesn't do.
It's not ironic, it's intentional. In libraries such as Scala's you specify GroupBy with whatever predicate against an arbitrary stream, and it takes care of all the intermediate data structures (e.g. hashes, arrays) and/or additional operations (sorting). In D, there's a strong emphasis of explicit costs and benefits, so to group by an arbitrary key you'd first sort by that key and then use the "dumb group" that only knows how to group on adjacent entries. I'm not sure which approach is best, but I tend to think the current approach is a better fit for D's general ethos. Andrei
Oct 17 2012
On Monday, 15 October 2012 at 22:35:41 UTC, Andrei Alexandrescu wrote:On 10/15/12 5:35 PM, Mehrdad wrote:I think we need something like these in Phobos -- I was quite surprised that I didn't find these in Phobos. They're really handy in Python.
Ideas?
Yes, I wanted to add some relational operators forever! There's a group() function in std.algorithm but doesn't offer a range of ranges. Andrei
+1 yeah, group() was useless for me. I wanted to group consecutive items together by some criterion, which it (ironically) explicitly doesn't do.
Oct 15 2012
On Monday, October 15, 2012 23:35:59 Mehrdad wrote:auto sorted(alias F = q{a < b}, SwapStrategy S = SwapStrategy.unstable, R)(R range) { auto arr = range.array(); arr.sort!(F, S)(); return arr; }
What does this gain over sort? If you use sort auto result = sort(range); you get a SortedRange, which functions like find can take advantage of, and it's one line just like your sorted function. If you need a new array for it, then just call array. auto result = sort(array(range)); I don't see what your proposed function buys you. Is it just that you want to operate on the sorted array rather than a SortedRange? In that case, it's just auto arr = array(range); sort(arr); So, sorted would save you all of one line. Such a function seems incredibly lightweight to be adding it to the standard library. - Jonathan M Davis
Oct 15 2012
On 10/15/12 9:29 PM, Mehrdad wrote:Hmm, I didn't know 'sort' returns a value. That's very confusing since now I have no idea if it's mutating or not. Python has both sort and sorted, with clear meanings. (The goal was to make a non-mutating version that I could call functional.) Maybe we should clarify what sort exactly does and doesn't do...
std.algorithm operates in place wherever possible, and sort's result is a view on the same range as the original, but with new capabilities created by the sorting process. I think it's a very elegant design. Andrei
Oct 17 2012
On 10/15/12 9:47 PM, Jonathan M Davis wrote:And if SortedRange is changed to provide access to its underlying range via a member named source (it was recently suggested by Andrei that we should standardize on doing that where appropriate), then it could become a one- liner: auto result = sort(array(range)).source;
Yes, I think we should move toward the ".source" convention for all applicable ranges, e.g. retro.source yields the original range etc. Andrei
Oct 17 2012
On 10/15/12 10:35 PM, Mehrdad wrote:On Tuesday, 16 October 2012 at 01:47:58 UTC, Jonathan M Davis wrote:It should probably explain the rationale behind returning SortedRange so that it's much clearer as to why you'd want to use the return value rather than the original (now sorted) range.
+1 As it stands it's not at all clear from the documentation what the intention is, or how someone can go about sorting something without mutating it. Thanks for the responses.
Agreed. Part of the problem was that at the time I changed sort to return a value (it used to return void), severe compiler bugs forced me to take it out again for a while. So it's been "experimental" until it just silently started working and I forgot about it; and you know how documentation of experimental work goes... Regarding sorted(), one possibility would be to define a lazy sorting routine under that name or lazySort(). It would make for a better name than heap(), which implements the desired functionality. Andrei
Oct 17 2012
On Tuesday, 16 October 2012 at 00:42:55 UTC, Jonathan M Davis wrote:On Monday, October 15, 2012 23:35:59 Mehrdad wrote:auto sorted(alias F = q{a < b}, SwapStrategy S = SwapStrategy.unstable, R)(R range) { auto arr = range.array(); arr.sort!(F, S)(); return arr; }
What does this gain over sort? If you use sort auto result = sort(range); you get a SortedRange, which functions like find can take advantage of, and it's one line just like your sorted function. If you need a new array for it, then just call array. auto result = sort(array(range));
Hmm, I didn't know 'sort' returns a value. That's very confusing since now I have no idea if it's mutating or not. Python has both sort and sorted, with clear meanings. (The goal was to make a non-mutating version that I could call functional.) Maybe we should clarify what sort exactly does and doesn't do...
Oct 15 2012
On Tuesday, October 16, 2012 03:29:17 Mehrdad wrote:On Tuesday, 16 October 2012 at 00:42:55 UTC, Jonathan M Davis wrote:On Monday, October 15, 2012 23:35:59 Mehrdad wrote:auto sorted(alias F = q{a < b}, SwapStrategy S = SwapStrategy.unstable, R)(R range) { auto arr = range.array(); arr.sort!(F, S)(); return arr; }
What does this gain over sort? If you use sort auto result = sort(range); you get a SortedRange, which functions like find can take advantage of, and it's one line just like your sorted function. If you need a new array for it, then just call array. auto result = sort(array(range));
Hmm, I didn't know 'sort' returns a value. That's very confusing since now I have no idea if it's mutating or not. Python has both sort and sorted, with clear meanings. (The goal was to make a non-mutating version that I could call functional.) Maybe we should clarify what sort exactly does and doesn't do...
It sorts the range that's passed in and then returns a SortedRange which wraps the original range. The advantage of the SortedRange is that functions like find will then know that it's sorted and can take advantage of that, but if you just want to sort it, then just ignore the return value. The documentation could be clearer about the return type, but it _is_ listed as part of the signature. It should probably explain the rationale behind returning SortedRange so that it's much clearer as to why you'd want to use the return value rather than the original (now sorted) range. Regardless, if you want to sort a copy of a range but keep the same type, then all you have to do is auto newRange = array(range); sort(newRange); And if SortedRange is changed to provide access to its underlying range via a member named source (it was recently suggested by Andrei that we should standardize on doing that where appropriate), then it could become a one- liner: auto result = sort(array(range)).source; - Jonathan M Davis
Oct 15 2012
On Tuesday, 16 October 2012 at 01:47:58 UTC, Jonathan M Davis wrote:It should probably explain the rationale behind returning SortedRange so that it's much clearer as to why you'd want to use the return value rather than the original (now sorted) range.
+1 As it stands it's not at all clear from the documentation what the intention is, or how someone can go about sorting something without mutating it. Thanks for the responses.
Oct 15 2012
On Tuesday, October 16, 2012 03:47:43 Jonathan M Davis wrote:And if SortedRange is changed to provide access to its underlying range via a member named source (it was recently suggested by Andrei that we should standardize on doing that where appropriate), then it could become a one- liner: auto result = sort(array(range)).source;
Actually, it looks like SortedRange already provides access to the range that it wraps via release. It returns the wrapped range and removes it from the SortedRange, which is actually better than source, because if SortedRange had source, then it would be possible to make it so that it wasn't sorted anymore. In any case, that means that the one line becomes auto result = sort(array(range)).release(); - Jonathan M Davis
Oct 15 2012