"in" everywhere

[bearophile]

Andrei Alexandrescu:

> I'm a bit leary of adopting this feature (it has been discussed). To me 
> "in" implies a fast operation and substring searching isn't quite it.
> 
> One thing that could be done is to allow "in" with literal arrays to 
> their right:
> 
> if (x in ["abcde", "asd"]) { ... }
> 
> The size of the operand is constant, known, and visible.

The "in" is useful to tell if an item is present in a collection (dynamic arrays, fixed-sized arrays, sorted arrays, tuple, typetuple, hash set, tree set, hash map, tree map, trees, graph, deque, skip list, finger tree, etc), and it's useful to tell if a substring is present in a string. Those two purposes are very commonly useful in programs.

Despite those purposes are very common, there is no need for an "in" syntax. In dlibs1 I have created an isIn() function that was good enough.

D supports the "in" operator for associative arrays, and in its operator overloading (my Set()/set() implementation supports the "in" operator), so it's natural for people to desire that operator to be usable for the other kind of collections too, like arrays. Maybe those people have used Python, where the in operator (__contains__) is widey used.

Regarding generic programming, Python doesn't have templates, but it has dynamic typing, that also has purposes similar to generic programming. To a python function that uses the "in" operator you may give both a list and an associative array, or other objects that support the __contains__. In this case the Python code performs an O(n) or O(1) operation according to the dynamic type given to the function.

I can live without the "in" operation for arrays and strings (useful to look for substrings too). So one solution is not not change the D language, and not add support for "in" to arrays.

Another solution is just to accept O(n) as the worst complexity for the "in" operator. I don't understand what's the problem in this.

Another solution is to support the "in" operator for dynamic arrays too, and define a new attribute, like @complexity(), plus an Enum that allows to specify the worst case complexity. So associative arrays are annotated with @complexity(O.linear), while the function that searches for items/substrings in arrays/strings is @complexity(O.constant). At compile-time the generic code is then able to query the computational complexity of the "in" operator implementation. The problem is that the compiler today can't enforce functions annotated with @complexity(O.constant) to actually not perform a linear search (but I don't think it's a problem, today if the Range protocol asks an operation to not be worse than O(n ln n) the compiler doesn't enforce it).

I don't like the idea of allowing the "in" operator for sorted arrays, tuples, fixed-sized arrays, skip lists, maps, sets, trees and disallow it for dynamic arrays. It looks a bit silly. People for the next ten years will then ask "in" to be extended for unsorted dynamic arrays & substring search too, you can bet on it.

Bye,
bearophile