scala - 如何从左到右和从右到左遍历数组？

Question

假设我有一个命令式算法，它保留两个索引 left和 right并从左到右和从右到左移动它们

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

现在我想编写这个没有可变索引的算法。
我怎样才能做到这一点 ？你有这种算法的例子吗？我更喜欢非递归方法。

Answer 1

您可以在列表及其反向之间映射元素对，然后从左到右遍历该对列表，并在满足条件时继续使用:

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

filtered 的值是 List((1, 5), (2, 4)) .
现在你可以对这些元素做任何你需要的事情:

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)

如果您需要某种上下文相关的操作(即每个
迭代取决于前一个的结果)那么你必须
使用更强大的抽象(monad)，但如果
这对你来说已经足够了。更好的是简单地使用递归，正如其他人所指出的那样，但你说这不是一个选择。

编辑:

版本没有额外的倒车传递，只有对 elem(长度 - 索引)的恒定时间访问:

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)