What is the exact difference in behavior between `++` and `#:::` when you concatenate two streams?

Question

To be more specific, I had a code similar to the following one (some of you will probably recognize the pattern of the last assignment of the coursera Functional Programming Course), that failed to find the solution with ++ but worked with #::: (the set of alreadySeen solution contained a node that had not been explored and prevented the solver from reaching the goal position). I have disguised the code to respect the agreement and in the short sample here ++ leads to a StackOverflowError whereas #::: yields the good solution. The scala doc for ++ warns about potential inifinite realization when used with other collection but in my example it is used between two streams.

case class PuzzleNode(pos: Position, moves: List[Move])

def reachableNodes(node: PuzzleNode): Stream[PuzzleNode] = ...

def from(initial: Stream[PuzzleNode], alreadySeen: Set[Position]): Stream[PuzzleNode] = {
  if (initial.isEmpty) Stream.empty
  else {
    val next = for {
      startNode <- initial
      node <- reachableNodes(startNode)
      if(!alreadySeen.contains(node.pos))
    } yield node

    //initial #::: from(next, alreadySeen ++ next.map(_.pos))
    initial ++ from(next, alreadySeen ++ next.map(_.pos))
  }
}

EDIT: ++ exhibits a lazy behavior for the following code, that I can understand given the ++ implementation in the stream class which uses cons to build the resulting stream.

val fibs: Stream[BigInt] = BigInt(0) #:: BigInt(1) #:: fibs.zip(fibs.tail).map { n => n._1 + n._2 }
val prefix: Stream[BigInt]  = BigInt(4) #:: BigInt(8) #:: Stream.Empty
(prefix ++ fibs) take 10 foreach println

Why is the behavior different in the from function above ?

Answer 1

++ evaluates its parameter immediately ( call by value), forcing the evaluation of the recursive call to from, which causes the StackOverflow. #::: evaluates the parameter lazily ( call by name), so the from recursive call will just happen as the stream is forced.

To your edit ++ is not exhibting lazy behaviour, you're calling it with a already defined Stream fibs, which evaluates only the head. The fact that it doesn't overflow is because the tail is lazily evaluated.

To see the difference try the following:

 val prefix: Stream[BigInt]  = BigInt(4) #:: BigInt(8) #:: Stream.Empty
 val ss1 = prefix ++ {println("hello"); BigInt(4)} #:: BigInt(8) #:: Stream.Empty //will print 'hello' since the parameter to ++ is evaluated right away
 val ss2 = prefix #::: {println("hello"); BigInt(4)} #:: BigInt(8) #:: Stream.Empty //prints nothing, will print 'hello' when you reach the 3 component of the Stream
 ss2(1) //8, nothing printed
 ss2(2) //prints 'hello', 4
 ss2(2) //nothing printed since the Stream memoizes the value, 4