May 17, 2012
On 5/16/2012 12:29 AM, bearophile wrote:
> Then why is Andrei using the name std.algorithm.schwartzSort?

May the schwartz be with you.
May 17, 2012
Al 17/05/12 03:32, En/na Walter Bright ha escrit:
> On 5/16/2012 12:29 AM, bearophile wrote:
>> Then why is Andrei using the name std.algorithm.schwartzSort?
> 
> May the schwartz be with you.
> 

Very appropriate :-)
On 27 May is the 35 anniversary of the first released film from the Star Wars series.

-- 
Jordi Sayol
May 17, 2012
On Thursday, 17 May 2012 at 03:15:47 UTC, Jordi Sayol wrote:
> Al 17/05/12 03:32, En/na Walter Bright ha escrit:
>> On 5/16/2012 12:29 AM, bearophile wrote:
>>> Then why is Andrei using the name std.algorithm.schwartzSort?
>> 
>> May the schwartz be with you.
>> 
>
> Very appropriate :-)
> On 27 May is the 35 anniversary of the first released film from the Star Wars series.

Walter's quote was from "Spaceballs". :-)

-Lars
May 17, 2012
On Tuesday, 15 May 2012 at 17:23:28 UTC, Kirill wrote:
> How about users who don't know what binary search is. binary search is an intuitive concept for people who have good programming experience but assumeSorted(r).contains(x) is more intuitive to higher level users.

If you don't know about binary search, you won't write assumeSorted(r).contains(x) you'll just write r.contains(x) because you have no idea that binary search exists. Why would you bother typing extra characters for a benefit that you are unaware of?

If you do know that binary search exists then the obvious algorithm name is binarySearch. If I use .contains to coax a binarySearch then I'm relying on a little bit of faith. In what situations does it give a binary search?

[1, 2, 3].contains(2); // does the compiler infer that 1, 2, 3 is sorted?
iota(10).contains(5); // is iota implicitly a sorted range?
assumeSorted([1, 2, 3]).map!(x => x + 1).contains(3); // does Phobos know that the map is order preserving?
assumeSorted([1, 2, 3]).filter!("a & 1").contains(2); // does Phobos know that filters always preserve order?

I'd have to read the documentation to find out which of these uses binary search. In fact, I'd probably have to read the Phobos source.

If I just used binarySearch then I would be 100% guaranteed that it will use a binary search. I don't have to second guess the compiler -- I just *know*.
May 17, 2012
On Thu, 17 May 2012 09:50:44 +0100, Lars T. Kyllingstad <public@kyllingen.net> wrote:

> On Thursday, 17 May 2012 at 03:15:47 UTC, Jordi Sayol wrote:
>> Al 17/05/12 03:32, En/na Walter Bright ha escrit:
>>> On 5/16/2012 12:29 AM, bearophile wrote:
>>>> Then why is Andrei using the name std.algorithm.schwartzSort?
>>>  May the schwartz be with you.
>>>
>>
>> Very appropriate :-)
>> On 27 May is the 35 anniversary of the first released film from the Star Wars series.
>
> Walter's quote was from "Spaceballs". :-)

Ahh.. I see your schwartz is as big as mine :p

R

-- 
Using Opera's revolutionary email client: http://www.opera.com/mail/
May 17, 2012
On 5/17/12 4:00 AM, Peter Alexander wrote:
> On Tuesday, 15 May 2012 at 17:23:28 UTC, Kirill wrote:
>> How about users who don't know what binary search is. binary search is
>> an intuitive concept for people who have good programming experience
>> but assumeSorted(r).contains(x) is more intuitive to higher level users.
>
> If you don't know about binary search, you won't write
> assumeSorted(r).contains(x) you'll just write r.contains(x) because you
> have no idea that binary search exists. Why would you bother typing
> extra characters for a benefit that you are unaware of?
>
> If you do know that binary search exists then the obvious algorithm name
> is binarySearch. If I use .contains to coax a binarySearch then I'm
> relying on a little bit of faith. In what situations does it give a
> binary search?
>
> [1, 2, 3].contains(2); // does the compiler infer that 1, 2, 3 is sorted?

Doesn't compile.

> iota(10).contains(5); // is iota implicitly a sorted range?

Doesn't compile.

> assumeSorted([1, 2, 3]).map!(x => x + 1).contains(3); // does Phobos
> know that the map is order preserving?

Doesn't compile, this would:

assumeSorted([1, 2, 3].map!(x => x + 1)).contains(3)

(which is quite a trick; map figures the input is a random-access range and exposes a random-access interface as well. Good luck doing that in other languages.)

> assumeSorted([1, 2, 3]).filter!("a & 1").contains(2); // does Phobos
> know that filters always preserve order?

Doesn't compile, and couldn't because filter() cannot preserve random access.

> I'd have to read the documentation to find out which of these uses
> binary search. In fact, I'd probably have to read the Phobos source.
>
> If I just used binarySearch then I would be 100% guaranteed that it will
> use a binary search. I don't have to second guess the compiler -- I just
> *know*.

I agree binarySearch is more precise, but I also think it's a minor issue not worth the cost of changing at this point. Improving names of things in the standard library is a quest that could go forever, make everybody happy we're making progress, and achieve no substantial gain.


Andrei
May 17, 2012
Andrei Alexandrescu:

> I agree binarySearch is more precise, but I also think it's a minor issue not worth the cost of changing at this point. Improving names of things in the standard library is a quest that could go forever, make everybody happy we're making progress, and achieve no substantial gain.

Names are very important, they are the fist and most important part of an API, they are the first handle for human programmers and their minds. The amount of care Python development group gives to the choice of names is visible and it makes a difference in Python usability.
Important names can't be chosen by a single person, because single persons have quirks (they overstate how much common a word or concept is, etc etc). So important names are better chosen by groups, that allow to average out those quirks.
I suggest to stick somewhere inside Phobos a name like "binarySearch".

Bye,
bearophile
May 17, 2012
On Thu, May 17, 2012 at 10:26:18AM -0500, Andrei Alexandrescu wrote:
> On 5/17/12 4:00 AM, Peter Alexander wrote:
[...]
> >I'd have to read the documentation to find out which of these uses binary search. In fact, I'd probably have to read the Phobos source.
> >
> >If I just used binarySearch then I would be 100% guaranteed that it will use a binary search. I don't have to second guess the compiler -- I just *know*.
> 
> I agree binarySearch is more precise, but I also think it's a minor issue not worth the cost of changing at this point. Improving names of things in the standard library is a quest that could go forever, make everybody happy we're making progress, and achieve no substantial gain.
[...]

Why not just add something like this then:

	E binarySearch(R,K)(R range, K key)
	{
		return assumeSorted(range).contains(key);
	}

Nobody says we have to change the names of existing code. Adding a wrapper with a nice name works just fine, and doesn't break any existing code, etc..


T

-- 
Who told you to swim in Crocodile Lake without life insurance??
May 17, 2012
On Thursday, 17 May 2012 at 15:26:19 UTC, Andrei Alexandrescu wrote:
> I agree binarySearch is more precise, but I also think it's a minor issue not worth the cost of changing at this point. Improving names of things in the standard library is a quest that could go forever, make everybody happy we're making progress, and achieve no substantial gain.

No need to change anything, just add something:

bool binarySearch(Range, Value)(Range range, Value value)
{
    return assumeSorted(range).contains(value);
}

(constraints, predicates and the myriad of qualifiers/decorations omitted for clarity).
May 17, 2012
On Thu, May 17, 2012 at 06:52:26PM +0200, Peter Alexander wrote:
> On Thursday, 17 May 2012 at 15:26:19 UTC, Andrei Alexandrescu wrote:
> >I agree binarySearch is more precise, but I also think it's a minor issue not worth the cost of changing at this point. Improving names of things in the standard library is a quest that could go forever, make everybody happy we're making progress, and achieve no substantial gain.
> 
> No need to change anything, just add something:
> 
> bool binarySearch(Range, Value)(Range range, Value value)
> {
>     return assumeSorted(range).contains(value);
> }
> 
> (constraints, predicates and the myriad of qualifiers/decorations
> omitted for clarity).

Great minds think alike. ;-)


T

-- 
It said to install Windows 2000 or better, so I installed Linux instead.