Chap 5 scanRight solution appears to calculate partial values multiple times

[jeremystone]

With the given solution for scanRight (for exercise 5.16, p77):

Stream(1, 2, 3).scanRight(0) { (a, b) => val x = a + b; print(s"$x "); x }.toList
//> 3 5 6 3 5 3 res55: List[Int] = List(6, 5, 3, 0)

(Looks quadratic to me. Same thing for Stream(1,2,3,4,5) has 15 partial sums calculated with this implementation.)

An alternative that does not touch the by-name accumulator, p, twice per fold, namely:
def scanRight2[B](z: B)(f: (A, => B) => B): Stream[B] =
foldRight((z, Stream(z)))((a, p) => {
val (p1, p2) = p
val b2 = f(a, p1)
(b2, cons(b2, p2))
})._2

results in:
Stream(1, 2, 3).scanRight2(0) { (a, b) => val x = a + b; print(s"$x "); x }.toList
//> 3 5 6 res55: List[Int] = List(6, 5, 3, 0)

[pchiusano]

I would actually just store the results in a lazy val. You don't want to strictly evaluate p I don't think. So something like:

(a,p0) => { lazy val p = p0; /* as before */ }

PR welcome! Also, is the numbering off on this exercise? The answer key has this as exercise 17.

[jeremystone]

Yes - lazy val even better.

Looks like implementing hasSubsequence used to be exercise 5.16. This implementation is now provided in the book with scanRight taking its number.

[pchiusano]

Fixed via your PR