How to traverse array from both left to right and from right to left?

Question

Suppose I have an imperative algorithm that keeps two indices left and right and moves them from left to right and from right to left

var left  = 0
var right = array.length - 1
while (left < right) { .... } // move left and right inside the loop

Now I would like to write this algorithm without mutable indices. How can I do that ? Do you have any examples of such algorithms ? I would prefer a non-recursive approach.

Answer 1

You can map pairs of elements between your list and its reverse, then go from left to right through that list of pairs and keep taking as long as your condition is satisfied:

val list = List(1, 2, 3, 4, 5)
val zipped = list zip list.reverse
val filtered = zipped takeWhile { case (a, b) => (a < b) }

Value of filtered is List((1, 5), (2, 4)). Now you can do whatever you need with those elements:

val result = filtered map {
  case (a, b) => 
    // do something with each left-right pair, e.g. sum them
    a + b
}

println(result) // List(6, 6)

If you need some kind of context dependant operation (that is, each iteration depends on the result of the previous one) then you have to use a more powerful abstraction (monad), but let's not go there if this is enough for you. Even better would be to simply use recursion, as pointed out by others, but you said that's not an option.

EDIT:

Version without extra pass for reversing, only constant-time access for elem(length - index):

val list = List(1, 2, 3, 4, 5)
val zipped = list.view.zipWithIndex
val filtered = zipped takeWhile { case (a, index) => (a < list(list.length - 1 - index)) }

println(filtered.toList)  // List((1, 0), (2, 1))

val result = filtered map {
  case (elem, index) => // do something with each left-right pair, e.g. sum them
    val (a, b) = (elem, list(list.length - 1 - index))
    a + b
}

println(result.toList) // List(6, 6)

Answer 2

Use reverseIterator:

scala> val arr = Array(1,2,3,4,5)
arr: Array[Int] = Array(1, 2, 3, 4, 5)

scala> arr.iterator.zip(arr.reverseIterator).foreach(println)
(1,5)
(2,4)
(3,3)
(4,2)
(5,1)

This function is efficient on IndexedSeq collections, which Array is implicitly convertible to.