这是我
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)
