Built-in method for rolling Scala List or Seq

Question

I'm trying to roll a list, for example like so:

val notRolled = (1 to 5).toList       // List(1,2,3,4,5)

val rolledBy1 = rollList(notRolled,1) // List(2,3,4,5,1)
val rolledBy2 = rollList(notRolled,2) // List(3,4,5,1,2)
val rolledBy3 = rollList(notRolled,3) // List(4,5,1,2,3)
val rolledBy4 = rollList(notRolled,4) // List(5,1,2,3,4)
val rolledBy5 = rollList(notRolled,5) // List(1,2,3,4,5)

val rolledByM1 = rollList(notRolled,-1) // List(5,1,2,3,4)
val rolledByM2 = rollList(notRolled,-2) // List(4,5,1,2,3)
val rolledByM3 = rollList(notRolled,-3) // List(3,4,5,1,2)
val rolledByM4 = rollList(notRolled,-4) // List(2,3,4,5,1)
val rolledByM5 = rollList(notRolled,-5) // List(1,2,3,4,5)

I had a look at scala-lang.org and can't seem to find anything that matches my requirement.

Is there a built-in method for rolling a list?

If not, is there a more efficient way to do it than this:

def rollList[T](theList: List[T], itemsToRoll: Int): List[T] = {
  val split = {
    if (itemsToRoll < 0) (theList.size + itemsToRoll % theList.size)
    else itemsToRoll % theList.size
  }
  val (beginning, end) = theList.splitAt(split)
  end ::: beginning
}

Answer 1

Using the enrich-my-library pattern will allow you to add the roll method directly to all the collections so that you can call myList.roll(2), as opposed to roll(myList, 1).

Using the generic CanBuildFrom pattern allows you to make roll return the best possible type on these collections (so that roll on a List will return a List, but roll on an Iterable will return an Iterable).

All together, here is one option that abides by these patterns:

import scala.collection.generic.CanBuildFrom
import scala.collection.TraversableLike

implicit class TraversableWithRoll[A, Repr <: Traversable[A]](val xs: TraversableLike[A, Repr]) extends AnyVal {
  def roll[That](by: Int)(implicit bf: CanBuildFrom[Repr, A, That]): That = {
    val builder = bf()
    val size = xs.size
    builder.sizeHint(xs)
    val leftBy = if (size == 0) 0 else ((by % size) + size) % size
    builder ++= xs.drop(leftBy)
    builder ++= xs.take(leftBy)
    builder.result
  }
}

This allows you to do some of the following:

List(1, 2, 3, 4, 5).roll(2) //List(4,5,1,2,3)
Seq(3, 4, 5).roll(-1) //Seq(5, 3, 4)

Notice the benefits of the fluent syntax enabled by the enrich-my-library pattern, and the stronger types enabled by the use of the CanBuildFrom implicit .

Answer 2

Here is one way of simulating a circular list in a functional way. I made it so that a positive i will do a right shift and a negative a left shift. This is the reverse of what the question has, but I felt it's more natural.

def shift[T](c: List[T], i: Int) = { 
   if(c.isEmpty) c
   else {
      val (h,t) = if (i >= 0) c.splitAt(c.size - i%c.size)
            else c.splitAt(- i%c.size) 
      t ++ h
   }
}

Here are some examples in the REPL:

cala> shift(List(1,2,4), 1)
res: List[Int] = List(4, 1, 2)

scala> shift(List(1,2,4), 2)
res: List[Int] = List(2, 4, 1)

scala> shift(List(1,2,4), 3)
res: List[Int] = List(1, 2, 4)

scala> shift(List(1,2,4), 4)
res: List[Int] = List(4, 1, 2)

scala> shift(List(1,2,4), 5)
res: List[Int] = List(2, 4, 1)

scala> shift(List(1,2,4), 6)
res: List[Int] = List(1, 2, 4)

scala> shift(List(1,2,4), -1)
res60: List[Int] = List(2, 4, 1)

scala> shift(List(1,2,4), -2)
res: List[Int] = List(4, 1, 2)

scala> shift(List(1,2,4), -3)
res: List[Int] = List(1, 2, 4)

scala> shift(List(1,2,4), -4)
res: List[Int] = List(2, 4, 1)

scala> shift(List(1,2,4), -5)
res: List[Int] = List(4, 1, 2)

scala> shift(List(1,2,4), -6)
res: List[Int] = List(1, 2, 4)

Answer 3

def rotate[A] (list: List[A], by: Int) = {
    if (list.isEmpty) list
    else {
        val shift = (by % list.size + list.size) % list.size
        val (l, r) = list.splitAt(shift)
        r ++ l
    }
}

val list = List(1, 2, 3, 4, 5)
rotate(list, 1) // List(2, 3, 4, 5, 1)
rotate(list, 2) // List(3, 4, 5, 1, 2)
rotate(list, -1) // List(5, 1, 2, 3, 4)
rotate(list, -2) // List(4, 5, 1, 2, 3)

rotate(list, -9) // List(2, 3, 4, 5, 1)

Answer 4

This is my pure functional very simple proposition:

def circ[A]( L: List[A], times: Int ): List[A] = {

    if ( times == 0 || L.size < 2 ) L
    else circ(L.drop(1) :+ L.head , times-1)
}

val G = List("1a","2b","3c")

println( circ(G,1) ) //List(2b, 3c, 1a)
println( circ(G,2) ) //List(3c, 1a, 2b)
println( circ(G,3) ) //List(1a, 2b, 3c)
println( circ(G,4) ) //List(2b, 3c, 1a)

Added for times < 0 (rolling backwards):

def circ[A]( L: List[A], times: Int ): List[A] = {
    if ( times == 0 || L.size < 2 ) L
    else if ( times < 0 ) circ(L.reverse,-times).reverse 
    else                  circ(L.drop(1) :+ L.head , times-1)
}

Answer 5

Given:

val notRolled = (1 to 5).toList 

Let's say we want rotate with shift = 3

val shift = 3

notRolled.zipWithIndex.groupBy(_._2 < shift).values.flatten.map(_._1)

For negative values we should add 5(lists size), so for shift = -3 we will calculate

val shift = -3
notRolled.zipWithIndex.groupBy(_._2 < 2).values.flatten.map(_._1)

Answer 6

I'm going to incorporate the ideas above, about CanBuildFrom, just as soon as I understand Scala better (!), but in the meantime, I had to do precisely this for the sake of writing a Burrows-Wheeler Transform algorithm. Here, with no take() or drop(), and no errors on empty collections (and, yes, side-effecting code):

def roll[A](xs: Traversable[A]): Iterator[Traversable[A]] = {
  var front = xs
  var back = collection.mutable.Buffer[A]()

  Iterator.continually(front ++ back).takeWhile { _ =>
    val done = front.isEmpty
    if (!done) {
      back :+= front.head
     front = front.tail
   }
   !done
  }
}