Как исправить мою реализацию частичных сумм в Scala?

Question

Это продолжение моего предыдущего вопроса . Я хотел бы реализовать s.scanLeft(0)(_ + _) самостоятельно (просто как упражнение)

То есть я хотел бы написать функцию partial_sums, которая получает поток s = s1, s2, s3, ... и создает новый поток s1, s1 + s2, s1 + s2 + s3, ...

Я реализую это следующим образом:

def add_streams(s1:Stream[Int], s2:Stream[Int]) =
  (s1 zip s2) map {case (x, y) => x + y}

def partial_sums(s:Stream[Int]):Stream[Int] =
  Stream.cons(s.head, add_streams(partial_sums(s), s.tail))

Этот код работает нормально. Однако, похоже, что требуется O (n), чтобы получить n-й элемент partial_sums. (то есть s [1] + s [2] + s [3] ... + s [n]). Я хотел бы кодировать partial_sums[n] = partial_sums[n-1] + s[n], для вычисления n-го элемента требуется O (1).

Это правильно? Как бы вы исправили код?

Answer 1

Основная идея состоит в том, чтобы сохранить промежуточный итог, а не добавлять потоки оптом

def partialSums(s:Stream[Int]) = if(s.isEmpty) new Stream[Int]() else partialSums(s, 0)

def partialSums(s:Stream[Int], runningTotal:Int)= Stream.cons(s.head+runningTotal, partialSums(s.tail, s.head+runningTotal)