www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Issue 4705

reply bearophile <bearophileHUGS lycos.com> writes:
I'd like to receive some comments from Andrei about one of the most nagging
problems I have with std.algorithm, it's not a big issue, but I bump my nose
against it few times every week:

http://d.puremagic.com/issues/show_bug.cgi?id=4705

If you have questions or doubts, feel free to ask here or in Bugzilla.

Bye,
bearophile
Sep 14 2011
next sibling parent reply travert phare.normalesup.org (Christophe) writes:
bearophile , dans le message (digitalmars.D:144513), a écrit :
 I'd like to receive some comments from Andrei about one of the most nagging
problems I have with std.algorithm, it's not a big issue, but I bump my nose
against it few times every week:
 
 http://d.puremagic.com/issues/show_bug.cgi?id=4705
 
 If you have questions or doubts, feel free to ask here or in Bugzilla.
 
 Bye,
 bearophile

min and max for ranges are good things to add. If min and max use a callable, it should be a less predicate, and max(item1, item2) should use a predicate too. A max!callable(range) that replaces max(map!collable(range)) is unuseful and confusing, since max should return one of the element passed in its arguments. mins and maxs are too specialized to be in phobos IMO. -- Christophe
Sep 15 2011
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 09/15/2011 11:44 AM, Christophe wrote:
 bearophile , dans le message (digitalmars.D:144513), a écrit :
 I'd like to receive some comments from Andrei about one of the most nagging
problems I have with std.algorithm, it's not a big issue, but I bump my nose
against it few times every week:

 http://d.puremagic.com/issues/show_bug.cgi?id=4705

 If you have questions or doubts, feel free to ask here or in Bugzilla.

 Bye,
 bearophile

min and max for ranges are good things to add. If min and max use a callable, it should be a less predicate, and max(item1, item2) should use a predicate too. A max!callable(range) that replaces max(map!collable(range)) is unuseful and confusing, since max should return one of the element passed in its arguments. mins and maxs are too specialized to be in phobos IMO.

Where do you draw the line? min and max for ranges are just reduce!min and reduce!max. What is "unuseful and confusing" about: max!"a.length"(range); ? Actually, I seldom want to take the maximum/minimum _without_ mapping the range first.
Sep 15 2011
parent reply travert phare.normalesup.org (Christophe) writes:
Timon Gehr , dans le message (digitalmars.D:144541), a écrit :
 On 09/15/2011 11:44 AM, Christophe wrote:
 bearophile , dans le message (digitalmars.D:144513), a écrit :
 I'd like to receive some comments from Andrei about one of the most nagging
problems I have with std.algorithm, it's not a big issue, but I bump my nose
against it few times every week:

 http://d.puremagic.com/issues/show_bug.cgi?id=4705

 If you have questions or doubts, feel free to ask here or in Bugzilla.

 Bye,
 bearophile

min and max for ranges are good things to add. If min and max use a callable, it should be a less predicate, and max(item1, item2) should use a predicate too. A max!callable(range) that replaces max(map!collable(range)) is unuseful and confusing, since max should return one of the element passed in its arguments. mins and maxs are too specialized to be in phobos IMO.

Where do you draw the line? min and max for ranges are just reduce!min and reduce!max.

Well, max(item1, item2) is just item1>item2?item1:item2 ... A line has to be drawn somewhere, depending of what people expect from a standard library. Then I'm just giving my opinion, depending on what I think people expect in a std library (which is biaised by what I expect from a std library...). What you say is true, and is an acceptable argument in favor of not including max for ranges. However: -min and max having been implemented in phobos for more that 2 arguments -the effect of min and max on ranges is obvious, so anyone implementing this function will implement it the same way, why not do it in phobos ?
 What is "unuseful and confusing" about:
 
 max!"a.length"(range); ?

What is confusing is that I don't know if this function returns a length, or one of the elements of the range. max compares elements two at a time and returns one of them. It seems (to me) more natural to give it a predicate to compare elements two at a time. This is what is used in c++ std lib. "less" predicates are very common in a std lib, so they should not surprise the user much. max!"a.length<b.length"(range); If that is too much of a surprise, then max should not take a callable. -- Christophe
Sep 15 2011
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Christophe:

 What is "unuseful and confusing" about:
 
 max!"a.length"(range); ?

What is confusing is that I don't know if this function returns a length, or one of the elements of the range.

In Python the max and min work this way, and the students I have taught Python don't see this as a problem. On the opposite, they are thankful for this feature.
 It seems 
 (to me) more natural to give it a predicate to compare elements two at a 
 time. This is what is used in c++ std lib.

It's less natural. And D is not C++, there are more than just C++ programmers in D. And it leads to longer & more complex code.
 "less" predicates are very 
 common in a std lib, so they should not surprise the user much.

In the standard library there is also a decorate-sort-undecorate sort too. Bye, bearophile
Sep 15 2011
next sibling parent reply Kagamin <spam here.lot> writes:
bearophile Wrote:

 Christophe:
 
 What is "unuseful and confusing" about:
 
 max!"a.length"(range); ?

What is confusing is that I don't know if this function returns a length, or one of the elements of the range.

In Python the max and min work this way, and the students I have taught Python don't see this as a problem. On the opposite, they are thankful for this feature.

maybe the name can be mappedMax!"a.length"(range); ?
Sep 15 2011
parent Kagamin <spam here.lot> writes:
Kagamin Wrote:

 maybe the name can be mappedMax!"a.length"(range); ?

This way schwartzSort can have an alias mappedSort. I agree, German is a bad choice to name functions.
Sep 15 2011
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/15/11 12:14 PM, Jonathan M Davis wrote:
 On Thursday, September 15, 2011 03:41 bearophile wrote:
 It seems
 (to me) more natural to give it a predicate to compare elements two at a
 time. This is what is used in c++ std lib.

It's less natural. And D is not C++, there are more than just C++ programmers in D. And it leads to longer& more complex code.

I think that that's up for debate. I would fully expect a min/max function to be using a comparator function, which means using a binary predicate. Also, given that everything else in std.algorithm which takes a predicate is taking an actually predicate and not what should be compared, having max take something like "a.length" would be extremely bizarre. I don't find max!"a.length"(range) to be natural at all. Maybe it's more natural for someone with little to no programming experience, but I really don't think that your average programmer is going to find it more natural. - Jonathan M Davis

I just realized argmax is exactly the name bearophile is looking for (http://en.wikipedia.org/wiki/Arg_max). I know, I'm awesome with names like that. We should add argmax to phobos. Andrei
Sep 15 2011
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 09/15/2011 07:48 PM, Jonathan M Davis wrote:
 On Thursday, September 15, 2011 10:39 Andrei Alexandrescu wrote:
 On 9/15/11 12:14 PM, Jonathan M Davis wrote:
 On Thursday, September 15, 2011 03:41 bearophile wrote:
 It seems
 (to me) more natural to give it a predicate to compare elements two at
 a time. This is what is used in c++ std lib.

It's less natural. And D is not C++, there are more than just C++ programmers in D. And it leads to longer& more complex code.

I think that that's up for debate. I would fully expect a min/max function to be using a comparator function, which means using a binary predicate. Also, given that everything else in std.algorithm which takes a predicate is taking an actually predicate and not what should be compared, having max take something like "a.length" would be extremely bizarre. I don't find max!"a.length"(range) to be natural at all. Maybe it's more natural for someone with little to no programming experience, but I really don't think that your average programmer is going to find it more natural. - Jonathan M Davis

I just realized argmax is exactly the name bearophile is looking for (http://en.wikipedia.org/wiki/Arg_max). I know, I'm awesome with names like that. We should add argmax to phobos.

If we're going to add it, that name works fine with me (though it should probably be argMax for proper camelcasing). I'd hate to see max work that way though. - Jonathan M Davis

It is written either arg max or argmax. Proper camel casing for the first one is argMax and for the second one argmax. Therefore it could go either way.
Sep 15 2011
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/16/11 1:24 PM, Simen Kjaeraas wrote:
 On Thu, 15 Sep 2011 19:14:24 +0200, Jonathan M Davis
 I think that that's up for debate. I would fully expect a min/max
 function to
 be using a comparator function, which means using a binary predicate.

This seems weird to me. min already has a binary predicate - a < b. This predicate is what defines min, any other predicate would make it a different function - usually reduce, unless we're talking about argMin (does argReduce make any kind of sense?). That said, there are cases where a < b is not enough, owing to some types not having a nice and simple comparison. Hence, binary predicates should also be allowed. I just feel that in the general case, binary predicates dilute the meaning of min/max. Would you consider this code good? min!"a > b"(range); That's not min, that's max. More: min!"a.member1 < b.member2"(range); Again, it's not min, it's something else.

This is a good argument. The "something else" is "extremum" (http://en.wikipedia.org/wiki/Maxima_and_minima). I suggest: * Introduce the algorithm "extremum" with a required predicate. * Introduce extremumCount and extremumPos, both with required predicate. * Keep minCount and minPos without a predicate. They'd in all likelihood use extremum. * Deprecate minCount and minPos with predicate (this is ouchworthy but I think it won't break a whole lot of code). * Introduce maxCount and maxPos without predicate. * Introduce min(range) and max(range) without predicate. * Introduce argmin and argmax with unary predicate. Andrei
Sep 16 2011
next sibling parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 16.09.2011 23:12, Andrei Alexandrescu wrote:
 On 9/16/11 1:24 PM, Simen Kjaeraas wrote:
 On Thu, 15 Sep 2011 19:14:24 +0200, Jonathan M Davis
 I think that that's up for debate. I would fully expect a min/max
 function to
 be using a comparator function, which means using a binary predicate.

This seems weird to me. min already has a binary predicate - a < b. This predicate is what defines min, any other predicate would make it a different function - usually reduce, unless we're talking about argMin (does argReduce make any kind of sense?). That said, there are cases where a < b is not enough, owing to some types not having a nice and simple comparison. Hence, binary predicates should also be allowed. I just feel that in the general case, binary predicates dilute the meaning of min/max. Would you consider this code good? min!"a > b"(range); That's not min, that's max. More: min!"a.member1 < b.member2"(range); Again, it's not min, it's something else.

This is a good argument. The "something else" is "extremum" (http://en.wikipedia.org/wiki/Maxima_and_minima). I suggest: * Introduce the algorithm "extremum" with a required predicate. * Introduce extremumCount and extremumPos, both with required predicate. * Keep minCount and minPos without a predicate. They'd in all likelihood use extremum. * Deprecate minCount and minPos with predicate (this is ouchworthy but I think it won't break a whole lot of code). * Introduce maxCount and maxPos without predicate. * Introduce min(range) and max(range) without predicate. * Introduce argmin and argmax with unary predicate.

Sounds good, as is minCount & minPos are bound to cause confusion. While extremum has the cognitive load of a special point (f' = 0 ?), yet not exactly min/max. -- Dmitry Olshansky
Sep 16 2011
prev sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 09/16/2011 09:12 PM, Andrei Alexandrescu wrote:
 On 9/16/11 1:24 PM, Simen Kjaeraas wrote:
 On Thu, 15 Sep 2011 19:14:24 +0200, Jonathan M Davis
 I think that that's up for debate. I would fully expect a min/max
 function to
 be using a comparator function, which means using a binary predicate.

This seems weird to me. min already has a binary predicate - a < b. This predicate is what defines min, any other predicate would make it a different function - usually reduce, unless we're talking about argMin (does argReduce make any kind of sense?). That said, there are cases where a < b is not enough, owing to some types not having a nice and simple comparison. Hence, binary predicates should also be allowed. I just feel that in the general case, binary predicates dilute the meaning of min/max. Would you consider this code good? min!"a > b"(range); That's not min, that's max. More: min!"a.member1 < b.member2"(range); Again, it's not min, it's something else.

This is a good argument. The "something else" is "extremum"

The "something else" is a "least element of a total order", or "min", but using a non-standard total order to extend the set of values to an ordered set. I don't think the argument is good. http://en.wikipedia.org/wiki/Total_order
 (http://en.wikipedia.org/wiki/Maxima_and_minima).

That is analysis. But the topic is discrete mathematics. I suggest:
 * Introduce the algorithm "extremum" with a required predicate.

What would that do? The range has more than one extremum if it is non-constant.
 * Introduce extremumCount and extremumPos, both with required predicate.

And those will be minCount+maxCount and merge(minPos,maxPos) ?
 * Keep minCount and minPos without a predicate. They'd in all likelihood
 use extremum.

How?
 * Deprecate minCount and minPos with predicate (this is ouchworthy but I
 think it won't break a whole lot of code).

 * Introduce maxCount and maxPos without predicate.

My suggestion: * Keep minCount and minPos with predicate. * Introduce maxCount and maxPos with predicate.
 * Introduce min(range) and max(range) without predicate.

A binary predicate would be fine. The terms min or max don't have any meanings without an ordering relation. Not giving the relation as an argument just makes the relation implicit.
 * Introduce argmin and argmax with unary predicate.

I think you meant an unary function. Timon
Sep 16 2011
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/16/11 3:16 PM, Timon Gehr wrote:
 On 09/16/2011 09:12 PM, Andrei Alexandrescu wrote:
 On 9/16/11 1:24 PM, Simen Kjaeraas wrote:
 On Thu, 15 Sep 2011 19:14:24 +0200, Jonathan M Davis
 I think that that's up for debate. I would fully expect a min/max
 function to
 be using a comparator function, which means using a binary predicate.

This seems weird to me. min already has a binary predicate - a < b. This predicate is what defines min, any other predicate would make it a different function - usually reduce, unless we're talking about argMin (does argReduce make any kind of sense?). That said, there are cases where a < b is not enough, owing to some types not having a nice and simple comparison. Hence, binary predicates should also be allowed. I just feel that in the general case, binary predicates dilute the meaning of min/max. Would you consider this code good? min!"a > b"(range); That's not min, that's max. More: min!"a.member1 < b.member2"(range); Again, it's not min, it's something else.

This is a good argument. The "something else" is "extremum"

The "something else" is a "least element of a total order"

Nope, because not the entire set is presented for the computation. Andrei
Sep 16 2011
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 09/16/2011 10:36 PM, Andrei Alexandrescu wrote:
 On 9/16/11 3:16 PM, Timon Gehr wrote:
 On 09/16/2011 09:12 PM, Andrei Alexandrescu wrote:
 On 9/16/11 1:24 PM, Simen Kjaeraas wrote:
 On Thu, 15 Sep 2011 19:14:24 +0200, Jonathan M Davis
 I think that that's up for debate. I would fully expect a min/max
 function to
 be using a comparator function, which means using a binary predicate.

This seems weird to me. min already has a binary predicate - a < b. This predicate is what defines min, any other predicate would make it a different function - usually reduce, unless we're talking about argMin (does argReduce make any kind of sense?). That said, there are cases where a < b is not enough, owing to some types not having a nice and simple comparison. Hence, binary predicates should also be allowed. I just feel that in the general case, binary predicates dilute the meaning of min/max. Would you consider this code good? min!"a > b"(range); That's not min, that's max. More: min!"a.member1 < b.member2"(range); Again, it's not min, it's something else.

This is a good argument. The "something else" is "extremum"

The "something else" is a "least element of a total order"

Nope, because not the entire set is presented for the computation. Andrei

The range defines the entire set we are looking at. What is your point?
Sep 16 2011
prev sibling next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 09/16/2011 10:35 PM, Simen Kjaeraas wrote:
 On Fri, 16 Sep 2011 22:16:59 +0200, Timon Gehr <timon.gehr gmx.ch> wrote:

 I suggest:

 * Introduce the algorithm "extremum" with a required predicate.

What would that do? The range has more than one extremum if it is non-constant.

extremum!"a<b"([1,2,3,1,2,3]) would be equal to [1,1].

That is not extremum. It is min.
 * Introduce extremumCount and extremumPos, both with required predicate.

And those will be minCount+maxCount and merge(minPos,maxPos) ?

Nope. extremumCount!"a<b"([1,2,3,1,2,3]) == 2.

There are 4 extrema: [1,3,1,3].
 extremumPos!"a>b"([1,2,3,1,2,3]) == [3,1,2,3].

Nope. extremumPos!"a>b"([1,2,3,1,2,3]) == [1,2,3,1,2,3], because 1 is an extremum.
 * Keep minCount and minPos without a predicate. They'd in all likelihood
 use extremum.

How?

alias extremumCount!"a<b" minCount; alias extremumPos!"a<b" minPos;

That won't work because it would also find maxima. The functions you describe are minCount and minPos.
Sep 16 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/16/11 3:54 PM, Timon Gehr wrote:
 On 09/16/2011 10:35 PM, Simen Kjaeraas wrote:
 On Fri, 16 Sep 2011 22:16:59 +0200, Timon Gehr <timon.gehr gmx.ch> wrote:

 I suggest:

 * Introduce the algorithm "extremum" with a required predicate.

What would that do? The range has more than one extremum if it is non-constant.

extremum!"a<b"([1,2,3,1,2,3]) would be equal to [1,1].


(BTW I thought of just returning the first found, so only 1.)
 That is not extremum. It is min.

Indeed extremum is not as good a name because it means an extreme value of a unary function over an interval. Extending this to relations is a bit forced. The example shows min, but the difficulty in finding a good name is that such a name would be meaningful in both of these cases: xyz!"a<b"([1,2,3,1,2,3]) is 1 xyz!"a>b"([1,2,3,1,2,3]) is 3 Question is what's a good name for xyz. It returns the element X of the range such that pred(E, X) is false for all E in the range. Then we'd defined xyzCount and xyzPos and call it a day. I agree with your point that it's the "minimum according to the order established by the predicate" but the fact of the matter is, "min" with an arbitrary predicate is bound to confuse people. I also thought of "bottom" from lattice theory, but that's also rather odd. So far my best candidates are "bound" and "limit". Andrei
Sep 16 2011
next sibling parent reply zeljkog <zeljkog private.com> writes:
On 16.09.2011 23:38, Andrei Alexandrescu wrote:
 xyz!"a<b"([1,2,3,1,2,3]) is 1

 xyz!"a>b"([1,2,3,1,2,3]) is 3

 Question is what's a good name for xyz.

Reduce, accumulate, fold...
Sep 16 2011
parent zeljkog <zeljkog private.com> writes:
On 16.09.2011 23:58, zeljkog wrote:
 On 16.09.2011 23:38, Andrei Alexandrescu wrote:
 xyz!"a<b"([1,2,3,1,2,3]) is 1

 xyz!"a>b"([1,2,3,1,2,3]) is 3

 Question is what's a good name for xyz.

Reduce, accumulate, fold...

I mean reduce!"a<b? a: b"
Sep 16 2011
prev sibling parent reply Mafi <mafi example.org> writes:
Am 16.09.2011 23:38, schrieb Andrei Alexandrescu:
 On 9/16/11 3:54 PM, Timon Gehr wrote:
 On 09/16/2011 10:35 PM, Simen Kjaeraas wrote:
 On Fri, 16 Sep 2011 22:16:59 +0200, Timon Gehr <timon.gehr gmx.ch>
 wrote:

 I suggest:

 * Introduce the algorithm "extremum" with a required predicate.

What would that do? The range has more than one extremum if it is non-constant.

extremum!"a<b"([1,2,3,1,2,3]) would be equal to [1,1].


(BTW I thought of just returning the first found, so only 1.)
 That is not extremum. It is min.

Indeed extremum is not as good a name because it means an extreme value of a unary function over an interval. Extending this to relations is a bit forced. The example shows min, but the difficulty in finding a good name is that such a name would be meaningful in both of these cases: xyz!"a<b"([1,2,3,1,2,3]) is 1 xyz!"a>b"([1,2,3,1,2,3]) is 3 Question is what's a good name for xyz. It returns the element X of the range such that pred(E, X) is false for all E in the range. Then we'd defined xyzCount and xyzPos and call it a day.

 Andrei

What about ultimum? It means the last or the outermost.
Sep 17 2011
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 09/17/2011 03:55 PM, Mafi wrote:
 Am 16.09.2011 23:38, schrieb Andrei Alexandrescu:
 On 9/16/11 3:54 PM, Timon Gehr wrote:
 On 09/16/2011 10:35 PM, Simen Kjaeraas wrote:
 On Fri, 16 Sep 2011 22:16:59 +0200, Timon Gehr <timon.gehr gmx.ch>
 wrote:

 I suggest:

 * Introduce the algorithm "extremum" with a required predicate.

What would that do? The range has more than one extremum if it is non-constant.

extremum!"a<b"([1,2,3,1,2,3]) would be equal to [1,1].


(BTW I thought of just returning the first found, so only 1.)
 That is not extremum. It is min.

Indeed extremum is not as good a name because it means an extreme value of a unary function over an interval. Extending this to relations is a bit forced. The example shows min, but the difficulty in finding a good name is that such a name would be meaningful in both of these cases: xyz!"a<b"([1,2,3,1,2,3]) is 1 xyz!"a>b"([1,2,3,1,2,3]) is 3 Question is what's a good name for xyz. It returns the element X of the range such that pred(E, X) is false for all E in the range. Then we'd defined xyzCount and xyzPos and call it a day.


That is the definition of a minimum. pred is the order relation and the range gives the set. Ergo xyz=min. But that is were we are.
 Andrei

What about ultimum? It means the last or the outermost.

As long as the function computes a least element, any names other than leastElem* or min* are just confusing. 'ultimum' is not specific enough. "Does it compute a least element or a greatest element?" The approach of having a name that includes both max and min cannot work in a satisfiable way for that reason.
Sep 17 2011
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 09/18/2011 09:38 PM, Simen Kjaeraas wrote:
 On Sat, 17 Sep 2011 16:06:44 +0200, Timon Gehr <timon.gehr gmx.ch> wrote:

 xyz!"a<b"([1,2,3,1,2,3]) is 1

 xyz!"a>b"([1,2,3,1,2,3]) is 3

 Question is what's a good name for xyz. It returns the element X of the
 range such that pred(E, X) is false for all E in the range. Then we'd
 defined xyzCount and xyzPos and call it a day.


That is the definition of a minimum. pred is the order relation and the range gives the set. Ergo xyz=min. But that is were we are.

Except that min does not mean 'apply this ordering to this set, and then do min on it' to most people.

It really should. I'd hate to see the custom predicate go away.
 Extremum is a better choice not because it
 better describes what it does, but precisely the opposite - people do not
 intuitively 'understand' it, and thus look it up.

If someone does not understand the point of the custom predicate, they will look up that too. The effect of having meaningless, or, as in this case, just plain wrong, function names is merely decreasing productivity, there are never positive implications.
 That said, I agree
 extremum is not a good name for xyz, but min is horrible.

min is not horrible, but good; it explains correctly what the function does. extremum does not, ergo it is horrible for all definitions of horrible function names known to me.
 What about ultimum? It means the last or the outermost.

As long as the function computes a least element, any names other than leastElem* or min* are just confusing. 'ultimum' is not specific enough. "Does it compute a least element or a greatest element?" The approach of having a name that includes both max and min cannot work in a satisfiable way for that reason.

Excepting of course the possibility that someone at some point might read the documentation...

feedMyDog(); That is a function that will do your laundry. If you don't remember the function name tomorrow, go look at the documentation (for reference, the function that will feed your dog is named stealMyUnderwear())
Sep 18 2011
prev sibling parent zeljkog <zeljkog private.com> writes:
On 16.09.2011 22:35, Simen Kjaeraas wrote:
 extremumCount!"a<b"([1,2,3,1,2,3]) == 2.
 extremumPos!"a>b"([1,2,3,1,2,3]) == [3,1,2,3].

and extremumEls!"a>b"([1,2,3,1,2,3]) == [3,3]
Sep 16 2011
prev sibling next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 09/16/2011 08:24 PM, Simen Kjaeraas wrote:
 On Thu, 15 Sep 2011 19:14:24 +0200, Jonathan M Davis
 <jmdavisProg gmx.com> wrote:

 On Thursday, September 15, 2011 03:41 bearophile wrote:
 Christophe:
 What is "unuseful and confusing" about:

 max!"a.length"(range); ?

What is confusing is that I don't know if this function returns a length, or one of the elements of the range.

In Python the max and min work this way, and the students I have taught Python don't see this as a problem. On the opposite, they are thankful for this feature.
 It seems
 (to me) more natural to give it a predicate to compare elements two

 time. This is what is used in c++ std lib.

It's less natural. And D is not C++, there are more than just C++ programmers in D. And it leads to longer & more complex code.

I think that that's up for debate. I would fully expect a min/max function to be using a comparator function, which means using a binary predicate.

This seems weird to me. min already has a binary predicate - a < b. This predicate is what defines min, any other predicate would make it a different function - usually reduce, unless we're talking about argMin (does argReduce make any kind of sense?). That said, there are cases where a < b is not enough, owing to some types not having a nice and simple comparison. Hence, binary predicates should also be allowed. I just feel that in the general case, binary predicates dilute the meaning of min/max. Would you consider this code good? min!"a > b"(range); That's not min, that's max.

That is min. But of a different ordered set. An ordered set is a pair of set and total order (a total order is a binary relation/binary predicate). Assume ElementType!Range == int then S=the set of range elements What you call min is a least element/minimum of (S,SLT). This is What you call max is a least element/minimum of (S,SGT) Where SLT/SGT denote the relations typically used to compute the order of signed integers. But both are minima. You basically just cannot compute a maximum with min!binary_predicate. You can compute it's value by finding the minimum of the reverse ordered set. But it is impossible to compute the maximum directly.
 More:
 min!"a.member1 < b.member2"(range);
 Again, it's not min, it's something else.

The same applies here. That IS min.
Sep 16 2011
prev sibling parent travert phare.normalesup.org (Christophe) writes:
"Simen Kjaeraas" , dans le message (digitalmars.D:144599), a écrit :
 That said, there are cases where a < b is not enough, owing to some
 types not having a nice and simple comparison. Hence, binary
 predicates should also be allowed. I just feel that in the general
 case, binary predicates dilute the meaning of min/max. Would you
 consider this code good?
      min!"a > b"(range);

Programers should know that the appropriate predicate for a comparison is the less function. If "a>b" is your less function, the the minimum of the range is indeed the maximum of the range ranked with the ordinary comparator, but it's still a minimum using this compararison function. Of course, writing min!"a>b" is not that good, because it is confusing, and the programmer should have used max!"a<b", but you cannot always prevent the programmer from doing stupid things. You can help him by providing max along with min so he does not have to do something like this. (and provide maxPos along with minPos). extremum would make me think both maximums and minimums are returned. -- Christophe
Sep 19 2011
prev sibling next sibling parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Thursday, September 15, 2011 03:41 bearophile wrote:
 Christophe:
 What is "unuseful and confusing" about:
 
 max!"a.length"(range); ?

What is confusing is that I don't know if this function returns a length, or one of the elements of the range.

In Python the max and min work this way, and the students I have taught Python don't see this as a problem. On the opposite, they are thankful for this feature.
 It seems
 (to me) more natural to give it a predicate to compare elements two at a
 time. This is what is used in c++ std lib.

It's less natural. And D is not C++, there are more than just C++ programmers in D. And it leads to longer & more complex code.

I think that that's up for debate. I would fully expect a min/max function to be using a comparator function, which means using a binary predicate. Also, given that everything else in std.algorithm which takes a predicate is taking an actually predicate and not what should be compared, having max take something like "a.length" would be extremely bizarre. I don't find max!"a.length"(range) to be natural at all. Maybe it's more natural for someone with little to no programming experience, but I really don't think that your average programmer is going to find it more natural. - Jonathan M Davis
Sep 15 2011
parent reply Kagamin <spam here.lot> writes:
Jonathan M Davis Wrote:

 I think that that's up for debate. I would fully expect a min/max function to 
 be using a comparator function, which means using a binary predicate.

1. how would they treat the function? 2. do you have a use case for a binary predicate?
Sep 16 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/16/11 4:33 AM, Kagamin wrote:
 Jonathan M Davis Wrote:

 I think that that's up for debate. I would fully expect a min/max function to
 be using a comparator function, which means using a binary predicate.

1. how would they treat the function? 2. do you have a use case for a binary predicate?

I was thinking along the lines of e.g. icmp(a, b) < 0 for a case-insensitive compare. I don't know offhand how to do the same with a mapper without copying strings. Anyhow, min and max with a mapper sounds worth looking into. Andrei
Sep 16 2011
parent Kagamin <spam here.lot> writes:
Andrei Alexandrescu Wrote:

 On 9/16/11 4:33 AM, Kagamin wrote:
 Jonathan M Davis Wrote:

 I think that that's up for debate. I would fully expect a min/max function to
 be using a comparator function, which means using a binary predicate.

1. how would they treat the function? 2. do you have a use case for a binary predicate?

I was thinking along the lines of e.g. icmp(a, b) < 0 for a case-insensitive compare. I don't know offhand how to do the same with a mapper without copying strings.

OK, one use case. I suppose this is needed rarely so it can be factored to another function or idiom. BTW case-insensitive comparison is a good candidate to be built into the underlying collection, e.g. AA.
Sep 19 2011
prev sibling next sibling parent "Simen Kjaeraas" <simen.kjaras gmail.com> writes:
On Thu, 15 Sep 2011 19:14:24 +0200, Jonathan M Davis <jmdavisProg gmx.com>  
wrote:

 On Thursday, September 15, 2011 03:41 bearophile wrote:
 Christophe:
 What is "unuseful and confusing" about:

 max!"a.length"(range); ?

What is confusing is that I don't know if this function returns a length, or one of the elements of the range.

In Python the max and min work this way, and the students I have taught Python don't see this as a problem. On the opposite, they are thankful for this feature.
 It seems
 (to me) more natural to give it a predicate to compare elements two  

 time. This is what is used in c++ std lib.

It's less natural. And D is not C++, there are more than just C++ programmers in D. And it leads to longer & more complex code.

I think that that's up for debate. I would fully expect a min/max function to be using a comparator function, which means using a binary predicate.

This seems weird to me. min already has a binary predicate - a < b. This predicate is what defines min, any other predicate would make it a different function - usually reduce, unless we're talking about argMin (does argReduce make any kind of sense?). That said, there are cases where a < b is not enough, owing to some types not having a nice and simple comparison. Hence, binary predicates should also be allowed. I just feel that in the general case, binary predicates dilute the meaning of min/max. Would you consider this code good? min!"a > b"(range); That's not min, that's max. More: min!"a.member1 < b.member2"(range); Again, it's not min, it's something else. -- Simen
Sep 16 2011
prev sibling next sibling parent "Simen Kjaeraas" <simen.kjaras gmail.com> writes:
On Fri, 16 Sep 2011 22:16:59 +0200, Timon Gehr <timon.gehr gmx.ch> wrote:

 I suggest:

 * Introduce the algorithm "extremum" with a required predicate.

What would that do? The range has more than one extremum if it is non-constant.

extremum!"a<b"([1,2,3,1,2,3]) would be equal to [1,1].
 * Introduce extremumCount and extremumPos, both with required predicate.

And those will be minCount+maxCount and merge(minPos,maxPos) ?

Nope. extremumCount!"a<b"([1,2,3,1,2,3]) == 2. extremumPos!"a>b"([1,2,3,1,2,3]) == [3,1,2,3].
 * Keep minCount and minPos without a predicate. They'd in all likelihood
 use extremum.

How?

alias extremumCount!"a<b" minCount; alias extremumPos!"a<b" minPos; -- Simen
Sep 16 2011
prev sibling next sibling parent "Simen Kjaeraas" <simen.kjaras gmail.com> writes:
------------pEUoe7C8eIDkulsALAqxG4
Content-Type: text/plain; charset=utf-8; format=flowed; delsp=yes
Content-Transfer-Encoding: 7bit

On Fri, 16 Sep 2011 23:38:35 +0200, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:

 extremum!"a<b"([1,2,3,1,2,3]) would be equal to [1,1].


(BTW I thought of just returning the first found, so only 1.)

Will there then be a different version (extremumArg?) that does return a range? Consider bearophile's example of min!"a.length" - it is not unlikely there will be several elements with an equal length. A corner case: extremum!"a<0"([1]) == ??? Does this throw? If so, how do we determine that? I implemented the functions as I have understood them, and attached them to this post. Permission is given to use this code in any way desired, at own risk. (WTF license or less limiting) Note that I have chosen to use the name extremum in the absense of better options. -- Simen ------------pEUoe7C8eIDkulsALAqxG4 Content-Disposition: attachment; filename=extremum.d Content-Type: application/octet-stream; name="extremum.d" Content-Transfer-Encoding: Base64 77u/aW1wb3J0IHN0ZC5yYW5nZTsKaW1wb3J0IHN0ZC5mdW5jdGlvbmFsOwppbXBv cnQgc3RkLmFycmF5OwppbXBvcnQgY29yZS5leGNlcHRpb247CmltcG9ydCBzdGQu ZXhjZXB0aW9uOwppbXBvcnQgc3RkLnR5cGVjb25zOwoKLyoqCiAqIFJldHVybnMg dGhlIG1vc3QgZXh0cmVtZSB2YWx1ZSBhcyB3ZWxsIGFzIHRoZSBudW1iZXIgb2Yg aXRlbXMgaW4gJChEIHJhbmdlKSBtYXRjaGluZyB0aGUgbW9zdAogKiBleHRyZW1l IHZhbHVlLCBhcyBkZWNpZGVkIGJ5IHRoZSBwcmVkaWNhdGUgJChEIHByZWQpLiBX aWxsIHJldHVybiAwIGZvciBlbXB0eSByYW5nZXMsIDEgb3IgbW9yZQogKiBmb3Ig cmFuZ2VzIG9mIG9uZSBvciBtb3JlIGl0ZW1zLgotLS0tCmFzc2VydCggZXh0cmVt dW1Db3VudCEiYTxiIiggWzEsIDIsIDMsIDEsIDIsIDNdICkgPT0gMiApOwphc3Nl cnQoIGV4dHJlbXVtQ291bnQhImEubGVuZ3RoPGIubGVuZ3RoIiggWyJhIiwgImJj IiwgImRlIiwgImZnIl0gKSA9PSAxICk7Ci0tLS0KICovClR1cGxlISggRWxlbWVu dFR5cGUhUmFuZ2UsIHNpemVfdCApIGV4dHJlbXVtQ291bnQoIGFsaWFzIHByZWQs IFJhbmdlICkoIFJhbmdlIHJhbmdlICkgaWYgKCBpc0lucHV0UmFuZ2UhUmFuZ2Ug KSB7CglhbGlhcyBiaW5hcnlGdW4hcHJlZCBmbjsKCQoJaWYgKCByYW5nZS5lbXB0 eSApIHsKCQlyZXR1cm4gdHlwZW9mKHJldHVybikoIEVsZW1lbnRUeXBlISggUmFu Z2UgKS5pbml0LCAwKTsKCX0KCQoJc2l6ZV90IHJlc3VsdCA9IDE7CgkKCUVsZW1l bnRUeXBlIVJhbmdlIGV4dHJlbWVFbGVtZW50ID0gcmFuZ2UuZnJvbnQ7CglyYW5n ZS5wb3BGcm9udCggKTsKCQoJZm9yZWFjaCAoIGU7IHJhbmdlICkgewoJCWlmICgg Zm4oIGUsIGV4dHJlbWVFbGVtZW50ICkgKSB7CgkJCWV4dHJlbWVFbGVtZW50ID0g ZTsKCQkJcmVzdWx0ID0gMTsKCQl9IGVsc2UgaWYgKCAhZm4oIGV4dHJlbWVFbGVt ZW50LCBlICkgKSB7CgkJCXJlc3VsdCsrOwoJCX0KCX0KCQoJcmV0dXJuIHR1cGxl KCBleHRyZW1lRWxlbWVudCwgcmVzdWx0ICk7Cn0KCnVuaXR0ZXN0IHsKCWFzc2Vy dCggZXh0cmVtdW1Db3VudCEiYTxiIiggWzEsIDIsIDMsIDEsIDIsIDNdICkgPT0g dHVwbGUoIDEsIDIgKSApOwoJYXNzZXJ0KCBleHRyZW11bUNvdW50ISJhPmIiKCBb MSwgMiwgMywgMSwgMiwgM10gKSA9PSB0dXBsZSggMywgMiApICk7Cglhc3NlcnQo IGV4dHJlbXVtQ291bnQhImE+YiIoIG5ldyBpbnRbMF0gKSA9PSB0dXBsZSggMCwg MCApICk7Cglhc3NlcnQoIGV4dHJlbXVtQ291bnQhImEubGVuZ3RoPGIubGVuZ3Ro IiggWyJhIiwgImJjIiwgImRlIiwgImZnIl0gKSA9PSB0dXBsZSggImEiLCAxICkg KTsKCWFzc2VydCggZXh0cmVtdW1Db3VudCEiYS5sZW5ndGg+Yi5sZW5ndGgiKCBb ImEiLCAiYmMiLCAiZCIsICJlZiJdICkgPT0gdHVwbGUoICJiYyIsIDIgKSApOwp9 CgovKioKICogUmV0dXJucyB0aGUgcG9zaXRpb24gb2YgdGhlIGVsZW1lbnQgb2Yg dGhlIG1vc3QgZXh0cmVtZSB2YWx1ZSBpbiB0aGUgZm9yd2FyZCByYW5nZSAkKEQg cmFuZ2UpLCBhcwogKiBkZWNpZGVkIGJ5IHRoZSBwcmVkaWNhdGUgJChEIHByZWQp LgogKiBpLmUuIGEgIHN1YnJhbmdlIG9mICQoRCByYW5nZSkgc3RhcnRpbmcgYXQg dGhlIHBvc2l0aW9uIG9mIHRoZSBlbGVtZW50IG9mIHRoZSBtb3N0IGV4dHJlbWUg dmFsdWUKICogYW5kIHdpdGggdGhlIHNhbWUgZW5kaW5nIGFzICQoRCByYW5nZSku Ci0tLS0KYXNzZXJ0KCBleHRyZW11bVBvcyEiYTxiIiggWzEsIDIsIDMsIDEsIDIs IDNdICkgPT0gWzEsIDIsIDMsIDEsIDIsIDNdICk7CmFzc2VydCggZXh0cmVtdW1Q b3MhImE+YiIoIFsxLCAyLCAzLCAxLCAyLCAzXSApID09IFszLCAxLCAyLCAzXSAp OwotLS0tCiAqLwpSYW5nZSBleHRyZW11bVBvcyggYWxpYXMgcHJlZCwgUmFuZ2Ug KSggUmFuZ2UgcmFuZ2UgKSBpZiAoIGlzRm9yd2FyZFJhbmdlIVJhbmdlICkgewoJ YWxpYXMgYmluYXJ5RnVuIXByZWQgZm47CgkKCWlmICggcmFuZ2UuZW1wdHkgKSB7 CgkJcmV0dXJuIHJhbmdlOwoJfQoJCglSYW5nZSByZXN1bHQgPSByYW5nZS5zYXZl KCApOwoJCglmb3IgKCA7ICFyYW5nZS5lbXB0eTsgcmFuZ2UucG9wRnJvbnQoICkp IHsKCQlpZiAoIGZuKCByYW5nZS5mcm9udCwgcmVzdWx0LmZyb250ICkgJiYgIWZu KCByZXN1bHQuZnJvbnQsIHJhbmdlLmZyb250ICkgKSB7CgkJCXJlc3VsdCA9IHJh bmdlLnNhdmUoICk7CgkJfQoJfQoJCglyZXR1cm4gcmVzdWx0Owp9Cgp1bml0dGVz dCB7Cglhc3NlcnQoIGV4dHJlbXVtUG9zISJhPGIiKCBbMSwgMiwgMywgMSwgMiwg M10gKSA9PSBbMSwgMiwgMywgMSwgMiwgM10gKTsKCWFzc2VydCggZXh0cmVtdW1Q b3MhImE+YiIoIFsxLCAyLCAzLCAxLCAyLCAzXSApID09IFszLCAxLCAyLCAzXSAp Owp9CgovKioKICogUmV0dXJucyBhbiBhcnJheSBvZiBhbGwgdGhlIGVsZW1lbnRz IG9mICQoRCByYW5nZSkgbWF0Y2hpbmcgdGhlIG1vc3QgZXh0cmVtZSB2YWx1ZSwg YXMKICogZGV0ZXJtaW5lZCBieSB0aGUgcHJlZGljYXRlICQoRCBwcmVkKS4gV2ls bCByZXR1cm4gMCBmb3IgZW1wdHkgcmFuZ2VzLCAxIG9yIG1vcmUgZm9yIG5vbi1l bXB0eS4KLS0tLQphc3NlcnQoIGV4dHJlbXVtQXJnISJhLmxlbmd0aDxiLmxlbmd0 aCIoIFsiYSIsICJiYyIsICJkIiwgImVmIl0gKSA9PSBbImEiLCAiZCJdICk7CmFz c2VydCggZXh0cmVtdW1BcmchImE8YiIoIG5ldyBpbnRbMF0gKSA9PSBbXSApOwph c3NlcnQoIGV4dHJlbXVtQXJnISJhPGIiKCBbMSwgMiwgMywgMSwgMiwgM10gKSA9 PSBbMSwgMV0gKTsKLS0tLQogKi8KRWxlbWVudFR5cGUhUmFuZ2VbXSBleHRyZW11 bUFyZyggYWxpYXMgcHJlZCwgUmFuZ2UgKSggUmFuZ2UgcmFuZ2UgKSBpZiAoIGlz SW5wdXRSYW5nZSFSYW5nZSApIHsKCWFsaWFzIGJpbmFyeUZ1biFwcmVkIGZuOwoJ CglpZiAoIHJhbmdlLmVtcHR5ICkgewoJCXJldHVybiBbXTsKCX0KCQoJYXV0byBy ZXN1bHQgPSBBcHBlbmRlciEoIEVsZW1lbnRUeXBlISggUmFuZ2UgKVtdICkoICk7 CglyZXN1bHQucHV0KCByYW5nZS5mcm9udCApOwoJcmFuZ2UucG9wRnJvbnQoICk7 CgkKCWZvcmVhY2ggKCBlOyByYW5nZSApIHsKCQlpZiAoIGZuKCBlLCByZXN1bHQu ZGF0YVswXSApICkgewoJCQlyZXN1bHQuY2xlYXIoICk7CgkJCXJlc3VsdC5wdXQo IGUgKTsKCQl9IGVsc2UgaWYgKCAhZm4oIHJlc3VsdC5kYXRhWzBdLCBlICkgKSB7 CgkJCXJlc3VsdC5wdXQoIGUgKTsKCQl9Cgl9CgkKCXJldHVybiByZXN1bHQuZGF0 YTsKfQoKdW5pdHRlc3QgewoJYXNzZXJ0KCBleHRyZW11bUFyZyEiYS5sZW5ndGg8 Yi5sZW5ndGgiKCBbImEiLCAiYmMiLCAiZCIsICJlZiJdICkgPT0gWyJhIiwgImQi XSApOwoJYXNzZXJ0KCBleHRyZW11bUFyZyEiYS5sZW5ndGg+Yi5sZW5ndGgiKCBb ImEiLCAiYmMiLCAiZCIsICJlZiJdICkgPT0gWyJiYyIsICJlZiJdICk7Cglhc3Nl cnQoIGV4dHJlbXVtQXJnISJhPGIiKCBbMSwyLDNdICkgPT0gWzFdICk7Cglhc3Nl cnQoIGV4dHJlbXVtQXJnISJhPGIiKCBuZXcgaW50WzBdICkgPT0gW10gKTsKCWFz c2VydCggZXh0cmVtdW1BcmchImE8YiIoIFsxLCAyLCAzLCAxLCAyLCAzXSApID09 IFsxLCAxXSApOwoJYXNzZXJ0KCBleHRyZW11bUFyZyEiYT5iIiggWzEsIDIsIDMs IDEsIDIsIDNdICkgPT0gWzMsIDNdICk7Cglhc3NlcnQoIGV4dHJlbXVtQXJnISIo YXwxKT4oYnwxKSIoIFsxLCAyLCAzLCAxLCAyLCAzXSApID09IFsyLCAzLCAyLCAz XSApOwp9CgovKioKICogUmV0dXJucyB0aGUgZmlyc3QgZWxlbWVudCBvZiAkKEQg cmFuZ2UpIHdpdGggdGhlIG1vc3QgZXh0cmVtZSB2YWx1ZSwgYXMgZGV0ZXJtaW5l ZCBieQogKiAkKEQgcHJlZCkuCiAqIEFuIGV4Y2VwdGlvbiBpcyB0aHJvd24gaWYg JChEIHJhbmdlKSBpcyBlbXB0eS4KLS0tLQphc3NlcnQoIGV4dHJlbXVtISJhPGIi KFsxLDIsM10pID09IDEgKTsKYXNzZXJ0KCBleHRyZW11bSEiYTxiIihbMSwyLDMs MSwyLDNdKSA9PSAxICk7Ci0tLS0KICovCkVsZW1lbnRUeXBlIVJhbmdlIGV4dHJl bXVtKCBhbGlhcyBwcmVkLCBSYW5nZSApKCBSYW5nZSByYW5nZSApIGlmICggaXNJ bnB1dFJhbmdlIVJhbmdlICkgewoJYWxpYXMgYmluYXJ5RnVuIXByZWQgZm47CgkK CWlmICggcmFuZ2UuZW1wdHkgKSB7CgkJdGhyb3cgbmV3IFJhbmdlRXJyb3IoIlJh bmdlIHZpb2xhdGlvbiIpOwoJfQoJCglFbGVtZW50VHlwZSFSYW5nZSByZXN1bHQg PSByYW5nZS5mcm9udDsKCXJhbmdlLnBvcEZyb250KCApOwoJCglmb3JlYWNoICgg ZTsgcmFuZ2UgKSB7CgkJaWYgKCBmbiggZSwgcmVzdWx0ICkgKSB7CgkJCXJlc3Vs dCA9IGU7CgkJfQoJfQoJCglyZXR1cm4gcmVzdWx0Owp9Cgp1bml0dGVzdCB7Cglh c3NlcnQoIGV4dHJlbXVtISJhPGIiKFsxLDIsM10pID09IDEgKTsKCWFzc2VydCgg ZXh0cmVtdW0hImE8YiIoWzEsMiwzLDEsMiwzXSkgPT0gMSApOwoJYXNzZXJ0KCBl eHRyZW11bSEiYS5sZW5ndGg+Yi5sZW5ndGgiKCBbImEiLCAiYmMiLCAiZCIsICJl ZiJdICkgPT0gImJjIiApOwoJYXNzZXJ0VGhyb3duIVJhbmdlRXJyb3IoIGV4dHJl bXVtISJhPGIiKCBuZXcgaW50WzBdICkgKTsKfQoKLyoqCiAqIFJldHVybnMgYW4g YXJyYXkgb2YgYWxsIG1pbmltYWwgZWxlbWVudHMgb2YgJChEIHJhbmdlKSwgb3B0 aW9uYWxseSBkZXRlcm1pbmVkIGJ5IHRoZSB1bmFyeQogKiBmdW5jdGlvbiAkKEQg ZnVuKS4KLS0tLQphc3NlcnQoIG1pbkFyZyggWzEsIDIsIDMsIDEsIDIsIDNdICkg PT0gWzEsIDFdICk7CmFzc2VydCggbWluQXJnISIzIC0gYS5sZW5ndGgiKCBbImFi IiwgImMiLCAiZGUiLCAiZiJdICkgPT0gWyJhYiIsICJkZSJdICk7CmFzc2VydCgg bWluQXJnKCJCYW5hbmFzIikgPT0gIkIiICk7Ci0tLS0KICovCkVsZW1lbnRUeXBl IVJhbmdlW10gbWluQXJnKCBSYW5nZSApKCBSYW5nZSByYW5nZSApIGlmICggaXNJ bnB1dFJhbmdlIVJhbmdlICkgewoJcmV0dXJuIGV4dHJlbXVtQXJnISJhPGIiKCBy YW5nZSApOwp9CgpFbGVtZW50VHlwZSFSYW5nZVtdIG1pbkFyZyggYWxpYXMgZnVu LCBSYW5nZSApKCBSYW5nZSByYW5nZSApIGlmICggaXNJbnB1dFJhbmdlIVJhbmdl ICkgewoJYWxpYXMgdW5hcnlGdW4hZnVuIGZuOwoJLy9yZXR1cm4gZXh0cmVtdW1B cmchKCAoIGEsIGIgKXsgcmV0dXJuIGZuKCBhICkgPCBmbiggYiApOyB9ICkoIHJh bmdlICk7IC8vIEJ1Zy4KCQoJYXV0byBmbjIgPSAoIEVsZW1lbnRUeXBlIVJhbmdl IGEsIEVsZW1lbnRUeXBlIVJhbmdlIGIgKXsgcmV0dXJuIGZuKCBhICkgPCBmbigg YiApOyB9OwoJcmV0dXJuIGV4dHJlbXVtQXJnIWZuMiggcmFuZ2UgKTsKfQoKdW5p dHRlc3QgewoJYXNzZXJ0KCBtaW5BcmcoIFsxLCAyLCAzLCAxLCAyLCAzXSApID09 IFsxLCAxXSApOwoJYXNzZXJ0KCBtaW5BcmchImEiKCBbMSwgMiwgMywgMSwgMiwg M10gKSA9PSBbMSwgMV0gKTsKCWFzc2VydCggbWluQXJnKCBbImEiLCAiYmMiLCAi YyIsICJkZSJdICkgPT0gWyJhIl0gKTsKCWFzc2VydCggbWluQXJnISJhLmxlbmd0 aCIoIFtbMV0sIFsyXSwgWzMsNF0sIFs1LDZdXSApID09IFtbMV0sIFsyXV0gKTsK CWFzc2VydCggbWluQXJnISIzIC0gYS5sZW5ndGgiKCBbImFiIiwgImMiLCAiZGUi LCAiZiJdICkgPT0gWyJhYiIsICJkZSJdICk7Cglhc3NlcnQoIG1pbkFyZygiYmFu YW5hcyIpID09ICJhYWEiICk7Cglhc3NlcnQoIG1pbkFyZygiQmFuYW5hcyIpID09 ICJCIiApOwp9CgovKioKICogUmV0dXJucyB0aGUgbWluaW1hbCBlbGVtZW50IG9m ICQoRCByYW5nZSksIG9wdGlvbmFsbHkgZGV0ZXJtaW5lZCBieSB0aGUgdW5hcnkg ZnVuY3Rpb24gJChEIGZ1bikuCi0tLS0KYXNzZXJ0KCBtaW4oIFsiYSIsICJiYyIs ICJjIiwgImRlIl0gKSA9PSAiYSIgKTsKYXNzZXJ0KCBtaW4hImEubGVuZ3RoIigg W1sxXSwgWzJdLCBbMyw0XSwgWzUsNl1dICkgPT0gWzFdICk7Ci0tLS0KICovCkVs ZW1lbnRUeXBlIVJhbmdlIG1pbiggUmFuZ2UgKSggUmFuZ2UgcmFuZ2UgKSBpZiAo IGlzSW5wdXRSYW5nZSFSYW5nZSApIHsKCXJldHVybiBleHRyZW11bSEiYTxiIigg cmFuZ2UgKTsKfQoKRWxlbWVudFR5cGUhUmFuZ2UgbWluKCBhbGlhcyBmdW4sIFJh bmdlICkoIFJhbmdlIHJhbmdlICkgaWYgKCBpc0lucHV0UmFuZ2UhUmFuZ2UgKSB7 CglhbGlhcyB1bmFyeUZ1biFmdW4gZm47CgkvL3JldHVybiBleHRyZW11bSEoICgg YSwgYiApeyByZXR1cm4gZm4oIGEgKSA8IGZuKCBiICk7IH0gKSggcmFuZ2UgKTsg Ly8gQnVnLgoJCglhdXRvIGZuMiA9ICggRWxlbWVudFR5cGUhUmFuZ2UgYSwgRWxl bWVudFR5cGUhUmFuZ2UgYiApeyByZXR1cm4gZm4oIGEgKSA8IGZuKCBiICk7IH07 CglyZXR1cm4gZXh0cmVtdW0hZm4yKCByYW5nZSApOwp9Cgp1bml0dGVzdCB7Cglh c3NlcnQoIG1pbiggWzEsIDIsIDMsIDEsIDIsIDNdICkgPT0gMSk7Cglhc3NlcnQo IG1pbiEiYSIoIFsxLCAyLCAzLCAxLCAyLCAzXSApID09IDEgKTsKCWFzc2VydCgg bWluKCBbImEiLCAiYmMiLCAiYyIsICJkZSJdICkgPT0gImEiICk7Cglhc3NlcnQo IG1pbiEiYS5sZW5ndGgiKCBbWzFdLCBbMl0sIFszLDRdLCBbNSw2XV0gKSA9PSBb MV0gKTsKCWFzc2VydCggbWluISIzIC0gYS5sZW5ndGgiKCBbImFiIiwgImMiLCAi ZGUiLCAiZiJdICkgPT0gImFiIiApOwoJYXNzZXJ0KCBtaW4oImJhbmFuYXMiKSA9 PSAnYScgKTsKCWFzc2VydCggbWluKCJCYW5hbmFzIikgPT0gJ0InICk7Cn0KCi8q KgogKiBSZXR1cm5zIHRoZSBtaW5pbWFsIGVsZW1lbnQgb2YgJChEIHJhbmdlKSwg YWxvbmcgd2l0aCB0aGUgbnVtYmVyIG9mIG9jY3VyZW5jZXMuIFRoZSBtaW5pbWFs CiAqIGVsZW1lbnQgbWF5IG9wdGlvbmFsbHkgYmUgZGV0ZXJtaW5lZCBieSB0aGUg dW5hcnkgZnVuY3Rpb24gJChEIGZ1bikuCi0tLS0KYXNzZXJ0KCBtaW5Db3VudCgg WzEsIDIsIDMsIDEsIDJdICkgPT0gdHVwbGUoIDEsIDIgKSApOwphc3NlcnQoIG1p bkNvdW50KCAiYmFuYW5hcyIgKSA9PSB0dXBsZSggJ2EnLCAzICkgKTsKLS0tLQog Ki8KVHVwbGUhKCBFbGVtZW50VHlwZSFSYW5nZSwgc2l6ZV90ICkgbWluQ291bnQo IFJhbmdlICkoIFJhbmdlIHJhbmdlICkgaWYgKCBpc0lucHV0UmFuZ2UhUmFuZ2Ug KSB7CglyZXR1cm4gZXh0cmVtdW1Db3VudCEiYTxiIiggcmFuZ2UgKTsKfQoKVHVw bGUhKCBFbGVtZW50VHlwZSFSYW5nZSwgc2l6ZV90ICkgbWluQ291bnQoIGFsaWFz IGZ1biwgUmFuZ2UgKSggUmFuZ2UgcmFuZ2UgKSBpZiAoIGlzSW5wdXRSYW5nZSFS YW5nZSApIHsKCWFsaWFzIHVuYXJ5RnVuIWZ1biBmbjsKCS8vcmV0dXJuIGV4dHJl bXVtISggKCBhLCBiICl7IHJldHVybiBmbiggYSApIDwgZm4oIGIgKTsgfSApKCBy YW5nZSApOyAvLyBCdWcuCgkKCWF1dG8gZm4yID0gKCBFbGVtZW50VHlwZSFSYW5n ZSBhLCBFbGVtZW50VHlwZSFSYW5nZSBiICl7IHJldHVybiBmbiggYSApIDwgZm4o IGIgKTsgfTsKCXJldHVybiBleHRyZW11bUNvdW50IWZuMiggcmFuZ2UgKTsKfQoK dW5pdHRlc3QgewoJYXNzZXJ0KCBtaW5Db3VudCggWzEsIDIsIDMsIDEsIDJdICkg PT0gdHVwbGUoIDEsIDIgKSApOwoJYXNzZXJ0KCBtaW5Db3VudCggImJhbmFuYXMi ICkgPT0gdHVwbGUoICdhJywgMyApICk7Cglhc3NlcnQoIG1pbkNvdW50KCAiIiAp ID09IHR1cGxlKCBkY2hhci5pbml0LCAwICkgKTsKCWFzc2VydCggbWluQ291bnQh ImEubGVuZ3RoIiggWyJhIiwgImJjIiwgImQiLCAiZWYiXSApID09IHR1cGxlKCAi YSIsIDIgKSApOwp9CgovKioKICogUmV0dXJucyB0aGUgcG9zaXRpb24gb2YgdGhl IG1pbmltYWwgZWxlbWVudCBvZiBmb3J3YXJkIHJhbmdlICQoRCByYW5nZSksIGku ZS4gYSBzdWJyYW5nZSBvZgogKiAkKEQgcmFuZ2UpIHN0YXJ0aW5nIGF0IHRoZSBw b3NpdGlvbiBvZiBpdHMgc21hbGxlc3QgZWxlbWVudCwgYW5kIGhhdmluZyB0aGUg c2FtZSBlbmRpbmcgYXMKICogJChEIHJhbmdlKS4gVGhlIHNtYWxsZXN0IGVsZW1l bnQgbWF5IG9wdGlvbmFsbHkgYmUgZGV0ZXJtaW5lZCBieSB0aGUgdW5hcnkgZnVu Y3Rpb24gJChEIGZ1bikuCi0tLS0KYXNzZXJ0KCBtaW5Qb3MoICJ0ZWFzcG9vbiIg KSA9PSAiYXNwb29uIiApOwphc3NlcnQoIG1pblBvcyEiYS5sZW5ndGgiKCBbImFi IiwgImJjIiwgImQiLCAiZWYiXSApID09IFsiZCIsICJlZiJdICk7Ci0tLS0KICov ClJhbmdlIG1pblBvcyggUmFuZ2UgKSggUmFuZ2UgcmFuZ2UgKSBpZiAoIGlzRm9y d2FyZFJhbmdlIVJhbmdlICkgewoJcmV0dXJuIGV4dHJlbXVtUG9zISJhPGIiKCBy YW5nZSApOwp9CgpSYW5nZSBtaW5Qb3MoIGFsaWFzIGZ1biwgUmFuZ2UgKSggUmFu Z2UgcmFuZ2UgKSBpZiAoIGlzRm9yd2FyZFJhbmdlIVJhbmdlICkgewoJYWxpYXMg dW5hcnlGdW4hZnVuIGZuOwoJLy9yZXR1cm4gZXh0cmVtdW0hKCAoIGEsIGIgKXsg cmV0dXJuIGZuKCBhICkgPCBmbiggYiApOyB9ICkoIHJhbmdlICk7IC8vIEJ1Zy4K CQoJYXV0byBmbjIgPSAoIEVsZW1lbnRUeXBlIVJhbmdlIGEsIEVsZW1lbnRUeXBl IVJhbmdlIGIgKXsgcmV0dXJuIGZuKCBhICkgPCBmbiggYiApOyB9OwoJcmV0dXJu IGV4dHJlbXVtUG9zIWZuMiggcmFuZ2UgKTsKfQoKdW5pdHRlc3QgewoJYXNzZXJ0 KCBtaW5Qb3MoIFsxLCAyLCAzLCAxLCAyLCAzXSApID09IFsxLCAyLCAzLCAxLCAy LCAzXSApOwoJYXNzZXJ0KCBtaW5Qb3MoICJ0ZWFzcG9vbiIgKSA9PSAiYXNwb29u IiApOwoJYXNzZXJ0KCBtaW5Qb3MhImEubGVuZ3RoIiggWyJhYiIsICJiYyIsICJk IiwgImVmIl0gKSA9PSBbImQiLCAiZWYiXSApOwp9CgoKLyoqCiAqIFJldHVybnMg YW4gYXJyYXkgb2YgYWxsIG1heGltYWwgZWxlbWVudHMgb2YgJChEIHJhbmdlKSwg b3B0aW9uYWxseSBkZXRlcm1pbmVkIGJ5IHRoZSB1bmFyeQogKiBmdW5jdGlvbiAk KEQgZnVuKS4KLS0tLQphc3NlcnQoIG1heEFyZyggWyJhIiwgImJjIiwgImMiLCAi ZGUiXSApID09IFsiZGUiXSApOwphc3NlcnQoIG1heEFyZyEiYS5sZW5ndGgiKCBb WzFdLCBbMl0sIFszLDRdLCBbNSw2XV0gKSA9PSBbWzMsNF0sIFs1LDZdXSApOwot LS0tCiAqLwpFbGVtZW50VHlwZSFSYW5nZVtdIG1heEFyZyggUmFuZ2UgKSggUmFu Z2UgcmFuZ2UgKSBpZiAoIGlzSW5wdXRSYW5nZSFSYW5nZSApIHsKCXJldHVybiBl eHRyZW11bUFyZyEiYT5iIiggcmFuZ2UgKTsKfQoKRWxlbWVudFR5cGUhUmFuZ2Vb XSBtYXhBcmcoIGFsaWFzIGZ1biwgUmFuZ2UgKSggUmFuZ2UgcmFuZ2UgKSBpZiAo IGlzSW5wdXRSYW5nZSFSYW5nZSApIHsKCWFsaWFzIHVuYXJ5RnVuIWZ1biBmbjsK CS8vcmV0dXJuIGV4dHJlbXVtISggKCBhLCBiICl7IHJldHVybiBmbiggYSApID4g Zm4oIGIgKTsgfSApKCByYW5nZSApOyAvLyBCdWcuCgkKCWF1dG8gZm4yID0gKCBF bGVtZW50VHlwZSFSYW5nZSBhLCBFbGVtZW50VHlwZSFSYW5nZSBiICl7IHJldHVy biBmbiggYSApID4gZm4oIGIgKTsgfTsKCXJldHVybiBleHRyZW11bUFyZyFmbjIo IHJhbmdlICk7Cn0KCnVuaXR0ZXN0IHsKCWFzc2VydCggbWF4QXJnKCBbMSwgMiwg MywgMSwgMiwgM10gKSA9PSBbMywgM10gKTsKCWFzc2VydCggbWF4QXJnISJhIigg WzEsIDIsIDMsIDEsIDIsIDNdICkgPT0gWzMsIDNdICk7Cglhc3NlcnQoIG1heEFy ZyggWyJhIiwgImJjIiwgImMiLCAiZGUiXSApID09IFsiZGUiXSApOwoJYXNzZXJ0 KCBtYXhBcmchImEubGVuZ3RoIiggW1sxXSwgWzJdLCBbMyw0XSwgWzUsNl1dICkg PT0gW1szLDRdLCBbNSw2XV0gKTsKCWFzc2VydCggbWF4QXJnISIzIC0gYS5sZW5n dGgiKCBbImFiIiwgImMiLCAiZGUiLCAiZiJdICkgPT0gWyJjIiwgImYiXSApOwoJ YXNzZXJ0KCBtYXhBcmcoImJhbmFuYXMiKSA9PSAicyIgKTsKCWFzc2VydCggbWF4 QXJnKCJTZWFzaG9yZSIpID09ICJzIiApOwp9CgoKLyoqCiAqIFJldHVybnMgdGhl IG1heGltYWwgZWxlbWVudCBvZiAkKEQgcmFuZ2UpLCBvcHRpb25hbGx5IGRldGVy bWluZWQgYnkgdGhlIHVuYXJ5IGZ1bmN0aW9uICQoRCBmdW4pLgotLS0tCglhc3Nl cnQoIG1heCggWzEsIDIsIDMsIDEsIDIsIDNdICkgPT0gMyApOwoJYXNzZXJ0KCBt YXgoImJhbmFuYXMiKSA9PSAncycgKTsKCWFzc2VydCggbWF4ISJhLmxlbmd0aCIo IFtbMV0sIFsyXSwgWzMsNF0sIFs1LDZdXSApID09IFszLDRdICk7Ci0tLS0KICov CkVsZW1lbnRUeXBlIVJhbmdlIG1heCggUmFuZ2UgKSggUmFuZ2UgcmFuZ2UgKSBp ZiAoIGlzSW5wdXRSYW5nZSFSYW5nZSApIHsKCXJldHVybiBleHRyZW11bSEiYT5i IiggcmFuZ2UgKTsKfQoKRWxlbWVudFR5cGUhUmFuZ2UgbWF4KCBhbGlhcyBmdW4s IFJhbmdlICkoIFJhbmdlIHJhbmdlICkgaWYgKCBpc0lucHV0UmFuZ2UhUmFuZ2Ug KSB7CglhbGlhcyB1bmFyeUZ1biFmdW4gZm47CgkvL3JldHVybiBleHRyZW11bUFy ZyEoICggYSwgYiApeyByZXR1cm4gZm4oIGEgKSA+IGZuKCBiICk7IH0gKSggcmFu Z2UgKTsgLy8gQnVnLgoJCglhdXRvIGZuMiA9ICggRWxlbWVudFR5cGUhUmFuZ2Ug YSwgRWxlbWVudFR5cGUhUmFuZ2UgYiApeyByZXR1cm4gZm4oIGEgKSA+IGZuKCBi ICk7IH07CglyZXR1cm4gZXh0cmVtdW0hZm4yKCByYW5nZSApOwp9Cgp1bml0dGVz dCB7Cglhc3NlcnQoIG1heCggWzEsIDIsIDMsIDEsIDIsIDNdICkgPT0gMyApOwoJ YXNzZXJ0KCBtYXghImEiKCBbMSwgMiwgMywgMSwgMiwgM10gKSA9PSAzICk7Cglh c3NlcnQoIG1heCggWyJhIiwgImJjIiwgImMiLCAiZGUiXSApID09ICJkZSIgKTsK CWFzc2VydCggbWF4ISJhLmxlbmd0aCIoIFtbMV0sIFsyXSwgWzMsNF0sIFs1LDZd XSApID09IFszLDRdICk7Cglhc3NlcnQoIG1heCEiMyAtIGEubGVuZ3RoIiggWyJh YiIsICJjIiwgImRlIiwgImYiXSApID09ICJjIiApOwoJYXNzZXJ0KCBtYXgoImJh bmFuYXMiKSA9PSAncycgKTsKCWFzc2VydCggbWF4KCJTZWFzaG9yZSIpID09ICdz JyApOwp9CgoKLyoqCiAqIFJldHVybnMgdGhlIG1heGltYWwgZWxlbWVudCBvZiAk KEQgcmFuZ2UpLCBhbG9uZyB3aXRoIHRoZSBudW1iZXIgb2Ygb2NjdXJlbmNlcy4g VGhlIG1heGltYWwKICogZWxlbWVudCBtYXkgb3B0aW9uYWxseSBiZSBkZXRlcm1p bmVkIGJ5IHRoZSB1bmFyeSBmdW5jdGlvbiAkKEQgZnVuKS4KLS0tLQphc3NlcnQo IG1heENvdW50KCBbMSwgMiwgMywgMiwgM10gKSA9PSB0dXBsZSggMywgMiApICk7 CmFzc2VydCggbWF4Q291bnQoICJiYW5hbmFzIiApID09IHR1cGxlKCAncycsIDEg KSApOwotLS0tCiAqLwpUdXBsZSEoIEVsZW1lbnRUeXBlIVJhbmdlLCBzaXplX3Qg KSBtYXhDb3VudCggUmFuZ2UgKSggUmFuZ2UgcmFuZ2UgKSBpZiAoIGlzSW5wdXRS YW5nZSFSYW5nZSApIHsKCXJldHVybiBleHRyZW11bUNvdW50ISJhPmIiKCByYW5n ZSApOwp9CgpUdXBsZSEoIEVsZW1lbnRUeXBlIVJhbmdlLCBzaXplX3QgKSAgbWF4 Q291bnQoIGFsaWFzIGZ1biwgUmFuZ2UgKSggUmFuZ2UgcmFuZ2UgKSBpZiAoIGlz SW5wdXRSYW5nZSFSYW5nZSApIHsKCWFsaWFzIHVuYXJ5RnVuIWZ1biBmbjsKCS8v cmV0dXJuIGV4dHJlbXVtISggKCBhLCBiICl7IHJldHVybiBmbiggYSApID4gZm4o IGIgKTsgfSApKCByYW5nZSApOyAvLyBCdWcuCgkKCWF1dG8gZm4yID0gKCBFbGVt ZW50VHlwZSFSYW5nZSBhLCBFbGVtZW50VHlwZSFSYW5nZSBiICl7IHJldHVybiBm biggYSApID4gZm4oIGIgKTsgfTsKCXJldHVybiBleHRyZW11bUNvdW50IWZuMigg cmFuZ2UgKTsKfQoKdW5pdHRlc3QgewoJYXNzZXJ0KCBtYXhDb3VudCggWzEsIDIs IDMsIDIsIDNdICkgPT0gdHVwbGUoIDMsIDIgKSApOwoJYXNzZXJ0KCBtYXhDb3Vu dCggImJhbmFuYXMiICkgPT0gdHVwbGUoICdzJywgMSApICk7Cglhc3NlcnQoIG1h eENvdW50KCAiIiApID09IHR1cGxlKCBkY2hhci5pbml0LCAwICkgKTsKCWFzc2Vy dCggbWF4Q291bnQhImEubGVuZ3RoIiggWyJhIiwgImJjIiwgImQiLCAiZWYiXSAp ID09IHR1cGxlKCAiYmMiLCAyICkgKTsKfQoKCi8qKgogKiBSZXR1cm5zIHRoZSBw b3NpdGlvbiBvZiB0aGUgbWF4aW1hbCBlbGVtZW50IG9mIGZvcndhcmQgcmFuZ2Ug JChEIHJhbmdlKSwgaS5lLiBhIHN1YnJhbmdlIG9mCiAqICQoRCByYW5nZSkgc3Rh cnRpbmcgYXQgdGhlIHBvc2l0aW9uIG9mIGl0cyBsYXJnZXN0IGVsZW1lbnQsIGFu ZCBoYXZpbmcgdGhlIHNhbWUgZW5kaW5nIGFzCiAqICQoRCByYW5nZSkuIFRoZSBs YXJnZXN0IGVsZW1lbnQgbWF5IG9wdGlvbmFsbHkgYmUgZGV0ZXJtaW5lZCBieSB0 aGUgdW5hcnkgZnVuY3Rpb24gJChEIGZ1bikuCi0tLS0KYXNzZXJ0KCBtYXhQb3Mo ICJUZWFzcG9vbiIgKSA9PSAic3Bvb24iICk7CmFzc2VydCggbWF4UG9zISJhLmxl bmd0aCIoIFsiYSIsICJiYyIsICJkIiwgImVmIl0gKSA9PSBbImJjIiwgImQiLCAi ZWYiXSApOwotLS0tCiAqLwpSYW5nZSBtYXhQb3MoIFJhbmdlICkoIFJhbmdlIHJh bmdlICkgaWYgKCBpc0ZvcndhcmRSYW5nZSFSYW5nZSApIHsKCXJldHVybiBleHRy ZW11bVBvcyEiYT5iIiggcmFuZ2UgKTsKfQoKUmFuZ2UgbWF4UG9zKCBhbGlhcyBm dW4sIFJhbmdlICkoIFJhbmdlIHJhbmdlICkgaWYgKCBpc0ZvcndhcmRSYW5nZSFS YW5nZSApIHsKCWFsaWFzIHVuYXJ5RnVuIWZ1biBmbjsKCS8vcmV0dXJuIGV4dHJl bXVtISggKCBhLCBiICl7IHJldHVybiBmbiggYSApID4gZm4oIGIgKTsgfSApKCBy YW5nZSApOyAvLyBCdWcuCgkKCWF1dG8gZm4yID0gKCBFbGVtZW50VHlwZSFSYW5n ZSBhLCBFbGVtZW50VHlwZSFSYW5nZSBiICl7IHJldHVybiBmbiggYSApID4gZm4o IGIgKTsgfTsKCXJldHVybiBleHRyZW11bVBvcyFmbjIoIHJhbmdlICk7Cn0KCnVu aXR0ZXN0IHsKCWFzc2VydCggbWF4UG9zKCBbMSwgMiwgMywgMSwgMiwgM10gKSA9 PSBbMywgMSwgMiwgM10gKTsKCWFzc2VydCggbWF4UG9zKCAiVGVhc3Bvb24iICkg PT0gInNwb29uIiApOwoJYXNzZXJ0KCBtYXhQb3MhImEubGVuZ3RoIiggWyJhIiwg ImJjIiwgImQiLCAiZWYiXSApID09IFsiYmMiLCAiZCIsICJlZiJdICk7Cn0= ------------pEUoe7C8eIDkulsALAqxG4--
Sep 16 2011
prev sibling parent "Simen Kjaeraas" <simen.kjaras gmail.com> writes:
On Sat, 17 Sep 2011 16:06:44 +0200, Timon Gehr <timon.gehr gmx.ch> wrote:

 xyz!"a<b"([1,2,3,1,2,3]) is 1

 xyz!"a>b"([1,2,3,1,2,3]) is 3

 Question is what's a good name for xyz. It returns the element X of the
 range such that pred(E, X) is false for all E in the range. Then we'd
 defined xyzCount and xyzPos and call it a day.


That is the definition of a minimum. pred is the order relation and the range gives the set. Ergo xyz=min. But that is were we are.

Except that min does not mean 'apply this ordering to this set, and then do min on it' to most people. Extremum is a better choice not because it better describes what it does, but precisely the opposite - people do not intuitively 'understand' it, and thus look it up. That said, I agree extremum is not a good name for xyz, but min is horrible.
 What about ultimum? It means the last or the outermost.

As long as the function computes a least element, any names other than leastElem* or min* are just confusing. 'ultimum' is not specific enough. "Does it compute a least element or a greatest element?" The approach of having a name that includes both max and min cannot work in a satisfiable way for that reason.

Excepting of course the possibility that someone at some point might read the documentation... -- Simen
Sep 18 2011
prev sibling next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Christophe:

 A max!callable(range) that 
 replaces max(map!collable(range)) is unuseful and confusing, since max 
 should return one of the element passed in its arguments.

That's not the semantics of what I have proposed, I think you need to read the bug report more carefully. Do you think that SchwartzSort return the mapped range sorted? It returns the original range sorted according to the position of the mapped items. The same is happening here. Bye, bearophile
Sep 15 2011
parent reply travert phare.normalesup.org (Christophe) writes:
bearophile , dans le message (digitalmars.D:144543), a écrit :
 Christophe:
 
 A max!callable(range) that 
 replaces max(map!collable(range)) is unuseful and confusing, since max 
 should return one of the element passed in its arguments.

That's not the semantics of what I have proposed, I think you need to read the bug report more carefully. Do you think that SchwartzSort return the mapped range sorted? It returns the original range sorted according to the position of the mapped items. The same is happening here.

Well, I don't know all of Phobos, and I didn't check what schwartzSort was. I got confused by the fact that you wanted to avoid typing: reduce!max(map!callable(range)). That's a nice idea then. sort does not use a Schwartzian transformation, although is preferable in many cases in term of efficiency: it uses a less predicate, because it has been decided that it is what the user expects, am I right? If you want to use a Schwartian transformation, you use schwartzSort. If you want Phobos to be consistent, max should use a less predicate, and schwartzMax should use a Schwartzian transformation. Maybe it should not be consistent on that particular point. I'm just saying. -- Christophe
Sep 15 2011
parent reply bearophile <bearophileHUGS lycos.com> writes:
Christophe:

 sort does not use a Schwartzian transformation, although is preferable 
 in many cases in term of efficiency: it uses a less predicate, because 
 it has been decided that it is what the user expects, am I right? If you 
 want to use a Schwartian transformation, you use schwartzSort.

I didn't agree with that design decision of Phobos, I think I said this to Andrei too. schwartzSort is a very handy sort, I don't like it buried by such long (and for me hard to write name, I am never able to remember its spelling). In Python3 the built-in sort is a schwartzSort. Beside the name, I think D schwartzSort needs an improvement, because currently you can't give it a function like q{ a.foo }, you have to use a longer lambda like (Foo a){ return a.foo; }. Bye, bearophile
Sep 15 2011
parent travert phare.normalesup.org (Christophe) writes:
bearophile , dans le message (digitalmars.D:144550), a écrit :
 Christophe:
 
 sort does not use a Schwartzian transformation, although is preferable 
 in many cases in term of efficiency: it uses a less predicate, because 
 it has been decided that it is what the user expects, am I right? If you 
 want to use a Schwartian transformation, you use schwartzSort.

I didn't agree with that design decision of Phobos, I think I said this to Andrei too. schwartzSort is a very handy sort, I don't like it buried by such long (and for me hard to write name, I am never able to remember its spelling). In Python3 the built-in sort is a schwartzSort. Beside the name, I think D schwartzSort needs an improvement, because currently you can't give it a function like q{ a.foo }, you have to use a longer lambda like (Foo a){ return a.foo; }.

Hum, then schwartzSort could be simply called sort, since there is no way the two sort function could be mistaken*. Actually the compiler could accept both sort function with a string template argument under the same name. sort!string(range) could check if unaryFun!string compiles, or if binaryFun!string compiles and returns a bool, and decide which sort algorithm to use. There is no possible confusion, unless someone has the crazy idea of using a schwartzian transformation that returns a bool. *What is questionable is whether sort!unaryFun should allocate the transformed data of the whole range in any case, because it may not be optimal. Anyway, that does not apply to max!unaryFun. -- Christophe
Sep 15 2011
prev sibling parent bearophile <bearophileHUGS lycos.com> writes:
Christophe:

 mins and maxs are too specialized to be in phobos IMO.

What are the disadvantage of having them in Phobos? Regarding the advantages, my experience shows that several algorithms require to find all the equally max or min items, it's a common enough pattern. Look at the AI book by Norvig to see algorithms that use it. The problem of not putting this micropattern in Phobos is condemn yourself to re-implement it again and again and again every time you need it. And... there are bugs and efficiency too to keep in account. This algorithm is simple, but it requires to temporarily store all the max/min items found so far. If you don't this efficiently, you waste computations and stress the GC. How many times do you want to re-implement this, debug it, and tune its efficiency? Once is enough. If you use maxs you are writing bug-free code, short, efficient, and you are documenting your code, there is less need to comment your code. And using maxs/mins (like using the other higher order functions) allows you to think about your code at a higher level. Bye, bearophile
Sep 15 2011
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/14/11 5:57 PM, bearophile wrote:
 I'd like to receive some comments from Andrei about one of the most
 nagging problems I have with std.algorithm, it's not a big issue, but
 I bump my nose against it few times every week:

 http://d.puremagic.com/issues/show_bug.cgi?id=4705

 If you have questions or doubts, feel free to ask here or in
 Bugzilla.

 Bye, bearophile

So you propose adding these (among others): min(collection) min!(callable)(collection) max(collection) max!(callable)(collection) We now have: min(a, b, c, ...) max(a, b, c, ...) minCount!callable(range) minPos!callable(range) The latter two take a binary predicate that customizes the comparison function. That's why maxCount and maxPos are not provided. This is where things get a bit problematic. In the calls min!foo(range) and minCount!foo(range), the function foo has a completely different meaning - the first is a unary mapper, the second is a binary predicate. This is quite confusing. I had the suspicion minCount and minPos where poor choices of name, but I was unable to find a better name for "min" there. It's something like "extremum" or "bound". Finding a good name would be great. I'm not sure how to solve this in a way that will minimize code breakage. One possibility I can think of is to define and use isUnaryFunction and isBinaryFunction. However, one-argument calls such as min(collection) seem unambiguous and valuable to me. Second, you propose mins(collection) mins!(callable)(collection) maxs(collection) maxs!(callable)(collection) that return all elements. I'm not sure how you plan to return - create a new array, or iterate a la filter? The latter is interesting, but for either variant is quite difficult to find use examples that are frequent enough to make min followed by filter too verbose. Thanks, Andrei
Sep 15 2011
next sibling parent dsimcha <dsimcha yahoo.com> writes:
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article
 However, one-argument calls such as min(collection) seem unambiguous and
 valuable to me.

FWIW, I've been using this only slightly more verbose call lately: immutable biggestX = minPos!"a.x > b.x"(someArray).front;
Sep 15 2011
prev sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 09/15/2011 05:42 PM, Andrei Alexandrescu wrote:
 We now have:

 min(a, b, c, ...)
 max(a, b, c, ...)
 minCount!callable(range)
 minPos!callable(range)

 The latter two take a binary predicate that customizes the comparison
 function. That's why maxCount and maxPos are not provided.

Are you sure that minCount!"a>b"(range); is better than maxCount(range); ? If so, for what definition of better? Do you expect every library user to implement the maxCount in terms of minCount himself in his own utility module?
 I had the suspicion minCount and minPos where poor choices of name, but I was
unable to find a better name for "min" there. It's something like
 "extremum" or "bound". Finding a good name would be great.

I am quite sure that those names are a quite perfect match, because they describe exactly what those functions do. Both extremum and bound are too general terms, because what the functions do relates to the least element (min) under the total order given by pred. After many years, mathematicians that think about it every day could not find a satisfying solution either, eg, consider: http://en.wikipedia.org/wiki/Least_element . They'll usually prove a theorem for one of min or max and then argue that the proof works analogously for the other one. If they want to refer specifically to min or max, they use eg. the terms 'min' or 'max', as opposed to eg 'min' and 'min in respect to the reverse of the total order used at other places in this paper'. I get that you think the names might be a poor choice because those functions are supposed to be usable to get the maxCount or the maxPos too. That is, in my opinion, the wrong conclusion. The problem is that those functions are supposed to be usable to get the maxCount or the maxPos in the first place. Functions called 'maxCount' and 'maxPos' are way better suited, and providing these would not increase the complexity of std.algorithm. It would only make it more regular. Orthogonality is in my opinion overrated. I, for one, do not want to move through problem space in a Manhattan taxicab. The shortest path between two points is a straight line. That is trivial fact. I understand that other people may have a different stance on this, but my personal experience is that not using most of the generic functionality in std.algorithm produces way faster and better self-documenting code. In functional style programs, good function names are crucial if the code should be understandable fast, and saving a few keystrokes matters a great deal because lines fill up fast. Timon
Sep 15 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/15/11 3:36 PM, Timon Gehr wrote:
 On 09/15/2011 05:42 PM, Andrei Alexandrescu wrote:
 We now have:

 min(a, b, c, ...)
 max(a, b, c, ...)
 minCount!callable(range)
 minPos!callable(range)

 The latter two take a binary predicate that customizes the comparison
 function. That's why maxCount and maxPos are not provided.

Are you sure that minCount!"a>b"(range); is better than maxCount(range); ? If so, for what definition of better? Do you expect every library user to implement the maxCount in terms of minCount himself in his own utility module?

Don't forget that I'm as fallible as the next guy, if not more. std.algorithm has some 8500 lines and I wrote most of them, so I was liable to make a few imperfect choices.
 I had the suspicion minCount and minPos where poor choices of name,
 but I was unable to find a better name for "min" there. It's something
 like
 "extremum" or "bound". Finding a good name would be great.

I am quite sure that those names are a quite perfect match, because they describe exactly what those functions do. Both extremum and bound are too general terms, because what the functions do relates to the least element (min) under the total order given by pred.

Reading the above I fail to understand whether you like these names or not.
 After many years, mathematicians that think about it every day could not
 find a satisfying solution either, eg, consider:
 http://en.wikipedia.org/wiki/Least_element . They'll usually prove a
 theorem for one of min or max and then argue that the proof works
 analogously for the other one. If they want to refer specifically to min
 or max, they use eg. the terms 'min' or 'max', as opposed to eg 'min'
 and 'min in respect to the reverse of the total order used at other
 places in this paper'.

 I get that you think the names might be a poor choice because those
 functions are supposed to be usable to get the maxCount or the maxPos
 too. That is, in my opinion, the wrong conclusion. The problem is that
 those functions are supposed to be usable to get the maxCount or the
 maxPos in the first place. Functions called 'maxCount' and 'maxPos' are
 way better suited, and providing these would not increase the complexity
 of std.algorithm. It would only make it more regular.

Once minCount takes a lambda, I can't tell people what lambda to pass, so they will be able to compute a maximum with it. Defining maxCount and maxPos without a lambda is definitely possible, but rather odd. How is one e.g. supposed to remember that minPos is the one with a lambda and maxPos isn't? I'd much rather look for a good name to replace both, and then define minXxx and maxXxx in terms of that. Andrei
Sep 15 2011
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 09/15/2011 11:39 PM, Andrei Alexandrescu wrote:
 On 9/15/11 3:36 PM, Timon Gehr wrote:
 On 09/15/2011 05:42 PM, Andrei Alexandrescu wrote:
 We now have:

 min(a, b, c, ...)
 max(a, b, c, ...)
 minCount!callable(range)
 minPos!callable(range)

 The latter two take a binary predicate that customizes the comparison
 function. That's why maxCount and maxPos are not provided.

Are you sure that minCount!"a>b"(range); is better than maxCount(range); ? If so, for what definition of better? Do you expect every library user to implement the maxCount in terms of minCount himself in his own utility module?

Don't forget that I'm as fallible as the next guy, if not more. std.algorithm has some 8500 lines and I wrote most of them, so I was liable to make a few imperfect choices.
 I had the suspicion minCount and minPos where poor choices of name,
 but I was unable to find a better name for "min" there. It's something
 like
 "extremum" or "bound". Finding a good name would be great.

I am quite sure that those names are a quite perfect match, because they describe exactly what those functions do. Both extremum and bound are too general terms, because what the functions do relates to the least element (min) under the total order given by pred.

Reading the above I fail to understand whether you like these names or not.

Yes, the names are good. But they imply there should be maxCount and maxPos functions.
 After many years, mathematicians that think about it every day could not
 find a satisfying solution either, eg, consider:
 http://en.wikipedia.org/wiki/Least_element . They'll usually prove a
 theorem for one of min or max and then argue that the proof works
 analogously for the other one. If they want to refer specifically to min
 or max, they use eg. the terms 'min' or 'max', as opposed to eg 'min'
 and 'min in respect to the reverse of the total order used at other
 places in this paper'.

 I get that you think the names might be a poor choice because those
 functions are supposed to be usable to get the maxCount or the maxPos
 too. That is, in my opinion, the wrong conclusion. The problem is that
 those functions are supposed to be usable to get the maxCount or the
 maxPos in the first place. Functions called 'maxCount' and 'maxPos' are
 way better suited, and providing these would not increase the complexity
 of std.algorithm. It would only make it more regular.

Once minCount takes a lambda, I can't tell people what lambda to pass, so they will be able to compute a maximum with it.

Technically, what they can do is: 1. create an ordered set with the reverse total order of the original ordered set 2. compute a minimum of that new set. 3. find the corresponding value in the original set You can take those three steps and call it an algorithm to compute a maximum. That this algorithm has to be applied manually to get maxPos/maxCount strikes me as odd.
 Defining maxCount and maxPos without a lambda is definitely possible,
 but rather odd. How is one e.g. supposed to remember that minPos is the
 one with a lambda and maxPos isn't?

They should take a binary predicate, just like minPos/minCount.
 I'd much rather look for a good name to replace both, and then define
 minXxx and maxXxx in terms of that.

Yes, but my point was, there is no good name, because there is no function that can do what you want. If all you have is a transitive binary relation there is absolutely no way to have an algorithm that computes either minima or maxima, based solely on the relation, because the relation unambiguously defines what is the minimum value and what is the maximum value. Therefore you have to introduce a second parameter that says whether to compute a minimum or a maximum. Approximately the best you could get is: globalExtremalPos!("a<b",ExtremalPos.minimum)(range) globalExtremalPos!("a<b",ExtremalPos.maximum)(range) And that is just satire. Those calls should be replaced with minPos!"a<b"(range) maxPos!"a<b"(range) Timon
Sep 16 2011
prev sibling next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Thursday, September 15, 2011 10:39 Andrei Alexandrescu wrote:
 On 9/15/11 12:14 PM, Jonathan M Davis wrote:
 On Thursday, September 15, 2011 03:41 bearophile wrote:
 It seems
 (to me) more natural to give it a predicate to compare elements two at
 a time. This is what is used in c++ std lib.

It's less natural. And D is not C++, there are more than just C++ programmers in D. And it leads to longer& more complex code.

I think that that's up for debate. I would fully expect a min/max function to be using a comparator function, which means using a binary predicate. Also, given that everything else in std.algorithm which takes a predicate is taking an actually predicate and not what should be compared, having max take something like "a.length" would be extremely bizarre. I don't find max!"a.length"(range) to be natural at all. Maybe it's more natural for someone with little to no programming experience, but I really don't think that your average programmer is going to find it more natural. - Jonathan M Davis

I just realized argmax is exactly the name bearophile is looking for (http://en.wikipedia.org/wiki/Arg_max). I know, I'm awesome with names like that. We should add argmax to phobos.

If we're going to add it, that name works fine with me (though it should probably be argMax for proper camelcasing). I'd hate to see max work that way though. - Jonathan M Davis
Sep 15 2011
prev sibling next sibling parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Thursday, September 15, 2011 11:46 Timon Gehr wrote:
 On 09/15/2011 07:48 PM, Jonathan M Davis wrote:
 On Thursday, September 15, 2011 10:39 Andrei Alexandrescu wrote:
 On 9/15/11 12:14 PM, Jonathan M Davis wrote:
 On Thursday, September 15, 2011 03:41 bearophile wrote:
 It seems
 (to me) more natural to give it a predicate to compare elements two
 at a time. This is what is used in c++ std lib.

It's less natural. And D is not C++, there are more than just C++ programmers in D. And it leads to longer& more complex code.

I think that that's up for debate. I would fully expect a min/max function to be using a comparator function, which means using a binary predicate. Also, given that everything else in std.algorithm which takes a predicate is taking an actually predicate and not what should be compared, having max take something like "a.length" would be extremely bizarre. I don't find max!"a.length"(range) to be natural at all. Maybe it's more natural for someone with little to no programming experience, but I really don't think that your average programmer is going to find it more natural. - Jonathan M Davis

I just realized argmax is exactly the name bearophile is looking for (http://en.wikipedia.org/wiki/Arg_max). I know, I'm awesome with names like that. We should add argmax to phobos.

If we're going to add it, that name works fine with me (though it should probably be argMax for proper camelcasing). I'd hate to see max work that way though. - Jonathan M Davis

It is written either arg max or argmax. Proper camel casing for the first one is argMax and for the second one argmax. Therefore it could go either way.

Well, if argmax is indeed recognized as a single word/term, then argmax works. I'm not familiar with it though, so I couldn't say based on what I know. - Jonathan M Davis
Sep 15 2011
parent Kagamin <spam here.lot> writes:
Jonathan M Davis Wrote:

 Well, if argmax is indeed recognized as a single word/term, then argmax works. 
 I'm not familiar with it though, so I couldn't say based on what I know.

You just need to understand when you see it used.
Sep 16 2011
prev sibling next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Friday, September 16, 2011 05:33:57 Kagamin wrote:
 Jonathan M Davis Wrote:
 I think that that's up for debate. I would fully expect a min/max
 function to be using a comparator function, which means using a binary
 predicate.

2. do you have a use case for a binary predicate?

Comparator functions are pretty much always binary predicates. With a min or max function, you're using a comparator function. It would be incredibly bizarre for it to do otherwise, and taking simply the property to compare would be extremely limiting. For instance, what if you you wanted to compare using two properties? That's completely straightforward with a binary predicate and utterly impossible when you pass the property to be compared instead of a proper predicate. - Jonathan M Davis
Sep 16 2011
parent reply bearophile <bearophileHUGS lycos.com> writes:
Jonathan M Davis:

 Comparator functions are pretty much always binary predicates.

And I think this has to change a bit in D. Because mapping functions are quite handy (despite requiring more memory, so it can't be the only way to do things in D, and both ways need to be supported). In Python3 sort/sorted/min/max don't take a comparator function, they only take a key mapping function. It's often used in Haskell too: import Data.List (sortBy) import Data.Ord (comparing) main = print $ sortBy (comparing length) [[1,3,1], [5], [7,7]]
 It would be incredibly bizarre for it to do otherwise,

It's not bizarre at all :-) If you want to express such value judgements then I suggest you to look at more programming languages, so better know what you are talking about.
 and taking simply the property to compare 
 would be extremely limiting.

It gives some limitations in some uncommon cases (where using a comparator is better), but surely it's not 'extremely limiting'. I am using _only_ key (mapping) functions in Python since years, and I am writing all kinds of programs with it.
 For instance, what if you you wanted to compare 
 using two properties? That's completely straightforward with a binary 
 predicate and utterly impossible when you pass the property to be compared 
 instead of a proper predicate.

It's extremely simple to do :-) (p){ return tuple(p.foo, p.bar); } Bye, bearophile
Sep 16 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/16/11 9:38 AM, bearophile wrote:
 Jonathan M Davis:

 Comparator functions are pretty much always binary predicates.

And I think this has to change a bit in D. Because mapping functions are quite handy (despite requiring more memory, so it can't be the only way to do things in D, and both ways need to be supported). In Python3 sort/sorted/min/max don't take a comparator function, they only take a key mapping function. It's often used in Haskell too: import Data.List (sortBy) import Data.Ord (comparing) main = print $ sortBy (comparing length) [[1,3,1], [5], [7,7]]

Yah, that's what SQL's order by does too. To sort numbers descending one would sort by mapping through "-a", to sort case-insensitive one would sort by mapping through "toupper(a)" etc. Without having thought a lot about this: sorting through mapping and sorting by binary predicate are not equivalent in power. This is because any sorting by mapping through some function f can be expressed as sorting by f(a) < f(b). At the same time, if what you have is an opaque predicate rank(a, b), you cannot define an equivalent mapper. This suggests it's better to sort by binary comparison. That being said, ranking by f(a) < f(b) can be quite wasteful if f is expensive, so it's good to have it as an option for certain algorithms. Obviously schwartzSort is one. Are there others? Andrei
Sep 16 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/16/11 11:29 AM, Andrei Alexandrescu wrote:
 On 9/16/11 9:38 AM, bearophile wrote:
 Jonathan M Davis:

 Comparator functions are pretty much always binary predicates.

And I think this has to change a bit in D. Because mapping functions are quite handy (despite requiring more memory, so it can't be the only way to do things in D, and both ways need to be supported). In Python3 sort/sorted/min/max don't take a comparator function, they only take a key mapping function. It's often used in Haskell too: import Data.List (sortBy) import Data.Ord (comparing) main = print $ sortBy (comparing length) [[1,3,1], [5], [7,7]]

Yah, that's what SQL's order by does too. To sort numbers descending one would sort by mapping through "-a", to sort case-insensitive one would sort by mapping through "toupper(a)" etc.

I just figured an annoying case for sort through mapping: how would one sort a range of ulong descending? Or a range of pointers for that matter? Andrei
Sep 16 2011
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
Andrei Alexandrescu:

 Obviously schwartzSort is one. Are there others?

max/min/mins/maxs come to mind immediately. It's not too much hard to invent a more general decorate-function-undecorate higher order function, but I do not want to use it to do sort/max/min.
 I just figured an annoying case for sort through mapping: how would one 
 sort a range of ulong descending? Or a range of pointers for that matter?

Python sort has a optional boolean argument that allows you to specify if to sort ascending or descending, but this doesn't solve all cases. Sorting a range of pointers is not a common operation, I presume. A solution is to wrap the ulong inside a BigInt, but it's not efficient. In this case it seems better to use a comparison function instead. My point wasn't to always replace comparison functions with a mapping one, both as useful in different situations. My point is that comparison functions are overrated, and both languages, standard libraries, and programmers need to take into account that mapping functions are often more handy, especially in the large percentage of a program where there is no need of top performance. Bye, bearophile
Sep 16 2011
prev sibling next sibling parent reply =?UTF-8?B?IkrDqXLDtG1lIE0uIEJlcmdlciI=?= <jeberger free.fr> writes:
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

Andrei Alexandrescu wrote:
 I just figured an annoying case for sort through mapping: how would one=

 sort a range of ulong descending? Or a range of pointers for that matte=

=20

Jerome --=20 mailto:jeberger free.fr http://jeberger.free.fr Jabber: jeberger jabber.fr
Sep 16 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/16/11 12:14 PM, "Jérôme M. Berger" wrote:
 Andrei Alexandrescu wrote:
 I just figured an annoying case for sort through mapping: how would one
 sort a range of ulong descending? Or a range of pointers for that matter?


Heh, thanks. I reckon doing the equivalent for pointers would require some unsavory manipulation. Andrei
Sep 16 2011
parent reply kennytm <kennytm gmail.com> writes:
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:

 Heh, thanks. I reckon doing the equivalent for pointers would require
 some unsavory manipulation.
 
 Andrei

You may want you check Python's "cmp_to_key" function. In terms of D it would be like: struct CmpToKey(alias binaryPred, T) { int opCmp(other) { return binaryPred(this, other); } T wrapped; } Then sort/min/max by `cmpToKey!"a<b"(a)`.
Sep 16 2011
parent kennytm <kennytm gmail.com> writes:
kennytm <kennytm gmail.com> wrote:
 Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:
 
 Heh, thanks. I reckon doing the equivalent for pointers would require
 some unsavory manipulation.
 
 Andrei

You may want you check Python's "cmp_to_key" function. In terms of D it would be like: struct CmpToKey(alias binaryPred, T) { int opCmp(other) { return binaryPred(this, other); } T wrapped; } Then sort/min/max by `cmpToKey!"a<b"(a)`.

Err I mean int opCmp(other) { if (binaryPred(this, other)) return -1; else if (binaryPred(other, this)) return 1; else return 0; }
Sep 16 2011
prev sibling parent Kagamin <spam here.lot> writes:
Andrei Alexandrescu Wrote:

 I just figured an annoying case for sort through mapping: how would one 
 sort a range of ulong descending? Or a range of pointers for that matter?

Sort ascending and reverse.
Sep 19 2011
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Friday, September 16, 2011 05:38:33 Kagamin wrote:
 Jonathan M Davis Wrote:
 Well, if argmax is indeed recognized as a single word/term, then argmax
 works. I'm not familiar with it though, so I couldn't say based on what
 I know.


That may be, but I wasn't talking about its use. I was just talking about its name. As I've never heard of it before now, I'm not at all familiar with whether argmax is used as a single word or note - kind of like how if I weren't familiar with newline or whitespace, then I wouldn't know that they're both usually one word, not two. - Jonathan M Davis
Sep 16 2011
prev sibling next sibling parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Friday, September 16, 2011 07:38 bearophile wrote:
 Jonathan M Davis:
 Comparator functions are pretty much always binary predicates.

And I think this has to change a bit in D. Because mapping functions are quite handy (despite requiring more memory, so it can't be the only way to do things in D, and both ways need to be supported). In Python3 sort/sorted/min/max don't take a comparator function, they only take a key mapping function. It's often used in Haskell too: import Data.List (sortBy) import Data.Ord (comparing) main = print $ sortBy (comparing length) [[1,3,1], [5], [7,7]]

Comparison is _by definition_ a multi-argument operation (and in most programming languages it's a binary operation by definition, since they don't allow you to chain comparison operations). Haskell's sortBy takes a binary predicate, and in this case, you're using comparing is used to generate one for you. But the it's still a binary predicate.
 and taking simply the property to compare
 would be extremely limiting.

It gives some limitations in some uncommon cases (where using a comparator is better), but surely it's not 'extremely limiting'. I am using _only_ key (mapping) functions in Python since years, and I am writing all kinds of programs with it.
 For instance, what if you you wanted to compare
 using two properties? That's completely straightforward with a binary
 predicate and utterly impossible when you pass the property to be
 compared instead of a proper predicate.

It's extremely simple to do :-) (p){ return tuple(p.foo, p.bar); }

Okay. I didn't think of that (probably because I was thinking more in terms of "length" than "a.length"), but is the overhead of creating a tuple to do that warranted in a systems programming language? I sure wouldn't think so - not to mention that the fact that max would then have to do something like pred(a) < pred(b) and thus call the predicate twice instead of the one function call that it would be doing with a proper binary predicate. If you're lucky, the inliner and optimizer would be able to reduce the extra overhead, but I'd be very surprised if it were able to eliminate it. Proper binary predicates just make way more sense IMHO. - Jonathan M Davis
Sep 16 2011
parent bearophile <bearophileHUGS lycos.com> writes:
Jonathan M Davis:

 but is the overhead of creating a tuple to do that 
 warranted in a systems programming language?

This is an interesting point. My experience shows that while you write code there are situations where you care for performance, even a lot. In such situations a system language must give you ways to get the performance you need. But there are many other situations where you know performance is not the most important thing, because it's in a less critical path, because you know you will sort only few items once in a while, or because you are writing a 20 lines long script-line program. In such situations you want to write less code (because less code often means less testing, less bugs, less code to read and modify), you want higher level code (because this makes the program simpler to understand and to think about). Such situations are common, and in my opinion in them a good language has to give you higher level ways to do what you need to do. This is multi-level programming. A max function that takes an unary key function that returns a 2-tuple built on the fly is probably not the most efficient code. But it's very short (especially if your language gives a succint syntax for tuples and lambdas), it's not bug-prone and it's quite handy and easy to to understand and to think about. So I'd like it in Phobos. A system language has to give you ways to be efficient, and probably it also has to offer ways to show and put in evidence where you are not doing things efficiently (like a compiler switch that lists all heap allocations of a module, or all its heap closures), but I don't want it to force me to write low-level code where I don't want to do it. There are plenty of situations where writing low-level code is not the best thing to do. Bye, bearophile
Sep 16 2011
prev sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Friday, September 16, 2011 14:24 bearophile wrote:
 Jonathan M Davis:
 but is the overhead of creating a tuple to do that
 warranted in a systems programming language?

This is an interesting point. My experience shows that while you write code there are situations where you care for performance, even a lot. In such situations a system language must give you ways to get the performance you need. But there are many other situations where you know performance is not the most important thing, because it's in a less critical path, because you know you will sort only few items once in a while, or because you are writing a 20 lines long script-line program. In such situations you want to write less code (because less code often means less testing, less bugs, less code to read and modify), you want higher level code (because this makes the program simpler to understand and to think about). Such situations are common, and in my opinion in them a good language has to give you higher level ways to do what you need to do. This is multi-level programming. A max function that takes an unary key function that returns a 2-tuple built on the fly is probably not the most efficient code. But it's very short (especially if your language gives a succint syntax for tuples and lambdas), it's not bug-prone and it's quite handy and easy to to understand and to think about. So I'd like it in Phobos. A system language has to give you ways to be efficient, and probably it also has to offer ways to show and put in evidence where you are not doing things efficiently (like a compiler switch that lists all heap allocations of a module, or all its heap closures), but I don't want it to force me to write low-level code where I don't want to do it. There are plenty of situations where writing low-level code is not the best thing to do.

Indeed, there are a lot of cases where it's just nicer to have higher level code even if it's less efficient, but the difference between writing min!"a.length < b.length" and min!"a.length" is negligible, and it does have cost some overhead. Writing the comparator function instead of using a tuple with a unary key is certainly worse in terms of the amount of code, but the overhead is worse too. I really don't think that the benefit outweighs the cost. And while a particular call to min may not need to be all that efficient all of the little inefficiencies add up. I'm not opposed to there being a separate argmax function which takes a unary key, but in general, I think that taking a binary function is by far the superior solution, and I'd hate to see the default choice for anything to be a unary key. The small, incremental gain in shortness of code is outweighed by the cost in efficiency and expressivity IMHO. - Jonathan M Davis
Sep 16 2011