Complexity nomenclature

[Timon Gehr via Digitalmars-d]

On 12/04/2015 03:35 AM, Andrei Alexandrescu wrote:
> On 12/03/2015 09:24 PM, Timon Gehr wrote:
>> On 12/04/2015 03:18 AM, Andrei Alexandrescu wrote:
>>> On 12/03/2015 08:37 PM, Jack Stouffer wrote:
>>>> On Friday, 4 December 2015 at 01:27:42 UTC, Andrei Alexandrescu wrote:
>>>>> These complexities must be reflected in the name of the primitives.
>>>>
>>>> I don't see why. IMO, names should convey what the function does, not
>>>> how it does it. Complexity is usually put in the function documentation
>>>> in Phobos when it's not constant, especially for range based ones, I
>>>> don't see a reason to change that.
>>>
>>> Complexity is part of the semantics, and in my design names and their
>>> semantics go hand in hand. -- Andrei
>>>
>>
>> Which is sensible. But in any given context, some parts of the semantics
>> are usually abstracted away. Sometimes one wants to abstract over
>> running times of called methods. ("This function calls this other
>> function at most O(n) times.")
>
> Sure, and there will be provision for that. The collections framework
> will contain logic such as: "If collection type C implements
> insertAfter, then implement UFCS function linearInsertAfter that
> forwards to it". So if as user you're fine with linearInsertAfter, it'll
> work as an upper bound. -- Andrei

This only works if the module imports std.container. Also, I might be 
okay with arbitrary running times, even super-linear. There's also the 
case where I want to implement a wrapper around a generic container. I 
will then need to provide static introspection in order to expose the 
methods with the correct names.