Scala - cycling over a finite sequence starting from a given element

Question

I need to efficiently cycle over a fixed sequence, starting from any one of its elements, not always from the beginning.
The solution I have been exploring is:

val directions = List("north", "east", "south", "west")
val cycle = Stream.continually(directions).flatten

cycle dropWhile (_ != "south") take 12 foreach println

Since I'm using this inside a hot loop, starting over and over again, and the actual sequence is pretty lengthy, I fear the dropWhile is going to cost me quite a bit.
Is there a way I can speed this up?
Am I ever doing it the right way?

Edit

Some good answers were given suggesting I should not use Streams. The central question now becomes: how can I avoid using dropWhile or similar functions?

Answer 1

The example below indexes the values of the fixed sequence to avoid traversing the list each time a new stream is started.

package rando

object Faster extends App {
  val directions = Vector("north", "east", "south", "west")
  val index = directions.zipWithIndex.map { case (d, i) => d -> i }.toMap
  def streamWithStart(start: String): Stream[String] =
    directions.drop(index(start)).toStream.append(Stream.continually(directions).flatten)
  streamWithStart("east") take 10 reduce(_+" "+_) foreach print; println()
  streamWithStart("north") take 10 reduce(_+" "+_) foreach print; println()
  streamWithStart("west") take 10 reduce(_+" "+_) foreach print; println()
  streamWithStart("south") take 10 reduce(_+" "+_) foreach print; println()
}

Answer 2

Here is an implicit class that allows you to call a .looped method on any Traversable. I believe you'll find the Iterator it returns much more efficient than the result of flattening Stream.continually.

import scala.reflect.ClassTag

/** Turns a Traversable into an infinite loop. */
implicit class TraversableLooper[A:ClassTag]( val items:Traversable[A] ) {
  def looped:Iterator[A] =
    if ( items.isEmpty )
      sys error "<empty>.looped"
    else
      new Iterator[A] {
      val array = items.toArray
      val numItems = array.length
      var i = -1
      def hasNext = true
      def next = {
        i += 1
        if ( i == numItems ) i = 0
        array(i)
      }
    }
}

Here it is in use:

scala> val directions = List("north", "east", "south", "west")
directions: List[String] = List(north, east, south, west)

scala> directions.looped dropWhile (_ != "south") take 12 foreach println
south
west
north
east
south
west
north
east
south
west
north
east

Also, do as much as possible before making the loop, e.g. the dropWhile:

( directions.looped dropWhile (_ != "south") take 4 ).toSeq.looped

Answer 3

You should use Iterator rather than Stream. Stream keep everything in memory, and become bigger and bigger.

scala> val directions = List("north", "east", "south", "west")
directions: List[String] = List(north, east, south, west)

scala> val cycle = Iterator.continually(directions).flatten
cycle: Iterator[String] = non-empty iterator

scala> cycle dropWhile (_ != "south") take 2 foreach println
south
west

scala> cycle dropWhile (_ != "east") take 2 foreach println
east
south

Answer 4

Yet another approach, where directions key value south is shifted up to the head of the list, then we iterate for instance 4 times over the shifted list,

implicit class AddCycleToList[A](val list: List[A]) extends AnyVal {

  def cycle(times: Int, from: A): Unit = {
    val shiftBy = list span { _ != from }
    val shifted = shiftBy._2 ++ shiftBy._1
    for (i <- 1 to times) shifted foreach println
  }
}

Hence

scala> val directions = List("north", "east", "south", "west")
directions: List[String] = List(north, east, south, west)

scala> directions.cycle(4, "south")
south
west
north
east
south
west
north
east
south
west
north
east
south
west
north
east

Answer 5

To avoid recalculating as much as possible:

val cycle = Stream.continually(directions).flatten
val cachedStreams = collections.mutable.Map.empty[String, Stream[String]]

def cycleStartingWith(direction: String) = 
  cachedStreams.getOrElseUpdate(direction, cycle.dropWhile(_ != direction))

This won't work with Iterators, however; in that case, I'd go with a variation on Dave Rando's answer.