The last few weeks something bothered while working on Protocols PEP: protocols should be ideally compact (and PEP already emphasizes this).
However, the only potential candidates for __getitem__ are Sequence and Mapping, that are both quite bulky (half dozen members each). I was thinking about different options like adding BaseMap as a base for Mapping and Sequence that will only have __getitem__. I expect this to be a popular protocol, since often people just need something that can be subscripted.

Fortunately I stumbled into this issue. It looks like the optimal way now is:

* Have an abstract base class (let's call it BaseMap, although I don't really like this name) in collections.abc that has only __getitem__ method.
* It will be inherited by both Sequence and Mapping, but for the purpose of static typing, Sequence[T] will be a subtype of BaseMap[int, T], while Mapping[KT, VT] will be a subtype of BaseMap[KT, VT].
* BaseMap will be contravariant in key, this will solve problems with Mapping (invariant in key), for example a function that expects BaseMap[str, int] will accept Dict[Union[str, unicode], int].
* BaseMap will be a protocol in typing, so that people can extend it depending on their needs (e.g. add a .get() method).

Guido, Łukasz if you agree, then I will add this to the Protocols PEP and  will make a PR to collections.abc. We need to agree on the name, there are two options now: BaseMap and Indexable. I don't like the second since I would rather have it as a generic alias: Indexable = BaseMap[int, T]. However, BaseMap is also not very good, since I want something more "neutral" between Mapping and Sequence.