scheme stream problem partSums

this week I got new homework to do, I should write a function partSums, which could add the elements in the original stream to build new stream like:

(element0,element0+element1,element0+element1+element2...)

and the result should have a 0 at the beginning.

in this example I assumed we have a function called integers to produce a stream like in Haskell [1..],so use the partSums on it should look like this:

(partSums integers)
> '(1, 3, 6, 10,开发者_Go百科 15...)

in my understanding, it's like this:

  1 2 3  4  5  6 7 8..
    1 2  3  4  5 6 7..
      1  2  3  4 5 6..
         1  2  3 4 5..
            1  2 3 4..
               1 2 .
+                  .
  1 3 6 10 15 21 .....

to add 2 streams I have done:

(define (add-streams s1 s2)
    (cond ((empty-stream? s1) s2)
          ((empty-stream? s2) s1)
          (else (cons-stream
                (+ (head s1)(head s2))
                (add-streams (tail s1) (tail s2))))))

and I also have functions head, tail, cons-stream, they are car,cdr, cons for stream.

can anyone help me finish this partSums?

thanks in advance

bearzk

HtDP-bot says:

• Can you write down a purpose statement and contract for this function? What does it consume, and what does it produce?
• Can you translate your examples into test cases? Write an expression, and the value it should produce. Compare them using "equal?"

Your approach appears to be to create a bunch of shifted streams and add them up. This would conceivably work if you knew how many elements you want to take, but if the number of elements is indeterminate, you can't create an infinite number of these streams, of course!

Another approach would be to maintain a list of streams you're adding from at each point, call it current-streams, starting with (list integers). Then at each step you (cons integers current-streams), obtain the next partial sum with (apply + (map head current-streams)), and recurse with current-streams changing to (map tail current-streams). This way you only add series as you really need them, rather than trying to create an infinite number of streams up-front. But this is a resource-intensive approach, since the number of streams you need to track will just keep growing and growing.

It would be nice if you could sum up a fixed number of streams (ideally two, with the function you wrote!) to get the output you wanted. Note that at each step through the output, the previous step has most of the partial sum you need already calculated for you... if you can find some way of using streams to take advantage of that. Try writing down the recurrence relationship between successive elements of the partSums sequence, with the help of the integers sequence you've already defined, and see if that leads you to a possibly different streaming approach...

(define (partial-sums s)
  (let loop ((current 0) (s s))
    (if (empty-stream? s) '()
        (let ((v (+ current (head s))))
          (cons-stream v (loop v (tail s)))))))

this

(partial-sums '(1 2 3 4 5 6 7 8 9))

prints

(1 3 6 10 15 21 28 36 45)

after defining

(define empty-stream? null?)
(define tail cdr)
(define head car)
(define cons-stream cons)