Scala:使用迭代器的动态编程递归

Question

学习如何在 Scala 中进行动态编程，我经常发现自己想要递归地处理一个数组(或其他一些可迭代的项目(。当我这样做时，我倾向于编写像这样的繁琐函数：

def arraySum(array: Array[Int], index: Int, accumulator: Int): Int => {
if (index == array.length) {
accumulator
} else {
arraySum(array, index + 1, accumulator + array(index)
}
}
arraySum(Array(1,2,3), 0, 0)

(暂时忽略我可以在数组上调用sum或执行.reduce(_ + _)，我正在尝试学习编程原理。

但这似乎我传递了很多变量，将数组传递给每个函数调用到底有什么意义？这似乎不干净。

因此，我有了使用迭代器执行此操作的想法，而不必担心传递索引：

def arraySum(iter: Iterator[Int])(implicit accumulator: Int = 0): Int = {
try {
val nextInt = iter.next()
arraySum(iter)(accumulator + nextInt)
} catch {
case nee: NoSuchElementException => accumulator
}
}
arraySum(Array(1,2,3).toIterator)

这似乎是一个更干净的解决方案。但是，当您需要使用动态规划来探索某些结果空间并且不需要在每次函数调用时调用迭代器时，这种情况就会崩溃。例如

def explore(iter: Iterator[Int])(implicit accumulator: Int = 0): Int = {
if (someCase) {
explore(iter)(accumulator)
} else if (someOtherCase){
val nextInt = iter.next()
explore(iter)(accumulator + nextInt)
} else {
// Some kind of aggregation/selection of explore results
}
}

我的理解是，这里的iter迭代器充当引用传递，因此当此函数调用时，iter.next()会更改传递给该函数的所有其他递归调用的迭代器实例。因此，为了解决这个问题，现在我在每次调用explore函数时克隆迭代器。例如：

def explore(iter: Iterator[Int])(implicit accumulator: Int = 0): Int = {
if (someCase) {
explore(iter)(accumulator)
} else if (someOtherCase){
val iterClone = iter.toList.toIterator
explore(iterClone)(accumulator + iterClone.next())
} else {
// Some kind of aggregation/selection of explore results
}
}

但这似乎很愚蠢，当我有多个迭代器时，愚蠢就会升级，这些迭代器在多个else if情况下可能需要也可能不需要克隆。处理这种情况的正确方法是什么？我怎样才能优雅地解决这类问题？

Answer 1

假设您要编写一个需要一些复杂数据结构作为参数的回溯递归函数，以便递归调用接收数据结构的略微修改版本。您有几种选择：

1. 克隆整个数据结构，修改它，将其传递给递归调用。这很简单，但通常非常昂贵。
2. 就地修改可变结构，将其传递给递归调用，然后在回溯时还原修改。您必须确保递归函数的每个可能调用始终准确地恢复数据结构的原始状态。这效率要高得多，但很难实现，因为它可能非常容易出错。
3. 将结构细分为大的不可变部分和小的可变部分。例如，您可以传递一个显式指定数组某个切片的索引(或一对索引(，以及一个永不变异的数组。然后，您可以"克隆"并仅保存可变部分，并在回溯时恢复它。如果它有效，它既简单又快速，但它并不总是有效，因为子结构可能很难用几个整数索引来描述。
4. 尽可能依赖持久的不可变数据结构。

我想详细说明最后一点，因为这是在 Scala 和一般函数式编程中的首选方法。

这是您的原始代码，它使用第三种策略：

def arraySum(array: Array[Int], index: Int, accumulator: Int): Int = {
if (index == array.length) {
accumulator
} else {
arraySum(array, index + 1, accumulator + array(index))
}
}

如果你使用List而不是Array，你可以把它重写成这样：

@annotation.tailrec
def listSum(list: List[Int], acc: Int): Int = list match {
case Nil => acc
case h :: t => listSum(t, acc + h)
}

在这里，h :: t是一种将列表解构为head和tail的模式。 请注意，您不再需要显式索引，因为访问列表的尾t是一个常量时间操作，因此只有相关的剩余子列表传递给listSum的递归调用。

这里没有回溯，但如果递归方法会回溯，使用列表会带来另一个优势：提取子列表几乎是免费的(常量时间操作(，但它仍然保证是不可变的，所以你可以把它传递到递归调用中，而不必关心递归调用是否修改它， 因此，您无需执行任何操作即可撤消递归调用可能完成的任何修改。这是持久不可变数据结构的优点：相关列表可以共享其大部分结构，同时从外部看起来仍然不可变，因此不可能仅仅因为您可以访问此列表的尾部而破坏父列表中的任何内容。对于可变数组的视图，

情况并非如此。