"in" everywhere

[Steven Schveighoffer]

On Tue, 12 Oct 2010 10:48:26 -0400, Stewart Gordon <smjg_1998 at yahoo.com>  
wrote:

> On 10/10/2010 02:05, Jonathan M Davis wrote:
>> On Saturday 09 October 2010 06:54:31 Stewart Gordon wrote:
> <snip>
>>> Surely, what matters most for generic code is that in has consistent
>>> _semantics_, rather than the computational complexity?
>>>
>>> Stewart.
>>
>> _Both_ matter.
>
> True, yet you don't address semantic differences at all in what follows,  
> so it doesn't really follow on from what I said.  But anyway....
>
>> Imagine, for instance, if we were to make Java's mistake of having List  
>> be an
>> interface which ArrayList and LinkedList implement and that List has a  
>> get()
>> function. Using ArrayList, get() has a complexity of O(1). Using  
>> LinkedList, it
>> has a complexity of O(n).
>
> Are you suggesting we just don't have a List interface, just to prevent  
> people from writing algorithms that work well in some list  
> implementations but poorly in others?  I'm not sure if that risk  
> outweighs any benefits....

No, what is suggested is that we build the complexity guarantees into the  
interface.  For example, if you had a List interface, and it could only  
guarantee O(n) performance for get, you'd call it e.g. slowGet(), to  
signify it's a slow operation, and define get to signify a fast  
operation.  Similarly, 'in' is defined to be fast, so it has no business  
being a function on an array.

So you can still have the List interface, but you don't hijack the "fast  
operation" of 'in' with a slow operation.  This allows it to still provide  
the slow operation, just not in a way that makes generic code use it  
assuming it is fast.

-Steve