Scalaの部分和の実装を修正するにはどうすればよいですか？

Question

これは私のprevious questionのフォローアップです。私は次のように私はそれを実装ストリームs = s1, s2, s3, ...を受信して​​、新しいストリームs1, s1 + s2, s1 + s2 + s3, ...

を作り出す機能partial_sumsを、書きたい、すなわち（単なる練習として）自分で

をs.scanLeft(0)(_ + _)を実装したいと思います：

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)) 

このコードは正常に動作します。しかし、partial_sumsのn番目の要素を得るにはO（n）が必要です。 （すなわち、s [1] + s [2] + s [3] ... + s [n]）。 partial_sums[n] = partial_sums[n-1] + s[n]をコードしたいと思います。これは、n番目の要素を計算するためにO（1）が必要です。

正しいですか？どのようにコードを修正しますか？ストリーム[INT] `I /` sのO：STRING`

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)