scala - 如何修复我在 Scala 中部分求和的实现？

Question

这是我的 previous 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) 才能获得 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)