스칼라에서 구현 한 부분 합계를 수정하는 방법은 무엇입니까?

Question

이것은 내 previous question의 후속 조치입니다. I는

, 나는 다음과 같이 s1, s1 + s2, s1 + s2 + s3, ...

내가 그것을 구현하는 새로운 스트림을 스트림 s = 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]을 코딩하고 싶습니다. 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)