View mode: basic / threaded / horizontal-split · Log in · Help
October 15, 2012
Add these to Phobos?
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?
October 15, 2012
Re: Add these to Phobos?
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
October 15, 2012
Re: Add these to Phobos?
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.
[snip]
> 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
October 15, 2012
Re: Add these to Phobos?
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.
> [snip]
>> 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.
October 16, 2012
Re: Add these to Phobos?
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
October 16, 2012
Re: Add these to Phobos?
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...
October 16, 2012
Re: Add these to Phobos?
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
October 16, 2012
Re: Add these to Phobos?
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.
October 16, 2012
Re: Add these to Phobos?
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
October 17, 2012
Re: Add these to Phobos?
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.
>> [snip]
>>> 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
« First   ‹ Prev
1 2
Top | Discussion index | About this forum | D home