Exercise 5.16 Solution

[ntto...@gmail.com]

Hi,

Can anyone show me a solution to exercise 5.16?

"Hard: Generalize tails to the function scanRight, which is like a foldRight that
returns a stream of the intermediate results. For example:"

So far the best I can do is:

def scanRight[B](s: B)(f: (A, => B) => B): Stream[B] = {
tails.map { stream =>
stream.foldRight(s) { (ni, ns) =>
f(ni, ns)
}
}
}

But this solution does not append the initial state to the end of the stream

[phde...@gmail.com]

Companion Guide (http://blog.higher-order.com/assets/fpiscompanion.pdf) has a solution. I came up with something different; on simple test cases it works, but I am not entirely sure if it's correct (using same vars a, p0 as companion guide to ease comparisons):

def scanRight[B](z: => B)(f: (A, => B) => B): Stream[B] =
foldRight(Stream(z))((a, p0) => Stream(f(a,p0.head)).append(p0) )

calling head is generally unadvisable but I believe here it's ok because by the time foldRight makes the RHS of => for Stream evaluation kick in, p0 should contain an initial stream (Stream(z)) that is not empty.

I tested this code successfully on
scala> Stream[Int]().scanRight(0)(_ + _).toList
res2: List[Int] = List(0)
and
scala> Stream(2,4,6,8).scanRight(0)(_ + _).toList
res0: List[Int] = List(20, 18, 14, 8, 0)

[shay shimony]

Your solution looks correct to me, but it will repeat the recursive call of p0 twice, which could be avoided as they showed in the solution (p0 is by name parameter, so each reference to it will recalculate it - in this case - the recursion of foldRight).

I came up we something similar to yours, which is simpler than their solution:

def scanRight[B](z: => B)(f: (A, => B) => B): Stream[B] =

    foldRight(cons(z, empty))((a, b) => {
      val bval: Stream[B] = b
      bval match {
        case Cons(h, t) => cons(f(a, h()), bval)
      }

    })