Scala: Streams and the difference with Lists. Prime numbers with streams and filter.

streams.scala

// Ways to create Streams
val xs = Stream.cons(1, Stream.cons(2, Stream.empty))
val ys = Stream(1, 2, 3) // Using Stream as a factory
(1 to 1000).toStream // Stream(1, ?) -- Tail not yet evaluated

// Comparing Streams to Lists
def streamRange(lo: Int, hi: Int): Stream[Int] =
  if (lo >= hi) Sream.empty
  else Stream.cons(lo, streamRange(lo + 1, hi))
def listRange(lo: Int, hi: Int): Stream[Int] =
  if (lo >= hi) Nil
  else lo :: listRange(lo + 1, hi)
// They look the same but the streamRange will NOT generate
// any data structure (only a single cons pair 1 - ?),
// but it would know how to reconstitute the stream
// if somebody demands it. If I ask for the tail element,
// a second cons pair would be built (2 - ?) but in order
// to have all the range buit I would have to ask and USE it
((1000 to 10000).toList filter isPrime)(1) // NOT efficient!
((1000 to 10000).toStream filter isPrime)(1) // efficient

// BUT REMEMBER!
x :: xs // ALWAYS produces a List, never a Stream
y #:: ys // Does produce a Stream, is equivalent to:
Stream.cons(y, ys)

// As values are only computated as needed
// we can construct infinite Streams
def from(n: Int): Stream[Int] = n #:: from(n + 1)
val natural_numbers = from(0)
val multiples_of_four = natural_numbers map (_ * 4)
multiples_of_four.take(100).toList // to see them...

// Computing square root (Newton), just recursion
def sqrt(x: Double) = {
  def sqrtIter(guess: Double): Double =
    if (isGoodEnough(guess)) guess
    else sqrtIter(improve(guess))
  def improve(guess: Double) = (guess + x / guess) / 2
  def isGoodEnough(guess: Double) =
    math.abs((guess * guess - x) / x) < 0.0001
  sqrtIter(1.0, x)
}

// Computing square root (Newton), with Streams 
def sqrtStream(x: Double): Stream[Double] = {
  def improve(guess: Double) = (guess + x / guess) / 2
  lazy val guesses: Stream[Double] = 1 #:: (guesses map improve)
  guesses
}

// Sream of aproximations
// All iterations in a list, last values more precise (2.0)
sqrtStream(4).take(10).toList

// We add isGoodEnough later
def isGoodEnough(guess: Double, x: Double) =
  math.abs((guess * guess - x) / x) < 0.0001

// We can filter the stream and just take
// the first one because it's good enough
sqrtStream(4) filter (isGoodEnough(_, 4))