Scala Stream function evaluation -

i got following code:

trait stream[+a] {   def uncons: option[(a, stream[a])]   def foldright[b](z: => b)(f: (a, => b) => b): b = {     uncons.map(t => {       f(t._1, t._2.foldright(z)(f))     }).getorelse(z)   }   def exists(p: => boolean) =     foldright(false)((x, acc) => acc || p(x))   def forall(p: => boolean) =     foldright(true)((x, acc) => p(x) && acc) }  object stream {   def cons[a](h: => a, t: => stream[a]): stream[a] =     new stream[a] {       lazy val uncons = some((h, t))     } } 

then create stream in lazy manner , invoke exists method check stream elements evaluated:

  println(stream.cons({println("5"); 1}, stream.cons({println("6"); 2}, stream.cons({println("7"); 3}, stream.cons({println("8"); 4}, stream.empty)))).exists(_ == 1)) 

and see is:

5 6 7 8 true 

so elements evaluated in spite of first 1 enough. seem understand why exists acts way does.

then run following code:

println(stream.cons({println("13"); 1}, stream.cons({println("14"); 2}, stream.cons({println("15"); 3}, stream.cons({println("16"); 4}, stream.empty)))).forall(_ < 2)) 

and see following:

13 14 false 

so far forall comes across non-satisfying value terminates traversal.

but why forall acts way? what's crucial difference between , exists?

there 2 things consider :

• the type of acc
• the order of p(x) in boolean expression.

laziness

if change type of acc b, won't able fail-fast (or short-circuit) in either of methods. must know since code extensively uses laziness, variable of type => b evaluated when value required i.e. used in expression. in case, acc future of result computed on stream. future happen if try looking @ it. thus, prevent whole stream evaluated, must prevent future looked at.

short-circuiting in boolean expressions

this order of p(x) matters. in expression a && b, if a false know whole conjunction false, scala won't try evaluating b because it's pointless.

combining two

now happens if 1 of operands lazy expression ? well, if have lazya || b, scala read expression left right , evaluate lazya. in case, lazya represents accumulation of next element , rest of stream. thus, lazya expands a0 :: lazya1, expands a0 :: a1 :: lazya2. therefore end computing whole stream computing left part of boolean binop.

now, if have a && lazyb, expands a && (b0 :: b1 :: lazyb2). see here, a or bi false, return without evaluating right part of statement. happens in forall.

how fix it

the news fix easy : swap order of p(x) , acc : p(x) true, disjunction return without evaluating acc, stopping computation.

def exists(p: => boolean) = foldright(false)((x, acc) => p(x) || acc) 

output :

5 true