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
