Generic function for Scala sequences like `Seq`, `IndexedSeq`, `List`

Question

I have a function which wraps around Seq.tail. I would like the function to return List for List, IndexedSeq for IndexedSeq, Seq for Seq.

Currently I use asInstanceOf to work around the fact tail always returns Seq to me.

    def skipRoot[S <: Seq[String]](path: S): S = {
      assert(path.head.nonEmpty)
      path.tail.asInstanceOf[S] // a nicer generic solution?
    }

    val list: List[String] = skipRoot("a" :: Nil)

I guess there must be a nicer way, perhaps using higher kinded types?

All of those have `tail` method declared. Why not just using it? — Tomer Shetah, Nov 23 '20 at 11:21
Because I want to perform the assertion about the head content. — Suma, Nov 23 '20 at 11:24
https://stackoverflow.com/questions/64209514/t-a-return-t-method https://stackoverflow.com/questions/52479695/type-mismatch-on-abstract-type-used-in-pattern-matching https://stackoverflow.com/questions/64467354/type-safety-with-adt-and-aux-pattern https://stackoverflow.com/questions/64318180/generic-function-where-the-return-type-depends-on-the-input-type-in-scala https://stackoverflow.com/questions/61668592/why-cant-i-return-a-concrete-subtype-of-a-if-a-generic-subtype-of-a-is-declared — Dmytro Mitin, Nov 23 '20 at 11:35

amorfis · Answer 1 · 2020-11-23T11:51:59.127

3

You use only head and tail methods. Both are declared in scala.collection.IterableOps, so why not use it?

def skipRoot[S <: IterableOps[PathItem]](path: S): S = { ... }

EDIT for Scala 2.12:

Try this:

skipRoot[S <: GenTraversableLike[String, S]](path: S): S = {...}

edited Nov 23 '20 at 11:51

answered Nov 23 '20 at 11:24

amorfis

15,390
15
77
125

It should also be `assert(path.headOption.exists(_.isRoot))` to avoid throwing a different exception when the path is empty. – Tim Nov 23 '20 at 11:27
1

Then you should find `tail` and `headOption` in `scala.collection.GenTraversableLike` – amorfis Nov 23 '20 at 11:30
@amorfis I guess `scala.collection.IterableOps` has 3 type parameters, not one. – Dmytro Mitin Nov 23 '20 at 17:36

slouc · Answer 2 · 2020-11-23T13:20:30.323

When you use subtyping, once you go "up", the only idiomatic way to go "down" is pattern matching.

For example,

val apple: Apple = new Apple()
val fruit: Fruit = apply

fruit match {
    case Apple() => // ...
    case _ => // ...
}

However, due to type erasure, this is not a good solution for your problem.

First solution

If you are willing to abandon subtyping altogether, you can use type classes which can solve this problem quite elegantly:

trait Foo[A, F[_]] {
  def skipRoot(path: F[A]): F[A]
}

implicit def fooList[A] = new Foo[A, List] {
  def skipRoot(path: List[A]): List[A] = path.tail
}

implicit def fooVector[A] = new Foo[A, Vector] {
  def skipRoot(path: Vector[A]): Vector[A] = path.tail
}

def genericSkipRoot[A, F[_]](collection: F[A])(implicit ev: Foo[A, F]) =
  implicitly[Foo[A, F]].skipRoot(collection)

genericSkipRoot(List(1, 2, 3))   // List(2, 3)
genericSkipRoot(Vector(1, 2, 3)) // Vector(2, 3)

Sure, you have to define explicit typeclass instances for all types that you want to use, but you gain a lot of flexibility, plus it's idiomatic. And you can even define instances for collections from other libraries that don't happen to extend Seq.

Second solution

If you want to keep subtyping, you need to use Scala 2.13 in which the collections library went through some redesign.

There, you will find that there's a trait

trait IterableOps[+A, +CC[_], +C]

which, as you can see, retains information about the collection. Your method then becomes:

def foo[S <: immutable.SeqOps[_, Seq, S]](sa: S): S = sa.tail
  
foo(List(1, 2, 3))   // List(2, 3)
foo(Vector(1, 2, 3)) // Vector(2, 3)

(note that you need to avoid the A parameter in order to make it compile, because you need to return just S and not S[A])

What I like on the typeclass approach is that is does not require any knowledge of collection internals. It may seem complex at first sight, but it is easy to understand and portable between Scala versions. — Suma, Nov 23 '20 at 13:11
Exactly! You can also easily use different typeclass implementations (there can be more than one instance of `Foo[Int]` and you can choose which one to bring into scope). And you can use different implementations for different types, rather than restricting yourself to a generic `path.tail`. And as I already said, you can define instances even for collections that don't extend `Seq`. — slouc, Nov 23 '20 at 13:22
@slouc Regarding second solution if we want `assert(path.head.nonEmpty)` (or `assert(path.head.isRoot)`) to compile we should add `String` (or `PathItem`) bound somewhere: `def foo[S <: immutable.SeqOps[_ <: String, Seq, S]](sa: S): S` (or `_ <: PathItem`). — Dmytro Mitin, Nov 23 '20 at 17:43
@slouc Similar modifications should be made in typeclass solution as well. — Dmytro Mitin, Nov 23 '20 at 17:46

Dmytro Mitin · Accepted Answer · 2020-11-23T13:17:39.273

2

Try

def skipRoot[S[X] <: IterableOps[X, Seq, S[X]]](path: S[String]): S[String] = {
  assert(path.head.nonEmpty)
  path.tail
}

Or Scala 2.12:

def skipRoot[S[X] <: GenTraversableLike[X, S[X]]](path: S[String]): S[String] = {
  assert(path.head.nonEmpty)
  path.tail
}

In Scala 3 you can also have a signature

def skipRoot[S[X] <: Seq[X] { def tail: S[X] }](path: S[String]): S[String]

https://scastie.scala-lang.org/DmytroMitin/vA42tuUlRJSvTHAKiPzzbQ/3

edited Nov 23 '20 at 13:17

answered Nov 23 '20 at 11:58

Dmytro Mitin

48,194
3
28
66

Abstracting over collections without a typeclass approach is just unnecessarily complex. Also, most of the generic or abstract collection types do not make a guarantee about performance of any of their operations. – Luis Miguel Mejía Suárez Nov 23 '20 at 13:02
@LuisMiguelMejíaSuárez Can be true although typeclass approach (`CanBuildFrom`) in 2.12 was reconsidered in 2.13 collections. Implicit resolution is not a panacea because it has its own edge cases. It's also worth mentioning that typeclasses themselves (without laws or other conventions) do not make performance guarantees either. – Dmytro Mitin Nov 23 '20 at 13:14
1

First, this was intended for OP but I commented in the wrong place _(sorry)_ - Second, yeah even typeclasses has its limitations, that si why I consider in general abstracting over collections a bad idea because - Third, my second comment was in general not about subtyping specifically, a collection type is a very important decision on most of the cases, sure you can write generic helpers that do a couple of `maps`, `filters`, `folds` or things that traverse all the collection _(which IMHO are better modelled by thing like **Functor**)_; but for more advanced algorithms it is bad idea. – Luis Miguel Mejía Suárez Nov 23 '20 at 13:35

Generic function for Scala sequences like `Seq`, `IndexedSeq`, `List`

3 Answers3