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

Question

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 <: SeqLike[A, Repr]](seq: SeqLike[A, Repr]) { 
 def bringToFront(a: A)(implicit cbf: CanBuildFrom[Repr, A, Repr]): Repr = {
 seq.find(_ == a) match {
 case Some(_) => 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 <: SeqLike[A, Repr]?
• 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.

• itsbruce: Since you're already using CanBuildFrom to recreate the original type, I'd say this is a very good case for using an Iterator for the intermediate step. That allows you to use HoFs like takeWhile while only traversing the sequence once. In fact, this could be implemented with two takeWhiles and one concatenation, with the bonus of laziness. Using Iterator gives you efficiency while still allowing expressive, idiomatic combinator functions.

Answer 1

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.

• dcastro: Thanks for the answer. Great tip on using higher kinds + to[F] instead of a builder. However, it seems like I do need the upper bound in order to use the +: operator in bringToFront.I'm not quite sure how to do this with a higher kinded type - if I add F[_] <: SeqLike[A, F[_]] then new SeqLikeOps(List(1)) won't compile - if I add F[A] <: SeqLike[A, F[A]] then IntelliJ complains about a "Suspicious shadowing by a Type Parameter: A" in the first occurrence of F[A].
• itsbruce: The solution is implicit evidence. (implicit ev: F[A] <:< SeqLike[A, F[A]]). In my example, I put thecanBuildFrom implicit on the class constructor but if you generally want to use SeqLike operators on F[A], put the implicit evidence on the constructor and the canBuildFrom on whichever methods need it.
• itsbruce: No worries. Added a couple of notes relevant to your other questions and your original implementation.
• itsbruce: Oh, and dude: sizeHint ;)
• itsbruce: @dcastro Came up with a single-traversal iterator solution. I promise that's my last fiddle on this question.