No typeclasses for Seq

[ephemerist]

I see there are typeclasses under cats.std for List and Vector (among others), but none for Seq. Is there a reason no typeclasses for Seq are provided? If it's simply that there's been no demand previously, then I'm happy to raise a PR to add this.

[ceedubs]

Thanks for bringing this up, @aebrett. This is a question that comes up every once in a while on Gitter, but it looks like we currently don't have an explanation of this in the docs anywhere (such as in the FAQ).

The short answer is that Seq doesn't tell you much. Unlike List or Vector, you don't know what the performance characteristics of a Seq instance are going to be, so you don't necessarily know the best way to implement methods in the type class instance. It may be mutable, in which case mySeq.map(identity) can't simply be rewritten as mySeq without potentially changing the meaning of your program.

In general, I think that when you are trying to abstract over collections, it's better to do something like def foo[F[_]:Functor, A](fa: F[A]) than to do something like def foo[A](fa: Seq[A]). This is more flexible for consumers of your method, and it also makes it so that your method can return F[A] without losing information about the input type and simply returning Seq[A].

Having said all of that, Seq shows up a lot in Scala code, and there should be instances available when people want them. Given the properties of Seq mentioned above, I think that alleycats is probably a good place for these instances (see also non/alleycats#38 and #472).

[johnynek]

While I agree that Seq is not the greatest abstraction (for many of the reasons mentioned above), it is the standard library and users will sometimes have to deal with Seq.

It is unfortunate that Seq may or may not be mutable, but would it violate any laws to implement Foldable or Traversable or Monad?

I don't see how. Can you demonstrate a failure case?

I also think we do more service to users by giving them these instances rather than tell them to go add yet another dependency.

[ceedubs]

@johnynek I think it depends on what your definition of equality is for the laws. For example, the functor laws say that I should be able to freely replace fa.map(identity) with fa, but that's not necessarily the case with mutable sequences. See this conversation.

Also, are we referring to scala.collection.Seq or scala.collection.immutable.Seq? The former appears more often, but the latter has a smaller chance of making people potentially run into issues.

I keep swinging back and forth on this sort of thing. On the one hand, I don't want to automatically throw stuff that might cause issues for someone into their implicit scope when they import cats.implicits._. On the other hand, I think that people probably generally know that if they mutate objects then that will affect the results that they get.

[johnynek]

"On the other hand, I think that people probably generally know that if they mutate objects then that will affect the results that they get."

I agree with this.

In my view, we should show a problem using best practices. If we have to use exceptions, nulls, casting, or mutation to show an issue, in my mind, that is mostly showing the danger of those practices and not reason to avoid support in cats.

So, to my way of thinking, if you pass a mutable Seq to a method wanting F[A] with F[_]: Functor in my mind, if you expect it must make an internal copy or there will be bugs, that is on you, and not a bug with cats.

That said, I have never needed these types for Seq, nor are they very hard to make if needed. I just hope we won't get overly prescriptive about what we support.

[travisbrown]

Another issue with Seq instances is that we have to worry about prioritization with respect to the instances for List, Vector, etc. Even apart from that, unless we introduce a bunch of CanBuildFrom-like machinery, we're going to end up pushing types up to Seq in ways that may be surprising to people who are used to the standard collections library.

I personally couldn't care less about the issues related to the fact that Seqs may be mutable, but I still think Seq instances would introduce more complications than they're worth.

[boggle]

FFW I have to work with a lot of tree structures containing Seqs. Turning these into lists or vectors manually all the time gets annoying soon (barring defining an implicit conversion).

[ArturGajowy]

It may be mutable, in which case mySeq.map(identity) can't simply be rewritten as mySeq without potentially changing the meaning of your program.

https://gitter.im/typelevel/cats?at=574da9f4da3f93da6f21fa7e

Why not just provide the instances for immutable.Seq? Would such a PR be accepted? Would the issues @travisbrown mentions apply?

[djspiewak]

FWIW, I don't see anything unlawful about implementing instances for immutable.Seq. The issue would be more one of prioritization and ambiguity, but we already have that problem with the traverse and monad syntax, so… shrug. Seq is horrible, but people do still use it, unfortunately.

[joan38]

I was wondering is the new collections from 2.13 changing anything?
I'm saying that since Seq is becoming immutable.Seq

[eugeniyk]

Imo Seq is good abstraction from the read side, but when it comes to modifications you either going to reflection dark world or have explicit-implicit factories, so.. shrug

[LukaJCB]

I think there's no real principled reason to leave out immutable.Seq, it has some problems and having typeclass instances for both a supertype and a subtype in the same hierarchy can be a bit trickty, but we already have precedent on that with Map and SortedMap.
I'm therefore very neutral on this issue, but if someone wants to put together a PR to provide immutable.Seq instances, I'd be inclined to merge that PR :)

[ryan-richt]

Just adding that this (only having instances for List and Vector for for instance, NonEmptyParallel) bit us today, and thanks to stack overflow found this thread. Maybe the instances could go in alleycats if there is dispute on purity, so users could invite those implicits in knowingly?