如何在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],它采用O(1)来计算第n个元素.

这是对的吗？你会如何修复代码？

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)