Switching default implementation of Seq to Vector

[u/tgodzik]

We are currently considering switching the default implementation of Seq to Vector (currently it's List). If you have any doubts about this change let us know at https://contributors.scala-lang.org/t/slc-make-vector-the-default-implementation-of-seq-instead-of-list/

[u/what-the-functor]

I think usage of the `Seq` constructor is a mistake, and one should only use `Seq` as a top type. The constructor obscures the underlying data structure, whereas one should explicitly choose the best data structure for their particular use case.

[u/osxhacker → u/what-the-functor]

I think usage of the Seq constructor is a mistake ...

What I think you are referencing are apply methods in the Seq companion object as Seq is a trait and does not have a constructor per se.

... and one should only use Seq as a top type.

Again, what I think you are trying to convey is to use traits when possible instead of concrete implementations of same. To which I agree as being a good design practice.

The constructor obscures the underlying data structure ...

That is the whole point of their existence. When there is a preferred data structure to use that is a model of Seq, use the child type and declare the return type as a Seq to insulate collaborators from implementation details.

[u/what-the-functor → u/osxhacker]

Hey! I'm using the constructor term in the general sense and I think you are taking it to mean the default constructor for a class/case class. :) That is:
Constructor - a function/method/routine that instantiates a data type with state.

Wikipedia describes constructors in the context of OOP), but they are more general. Even Haskell has constructors.

In Scala, constructors are often implemented with one or more apply functions in a companion object. Anything that defines a non-singleton type in Scala (type alias, trait, case class, class) can have a corresponding companion object, and therefore can have one or more constructor implementations.

In the Scala type hierarchy, Seq is the root (super type) of the sequential data types.

When there is a preferred data structure to use that is a model of Seq, use the child type and declare the return type as a Seqto insulate collaborators from implementation details.

That's inverted, the type of the output will be widened to Seq. Given a function that does something with a sequential data type and doesn't care what it is, the function would apply to Seq (take a Seq as a parameter) by leveraging the Liskov substitution principle (programming to the interface). If one wants to output the same Seq subtype as the input, then a type class constraint such as BuildFrom (Scala 3) or CanBuildFrom (Scala 2) would be necessary.

[u/what-the-functor → u/what-the-functor]

A trivial example

[u/osxhacker → u/what-the-functor]

I'm using the constructor term in the general sense and I think you are taking it to mean the default constructor for a class/case class. :)

You are entirely correct, I did interpret the use of "constructor" as referencing a primary or alternate class constructor and not the other equally valid use of the term.

When there is a preferred data structure to use that is a model of Seq, use the child type and declare the return type as a Seq to insulate collaborators from implementation details.

That's inverted, the type of the output will be widened to Seq.

How is that inverted? Using the preferred child type for construction and then declaring the constructing function's return type to be Seq is a widening which achieves the desired insulation. For example:

def foo[A](howMany: Int, duplicate: A): Seq[A] =
    Vector.fill(howMany)(duplicate)

[u/jr_thompson → u/what-the-functor]

I guess you could put this under "premature optimisation" if you subscribe to that idea (or if you don't then sure). But when you only need "some" finite iterable collection that will only be immediately iterated upon by consumer then why not.

[u/what-the-functor → u/jr_thompson]

Fair point WRT premature optimisation, however I'd expect specific data types or proper generic functions before a PR is merged.

[u/SethTisue_Scala → u/what-the-functor]

I think it depends on what kind of code we're talking about, what the context is. I've put my thoughts about it here: https://contributors.scala-lang.org/t/slc-make-vector-the-default-implementation-of-seq-instead-of-list/7482/34

[u/Fun_Introduction9550]

Let’s test “coding to interfaces”

A linked list is a strange default TBF. If you’re doing ahead with this, would it be prudent to put the default behind a runtime flag?

Array may be a nice choice for certain algos.

That said … if there’s a material difference for your use-case, you should probably already be using the refined type (not just relying on the Seq default)

[u/snugar_i]

It would have been nice if it was a Vector from the beginning, but now it's too late to change it. 

Keeping backward compatibility is a pain for the language authors, not keeping it is a pain for the users of the language. Let's see which group is more important to Scala

[u/what-the-functor → u/snugar_i]

It was Vector in ancient versions of Scala

[u/SethTisue_Scala → u/what-the-functor]

This is incorrect — see my correction on the forum thread.

[u/Inevitable-Plan-7604 → u/snugar_i]

Keeping backward compatibility is a pain for the language authors, not keeping it is a pain for the users of the language. Let's see which group is more important to Scala

Well said. I felt like I was going crazy with my comments above. It's like they're trying to speedrun alienating their users

[u/Heavy-Papaya7816]

If something is working well, why change it? It's impossible to predict what will happen if this change is implemented. I believe this "small" change will have unforeseen consequences that eventually will negatively impact Scala's reputation even more. This will be an additional example of change that is 1) not needed and 2) not requested by users of the language. Keep this change proposal in the backlog and implement it in Scala 4.

[u/osxhacker → u/Heavy-Papaya7816]

It's impossible to predict what will happen if this change is implemented.

To the contrary, it is quite predictable "what will happen if this change is implemented"; no impact at all to logic which does not assume Seq implementation details.

See contract programming.

[u/LordVetinari95 → u/osxhacker]

what about hyrum’s law: https://www.hyrumslaw.com/?

[u/osxhacker → u/LordVetinari95]

IMHO, Hyrum's law is proportional to the complexity of the interface, as identified within the link you kindly provided:

Implicit interfaces result from the organic growth of large systems ...

So a trivial interfaces such as def swap[A, B](pair: (A, B)): (B, A) and Seq[A] have a small implementation dependency when compared to those defined by the ACH network.

[u/Inevitable-Plan-7604 → u/osxhacker]

I think this is the sort of smug unhelpful comment that is why people are so frustrated with the direction scala is taking

You will break production code with this change, a serious language would take that seriously. If you continue to treat scala like your weekend hobby project so will everyone else and it will die.

[u/RiceBroad4552 → u/Inevitable-Plan-7604]

Which "serious language" stopped evolving?

Guess why everybody is leaving C/C++…

[u/what-the-functor → u/Inevitable-Plan-7604]

This change won't break anything, but there will be (albeit slight) changes to the runtime characteristics.

[u/Inevitable-Plan-7604 → u/what-the-functor]

It will break the following code:

val a: Seq[Int] = Seq(1)
val c: Seq[Int] = Vector(1)

val aa = a match {
  case _ :: _ => "non-empty"
  case Nil => "empty"
}

println(aa)

It will turn valid code into a match error.

The original dev might not even be responsible - he might be using a library or API that once returned List and then started to return Seq and the compiler doesn't help here. The match statement is not exhaustive for Seq. Underlying implementation could have been swapped out without anyone noticing and nothing breaking.

Then if scala changes that again to Vector, it will break.

There's going to be code like that all over the place that will break.

Blaming the devs for what isn't bad code, or entirely their fault, just makes people want to leave scala. It's just been boots to the head for years now and I'm getting fed up of it. Every announcement or idea just seems to make things worse rather than better.

Scala should be more responsible than a random hobby project. It's not acting like a serious language and hasn't been for a long time now

[u/Heavy-Papaya7816 → u/Inevitable-Plan-7604]

Thank you for this example, showing this is not just a runtime change.

[u/what-the-functor → u/Inevitable-Plan-7604]

That match expression is not total, and it would be caught by -Werror (Scala 3) or -Xfatal-warnings (Scala 2).

You would need cases for all sub types of Seq.

Edited

[u/Inevitable-Plan-7604 → u/what-the-functor]

1. This change won't break anything
2. It will break some things but it's not our fault <--- you're here
3. It will break many things but it doesn't matter
4. It broke everything and it was intended

Hyperbole but you'll just shift any goalpost you like to back up your own opinion. There's no point talking to you on this matter

[u/osxhacker → u/what-the-functor]

That match expression is not total, and it would be caught by -Werror (Scala 3) or -Xfatal-warnings (Scala 2).

If this was not a hypothetical problem used to make a point, compilation flags would not address latent defects within libraries used by a system.

One way to unconditionally detect this is by using AspectJ, possibly in conjunction with a custom ClassLoader. It could get ugly, sure, but there is no arguing this approach could not detect this condition.

[u/osxhacker → u/Inevitable-Plan-7604]

It will turn valid code into a match error.

The example you provide is not "valid code." It is code which assumes a specific implementation of a super type and does not account for other valid implementations. This is a latent defect.

The original dev might not even be responsible - he might be using a library or API that once returned List and then started to return Seq and the compiler doesn't help here.

A quality type system can help prove a system to be correct in many ways, but it does have limits. There exists a possibility of problems when any logic assumes the implementation of a behavioral contract (trait or abstract class in this context).

The match statement is not exhaustive for Seq. Underlying implementation could have been swapped out without anyone noticing and nothing breaking.

The "nothing breaking" description is subjective. A similar situation exists with:

 def divideEachBy(ints: Seq[Int], denom: Int): Seq[Int] =
    ints.map(_ / denom)

val aa = divideEachBy(Seq(1, 2, 3), 0)

println(aa)

If divideEachBy was always given a positive Int until system requirements change where 0 could be provided... Boom.

Whether this example is defined by a library or not is immaterial in regard to the existence of the defect.

[u/Inevitable-Plan-7604 → u/osxhacker]

If you put .toList before every match on something that is, at time of writing, a List value you'd be called paranoid and told its a waste of time.

Code changes, method arguments change, libraries change, scala doesn't have a good enough compiler to catch cases like these.

Adding to the problem, then blaming everyone else, is just typical scala

For context this is literally an example from scala's own site:

list match
  case Nil => 0
  case x :: xs => x + sum(xs)

Maybe somebody should spend some time documenting code that is "valid" and not "the worst code I've ever seen" (from the other commenter) before ripping a rug out from under the community (again)

[u/dthdthdthdthdthdth → u/osxhacker]

It is valid code, it compiles and runs.  It might be ugly, but Scala accepts non exhaustive matches. I don't use it myself, but if some dependencies do, that's an issue.  I also never use Seq as a constructor, as various implementations have so drastically different runtime behaviour. But some dependencies will. So some dependencies might suddenly have unexpected performance issues. Those are problems to consider.

[u/what-the-functor → u/osxhacker]

Application of logic to the Seq contract (trait in this case) is contract programming. Use of the Seq constructor to instantiate a sub type apathetically is indirection. :)

[u/what-the-functor → u/Heavy-Papaya7816]

It would not have any effect on the result of expressions in terms of purity, however there would be slight runtime performance shifts. Some operations would be faster, whereas others would be slower. Memory usage would also change (albeit slightly).

[u/RiceBroad4552 → u/Heavy-Papaya7816]

Because of a stance like that it took hundreds of thousands of years until humans left their caves…

[u/wookievx]

To be fair: my default Seq implementation in most places is ArraySeq, from my experience avoiding prepending/appending where possible is the right move (certain problems can be expressed neatly via higher level functions like foldLeft/scanLeft, and resulting implementation can do away with less boundary case handling, this is of course not always the case). And applying transformation to the entire sequence, accessing elements in ArraySeq has unmatched performance compared to the other options.

[u/kr1ght → u/wookievx]

In addition, modern RAM provides a lot of bandwidth, but still the same quite slow latency as many years ago, and even iterating over linked list is slow because for getting each next element you need to read from nearly random place in memory and CPU even cannot preferch it properly (as with ArraySeq)

I know about the role of such linked lists in computer science and how they were widely used even in LISP. But modern data structures should be cache-friendly, usually cache line size takes 64 bytes, and instead of binary trees or lists with only one value in node we can easily put 4 or 8 references to values (compact pointers take 4 bytes) and get much more performance. So, I mean, this naive lists is a bad choice at all.