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(), это изменяет экземпляр 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 случаях.Как правильно обращаться с подобными ситуациями?Как я могу элегантно решить такие проблемы?

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.

Здесь нет возврата назад, но если рекурсивный метод будет возвращаться назад, использование списков принесло бы еще одно преимущество: извлечение подсписка почти бесплатно (операция с постоянным временем), но оно все равно гарантировано неизменным, поэтому вы можете просто передатьэто в рекурсивный вызов, без необходимости заботиться о том, изменяет ли рекурсивный вызов его или нет, и поэтому вам не нужно ничего делать, чтобы отменить любые изменения, которые могли бы быть сделаны рекурсивными вызовами.В этом преимущество постоянных неизменяемых структур данных: связанные списки могут совместно использовать большую часть своей структуры, но при этом они выглядят неизменяемыми извне, поэтому невозможно сломать что-либо в родительском списке только потому, что у вас есть доступ к хвосту этого списка,Это не относится к виду изменяемого массива.