std.partition is fucked

[Andrei Alexandrescu]

Sean Kelly wrote:
> == Quote from Andrei Alexandrescu (SeeWebsiteForEmail at erdani.org)'s article
>> Sean Kelly wrote:
>>> == Quote from Andrei Alexandrescu (SeeWebsiteForEmail at erdani.org)'s article
>>>> Sean Kelly wrote:
>>>>> Andrei Alexandrescu wrote:
>>>>>> Note how the left edge of result follows the left edge of r, but the
>>>>>> right edge stays put because partition() returns the right-hand-side
>>>>>> range. r shrinks from both ends to exhaustion.
>>>>> So all the elements that satisfy the predicate end up at the end of the
>>>>> original range instead of the beginning?  Was that an arbitrary choice,
>>>>> or is there a reason for it?
>>>> The elements satisfying the predicate are at the beginning, see e.g. the
>>>> unittests. The range returned is (as always) the right-hand side, i.e.
>>>> the range containing the elements that don't satisfy the predicate.
>>> Weird.  I'd always thought that the standard behavior was the opposite.
>>> That way partition could be passed a lessThan predicate and be used
>>> for sorting.  Though I guess you can just use a greaterThan predicate
>>> instead.
>> Nono, lessThan is a binary predicate whereas partition takes a unary
>> predicate. The spec of partition is very simple: do whatever the hell it
>> takes to put elements e that satisfy pred(e) before elements that don't.
>> If you follow the way std.sort uses partition, you'll see that it passes
>> a unary predicate that compares for less than against the chosen pivot.
> 
> Okay, I think we're talking at cross-purposes :-)  It seems we both agree
> that partition should place the elements satisfying pred before those that
> do not.  And I should have been more clear about pred being a unary
> function.  In any case, what I'm wondering is why partition returns the
> range representing the elements that do not satisfy pred.  When I call
> partition, wouldn't I be interested in the result containing the elements
> that have satisfied the supplied predicate?  Or does this cause problems
> for the sort routine.

Oh, now I understand. Sorry.

As a general rule, when it could return either the left or the right 
subrange of a range, functions in std.algorithm return the right range. 
This is because sentinel-terminated ranges cannot express the 
left-hand-side range.

Partition is in fact the perfect example because it works with forward 
ranges. If you want to partition a singly-linked list, you'd have to 
return the right-hand sublist. There's nothing else you could possibly 
return! If you wanted to return the left-hand sublist, you'd have to 
return a different type of range (something like "list up to this node").

So for generality's sake, whenever you have a choice, return the 
right-hand part of a range.

There is growing interest in defining additional ranges that express (at 
a cost) things like "the portion of a singly-linked list starting at 
node X and ending at node Y". For example, people want to do a find() 
and then deal with the portion _before_ the found element. I'd love to 
discuss that further, but I guess I'll have to wait for the d.next 
newsgroup. :oD


Andrei