How to create a custom Seq with bounded type parameter in Scala?

Question

Consider the following working custom Seq:

class MySeq[B](val s: Seq[B]) 
extends Seq[B]
with GenericTraversableTemplate[B, MySeq]
with SeqLike[B, MySeq[B]] {
  override def companion = MySeq

  def iterator = s.iterator

  def apply(i: Int) = s(i)

  def length = s.length

  override def toString = s map { _.toString } mkString("\n")
}
object MySeq extends SeqFactory[MySeq] {
  implicit def canBuildFrom[B]: CanBuildFrom[Coll, B, MySeq[B]] =
       new GenericCanBuildFrom[B]
  def newBuilder[B] = new ListBuffer[B] mapResult (x => new MySeq(x.toSeq))
}

I would like to impose a bound on the type parameter B. In other words, I would like something like this (not working):

class MyA

class MySeq[+B <: MyA](val s: Seq[B]) 
extends Seq[B]
with GenericTraversableTemplate[B, MySeq]
with SeqLike[B, MySeq[B]] {
  override def companion = MySeq  // Type Mismatch Here

  def iterator = s.iterator

  def apply(i: Int) = s(i)

  def length = s.length

  override def toString = s map { _.toString } mkString("\n")
}
object MySeq extends SeqFactory[MySeq] {
  implicit def canBuildFrom[B]: CanBuildFrom[Coll, B, MySeq[B]] =
       new GenericCanBuildFrom[B]
  // Type Mismatch in the line below
  def newBuilder[B] = new ListBuffer[B] mapResult (x => new MySeq(x.toSeq))
}

But I get the following type mismatch errors in the indicated lines:

inferred type arguments [B] do not conform to 
class MySeq's type parameter bounds [+B <: MyA] 
Main.scala  line 49

type mismatch;  
found   : countvotes.structures.MySeq.type  
required: scala.collection.generic.GenericCompanion[Seq]    
Main.scala  line 36

type mismatch;  
found   : MySeq[B(in class MySeq)]  
required: MySeq[B(in method newBuilder)]    
Main.scala  line 49

type mismatch;  
found   : scala.collection.immutable.Seq[B(in method newBuilder)]  
required: Seq[B(in class MySeq)]    
Main.scala  line 49

I have tried to solve this problem by adding bounds to the type parameters of CanBuildFrom and newBuilder, but then I get other error messages.

How can I create a custom Seq with a type parameter bound?

Answer 1

I'm not getting the error on line 26:

override def companion = MySeq

Maybe something else is causing that.

Anyway, the issue is that you cannot have a GenericCompanion[MySeq] (a supertype of SeqFactory). The reason is that GenericCompanion[Coll] means that you can construct a Coll[A] for any A (see signature of newBuilder). You also cannot have MySeq[A] <: GenericTraversableTemplate[A, MySeq], because genericBuilder is impossible. This makes sense; MySeq isn't really a "generic collection" because it wants its elements to all be MyA.

The solution is to have MySeq[B] <: GenericTraversableTemplate[B, Seq], (which comes free with extends Seq). You then have two choices for companion. It can just be the default one from Seq, or it can be s.companion. In the first case, ((as: MySeq[A]): Seq[A]).map(...) will produce a List (at runtime; at compiletime it's just a generic Seq). In the second, it will depend on what as.s is (again, at runtime; compiletime will only see a Seq). You can keep the extends SetLike, though.

Then, you need to provide a custom CanBuildFrom: MySeq.canBuildFrom[A <: MyA]: CanBuildFrom[MySeq[A], A, MySeq[A]], and define MySeq#newBuilder.

class MySeq[+B <: MyA](val s: Seq[B]) 
  extends Seq[B]
  with SeqLike[B, MySeq[B]]
{
  override def iterator = s.iterator
  override def apply(i: Int) = s(i)
  override def length = s.length

  override def toString = s.map(_.toString).mkString("\n")

  override def companion = s.companion
  protected[this] override def newBuilder: mutable.Builder[B, MySeq[B]] = new mutable.Builder[B, MySeq[B]] {
    private[this] val base = s.genericBuilder[B]
    override def +=(elem: B) = { base += elem; this }
    override def clear() = base.clear()
    override def result() = new MySeq[B](base.result())
  }
}

object MySeq {
  implicit def canBuildFrom[A <: MyA]: CanBuildFrom[MySeq[_], A, MySeq[A]] = ???
}

val list = List(new MyA, new MyA, new MyA, new MyA)
val vect = list.toVector
val mLst = new MySeq(list)
val mVec = new MySeq(vect)
{
  val res = mLst.filter(_.hashCode != list.head.hashCode)
  implicitly[res.type <:< MySeq[MyA]]
}
{
  val res = (mVec: Seq[MyA]).map(identity)
  assert(res.isInstanceOf[Vector[_]])
}
{
  val res = (mLst: Seq[MyA]).map(identity)
  assert(res.isInstanceOf[List[_]])
}

Answer 2

Here is a full MWE based on HTNW's accepted answer above, with canBuildFrom implemented:

class MyA

class MySeq[+A <: MyA](val s: Seq[A]) 
  extends Seq[A]
  with SeqLike[A, MySeq[A]]
{
  override def iterator = s.iterator
  override def apply(i: Int) = s(i)
  override def length = s.length

  override def toString = s.map(_.toString).mkString("\n")

  override def companion = s.companion
  protected[this] override def newBuilder = MySeq.newBuilder
}

object MySeq {
  def newBuilder[A <: MyA] = new mutable.Builder[A, MySeq[A]] {
    private[this] val base = Seq.newBuilder[A]
    override def +=(elem: A) = { base += elem; this }
    override def clear() = base.clear()
    override def result() = new MySeq[A](base.result())
  }

  implicit def canBuildFrom[A <: MyA]: CanBuildFrom[MySeq[_], A, MySeq[A]] = new CanBuildFrom[MySeq[_], A, MySeq[A]] {
    def apply(from: Election[_]) = newBuilder
    def apply() = newBuilder
  }
}