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

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

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.

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

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

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); ?

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.

"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

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

"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

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.

"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

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.

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.

 You just need to understand when you see it used.

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

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?

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.

 1. how would they treat the function?
 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

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

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

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

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

=?UTF-8?B?IkrDqXLDtG1lIE0uIEJlcmdlciI=?= <jeberger free.fr> 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 matte=

r?
=20

	Map to ulong.max-x

		Jerome
--=20
mailto:jeberger free.fr
http://jeberger.free.fr
Jabber: jeberger jabber.fr

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?

 	Map to ulong.max-x

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

Andrei

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)`.

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;
}

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.

"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

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

"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

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

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.

"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  

 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.

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

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

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

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

"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

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.

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

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...

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"

"Simen Kjaeraas" <simen.kjaras gmail.com> writes:

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

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.

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.

"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

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())

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]

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

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?

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

 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.

 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.

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

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

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

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

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

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

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

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;

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

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

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