Extending SeqLike - move an element to the front of the sequence

I wrote a method called bringToFront, which moves an element a to the first position of a sequence seq if it exists; otherwise, seq is returned.
If a appears in the sequence more than once, only the first occurrence is moved.

Sample input/output:

List(1, 2, 3, 4, 3).bringToFront(1)     // List(1, 2, 3, 4, 3)
List(1, 2, 3, 4, 3).bringToFront(2)     // List(2, 1, 3, 4, 3)
List(1, 2, 3, 4, 3).bringToFront(3)     // List(3, 1, 2, 4, 3)
List(1, 2, 3, 4, 3).bringToFront(4)     // List(4, 1, 2, 3, 3)
List(1, 2, 3, 4, 3).bringToFront(5)     // List(1, 2, 3, 4, 3)

I could have easily defined these as extensions on List[A] or Seq[A], but I wanted to try and define them for the most abstract type possible, SeqLike[A, Repr]. For this, a CanBuildFrom is needed (I think).

Code:

implicit class SeqLikeOps[A, Repr  a +: seq.removeFirst(a)
      case _ => seq.repr
    }
  }

  def removeFirst(a: A)(implicit cbf: CanBuildFrom[Repr, A, Repr]): Repr = {
    val b = cbf()

    @tailrec
    def go(xs: SeqLike[A, Repr]): Unit = xs match {
      case h +: t if h == a => b ++= t
      case h +: t => b += h; go(t)
      case _ => ()
    }

    go(seq)
    b.result()
  }
}

My concerns:

• Is this the correct way of extending types like SeqLike or TraversableLike in general?

• In SeqLike[A, Repr], A and Repr are covariant. In SeqLikeOps[A, Repr], they're not, because they appear in a contravariant position in the signatures of bringToFront and remoteFirst. Is there any downside to this? Could they, somehow, be made covariant?

• Do I need the upper bound `

• Are the names I chose for these methods good? Suggestions are welcome.

• Is there a more efficient (in regards to memory and/or time complexity) and/or idiomatic way of implementing this?

Feel free to point out anything else I might have done wrong.

You might be overcomplicating a bit by reaching further than you need into builder mechanics. If you rewrite the signature of SeqLikeOps to

import scala.language.higherKinds
implicit class SeqLikeOps[A, F[_]](seq: SeqLike[A, F[A]])
  (implicit cbf: CanBuildFrom[F[A], A, F[A]]) {

then bringToFront can basically look like this:

def bringToFront(a: A): F[A] = {
  val as = // Do some magic with seq
  as.to[F]
}

Using higher kinds makes the upper bound go away while leaving the messy details of building to .to[F]
Here's one way to do that using Iterators for efficient space usage and gc and for their laziness.

implicit class SeqLikeOps[A, F[_]](seq: SeqLike[A, F[A]])(implicit cbf: CanBuildFrom[F[A], A, F[A]]) {
  private sealed trait Step {
    def iter: Iterator[A]
    def run(x: A): Step
  }
  private case class Found(iter: Iterator[A]) extends Step {
    def run(x: A) = Found(iter ++ Iterator(x))
  } 
  private case class NotFound(iter: Iterator[A], val a: A) extends Step {
    def run(x: A) = 
      if (x == a) 
        Found(Iterator(x) ++ iter)
      else
        NotFound(iter ++ Iterator(x), a)
  }
  def bringToFront(a: A): F[A] = {
    val result = seq.iterator.foldLeft(NotFound(Iterator[A](), a): Step) {
      (s, a) => s.run(a)
    } 
    result.iter.to[F]
  }

}

Using Iterator this way does grow the heap in proportion to the size of seq, because of the lazy ++. There are other ways to do this, still using the continuation-passing-style of Found/NotFound, which don't even do that. If such a solution isn't clear to you, I can provide one on request.

That aside, using an Iterator to build the final collection is a win.

As to variance, I can see no use for it in SeqLikeOps. Your aim here is to be returning the same collection type wherever possible and the same A always. Any subtype of F[A] is going to be seqLike and you return F, so variance has no purpose.

Sticking with the direct use of the builder (which may give the best performance), you might want to consider indexOf rather than find. Then if it returns -1 or 0, you just return the original. Otherwise you can build b using a, seq.take(index) and seq.drop(index + 1) with no recursion or other tricks needed. Oh, and you forgot sizeHint...

def bTF(a: A)(implicit cbf: CanBuildFrom[F[A], A, F[A]]): F[A] = {
  seq.indexOf(a) match {
    case i if i > 1 => {
      val b = cbf()
      b.sizeHint(seq)
      b += a
      b ++= seq take i
      b ++= seq drop (i + 1)
      b.result
    }
    case _ => seq.repr
  }
}

Of course, what we both really want is a way to minimise traversal. Scala just doesn't make that as easy as I'd like. But indexOf does mean only 1 traversal, with no new build, both if the value isn't found or if it is already at the front. It also means equality tests are only done on one traversal, not two.

After a little more thought, I came up with a variant of the above solution which really only iterates just once. But it may not be future-proof.

def bTFi(a: A)(implicit cbf: CanBuildFrom[F[A], A, F[A]]): F[A] = {
  val iter = seq.iterator
  val pred = iter.takeWhile(_ != a)
  val b = cbf()
  b.sizeHint(seq)
  b += a
  b ++= pred
  if (iter.isEmpty)
    seq.repr
  else {
    b ++= iter
    b.result
  }
}

Using the iterator this way means only one traversal of the collection. It works because, when forced by the assignment to the builder, takeWhile(_ != A) has to examine the first element which does equal a. And any Iterator operation which fetches the next element discards it after use. So this does work with the absolute minimum of traversal and good economy of space.

I just have a feeling this may rely on an implementation detail that might change. I will ask around.

EDIT:

Using anything other than next and hasNext on an iterator is considered not safe as the state of the iterator after any other operation is considered an implementation detail. But hey, here's an even simpler version:

def bTFi2(a: A)(implicit cbf: CanBuildFrom[F[A], A, F[A]]): F[A] = {
  val iter = seq.iterator
  val pred = iter.takeWhile(_ != a)
  (Iterator(a) ++ pred ++ iter).to[F]
}

which does feel a bit dirty.

StackExchange Code Review Q#106135, answer score: 2