How to fix my implementation of partial amounts in Scala?

Question

This is a continuation of my previous question . I would like to implement s.scanLeft(0)(_ + _) myself (as an exercise)

That is, I would like to write a partial_sums function that receives the stream s = s1, s2, s3, ... and creates a new stream s1, s1 + s2, s1 + s2 + s3, ...

I implement it as follows:

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

This code is working fine. However, it seems that O (n) is required to get the nth partial_sums element. (ie s [1] + s [2] + s [3] ... + s [n]). I would like to code partial_sums[n] = partial_sums[n-1] + s[n] , which takes O (1) to calculate the nth element.

Is it correct? How do you fix the code?

Answer 1

The main idea is to keep the current total, and not add streams to the mass

 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)