时间戳

首页 > 解决方案 > Scala：使用迭代器的动态编程递归

scala - Scala：使用迭代器的动态编程递归

问题描述

学习如何在 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数组或执行 a .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()，它会更改传递给函数的所有其他递归调用的 iter 实例。所以为了解决这个问题，现在我在每次调用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情况下可能需要或可能不需要克隆时，愚蠢会升级。处理这种情况的正确方法是什么？我怎样才能优雅地解决这些问题？

标签： scalarecursionfunctional-programmingdynamic-programmingbacktracking

解决方案

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

  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))
  }
}

如果您要使用 aList而不是 a 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.

这里没有回溯，但是如果递归方法会回溯，使用列表会带来另一个好处：提取子列表几乎是免费的（恒定时间操作），但它仍然保证是不可变的，因此您可以将其传递给递归调用，而不必关心递归调用是否修改它，因此您不必做任何事情来撤消递归调用可能完成的任何修改。这是持久不可变数据结构的优势：相关列表可以共享它们的大部分结构，同时从外部看起来仍然是不可变的，因此不可能仅仅因为您可以访问该列表的尾部而破坏父列表中的任何内容. 对于可变数组的视图，情况并非如此。

推荐阅读