Scala筆記 27 - 重寫牛頓法開平方根，利用Streams

利用Streams重寫牛頓法開平方根

在筆記4中，我們之前嘗試做了牛頓法來開平方根，基本上是一個不斷收斂的過程，是否收斂是利用isGoodEnough function來檢驗：

如果改成Stream版本非常簡潔：

def sqrtStream(x: Double): Stream[Double] = {
  def improve(guess: Double) = (guess + x / guess) / 2  
  lazy val guesses: Stream[Double] = {
    println("eval") 
    1 #:: (guesses map improve)
  }
  guesses
}

sqrtStream(2).take(10).toList

但是guesses的定義相當奇怪，它是一個stream，從1開始去append到遞迴定義的tail Stream，而這個tail Stream就是把guess Stream中所有的數字都去做improve，有點難懂。嘗試來解譯上面的expression怎麼evaluate的：

首先直到toList被evaluate，guesses才會被evaluate，且只要evaluate stream中的前十個items:

itreation 1
此時guesses是的head是1，剩下的tail stream的定義是(guesses map improve)

iteration 2
此時要evaluate iteration 1中的tail stream的head，也就是
improve(1) = (1 + 2 / 1) / 2
剩下的tail stream 為head = improve(1)的stream

iteration 3
此時要evaluate iteration 2中的tail stream的head，也就是
improve( improve(1) )

.
.

所以  sqrtStream(2).take(10).toList
相當於精準控制了iteration做了10次，不用去管convergence的問題。

這個範例讓我感覺如果寫一個recursive stream定義的話，這個stream被take幾次相當于對其items重新加上幾次的recursive定義，所以第二個item被定義成recursion 1次，第三個item被定義成recursion 2次，以此類推。

在此例中，guesses也可以用def keyword定義成function，但是 "eval"字串被印出了10次，而lazy val宣告的guesses只會印出一次。我猜測由於stream本身是lazy val的關係，def版本的guesses並不會多做其他的事情，不過不知道怎麼驗證這件事。