Why does Seq[V] not extend Map[Int,V] nor does Set[V] extend Map[V,Bool]?

Question

The three immediate subtypes of Iterable are Map, Seq, and Set. It seems like—aside from performance issues—a Seq is a map from integers to values, and a Set is a map from values to booleans (true if the value is in the set, false otherwise).

If this is the case, why is this not expressed in the type system by making Seq[V] extend Map[Int, V] and Set[V] extend Map[V, Boolean]?

Answer 1

Well, they sort of do, at least actually common functionality. Seq[B] inherits from Int => B (via PartialFunction[Int, B]), Map[A, B] inherits from A => B (also via PartialFunction[A, B]), and Set[A] inherits from A => Boolean. Thus, as far as function application and composition methods are concerned, all three can be used interchangeably. Additionally, they can be used interchangeably as far as traversal goes, as all implement TraversableLike.

Answer 2

Seeing a sequence as an assignment from integers to elements is only one way to describe what a sequence is. There are other ways, and there is no reason why that way of describing a sequence should become canonical. The actual purpose of a sequence is to make a bunch of elements accessible and traversable. A sequence is not required to actually assign integer numbers to the elements. For example, most Stream implementations probably don't have a counter running in parallel to the traversal. Requiring that would impose an unnecessary overhead on the implementation.

Besides, a Map[K,V] is also an Iterable[(K,V)]. Following your suggestion, a Seq[A] would also have to be a Map[Int,A], which would by that also make it an Iterable[(Int,A)]. Since Seq extends Iterable, this would make the Seq[A] both an Iterable[A] and an Iterable[(Int,A)] (and, recursively, an Iterable[(Int,(Int,A))], Iterable[(Int,(Int,(Int,A)))], and so on), which is not an allowed way of inheritance in Scala.

You can construct a similar argument for your suggestion regarding Set.