这是我的 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 个元素。
这是正确的吗？你会如何修复代码？
最佳答案
基本思想是保持运行总数，而不是批量添加流
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)
关于scala - 如何修复我在 Scala 中部分求和的实现？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8656851/