Vishnu (3) [Avatar] Offline
#1
Hi, I am wondering if the solution in the book is correct for 5.4


  // 5.4
  def forAll (f:A => Boolean) : Boolean = foldRight (true) ( (a,b) => f(a) && b )
  


This code will always return true for a

Stream[Boolean] = Empty


And what you actually want is that if the string is empty, it should return false.. just wondering.

The problem with the current implementation, is that if i try example 5.14 (hasSubsequence), with the following it will return true.

      Stream(1,2,3,4,5,6,7,8).hasSubsequence(Stream(10,11,12)) must_=== false

runar (53) [Avatar] Offline
#2
Hi Vishnu,

`forAll(f)` should always return `true` for the empty stream, no matter what `f` is. Think about it this way:

What would you expect the following to return?

!s.forAll(f)


I'd expect that negation to be true precisely when there are some elements in `s` that don't match `f`. I would expect "not all the elements match" and "some of the elements don't match" to be the same. That is, if we were to assert "there are no elements in the stream not matching f" (obviously true for the empty stream), that should be the same thing as saying "all elements in the stream match f".

If that's not convincing, think about it another way:

Given two streams `s1` and `s2`, if we say
s1.forAll(f) && s2.forAll(f)
that should be the same as saying
(s1 ++ s2).forAll(f)
That is, if all elements in either stream match, then all elements in the combined stream should also match. If you decide that forAll returns false for the empty stream, that property no longer holds.

I haven't seen your implementation of hasSubsequence, but the one given in the answers uses exists rather than forAll. We could rewrite it using forAll by using a double negation:

def hasSubsequence[A](s: Stream[A]): Boolean =
    !(tails forAll (a => !(a startsWith s)))