如何在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_sum (s:Stream[Int]):Stream[Int] =Stream.cons (s。Head, add_streams(partial_sum (s)， s.tail)之前
这段代码工作正常。然而，它看起来需要O(n)来获得partial_sums的第n个元素。(即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)