1.1.7 實例：用牛頓法求平方根

上面介紹的函數很像常規的數學函數，它們描述的都是根據一個或幾個參數確定一個值。然而，在數學的函數和計算機的函數之間有一個重要的差異，那就是，計算機的函數還必須是有效可行的。

作為實例，現在考慮計算平方根的問題。我們可以把平方根函數定義為：

得到那樣的y，能使得y≥0而且y2=x

這句話描述了一個完全合法的數學函數，我們可以根據它去判斷某個數是否為另一個數的平方根，或根據它推導出一些有關平方根的一般性事實。然而，在另一方面，這個定義并沒有描述計算機函數，因為它確實沒有告訴我們，在拿到一個數之后，如何實際地找出這個數的平方根。即使采用類似JavaScript的形式重寫一遍這個定義也無濟于事：

這只不過是重述了原來的問題。

數學函數與計算機的函數之間的明顯對比，不過是描述事物的特征，與描述如何去做出這一事物之間的普遍性差異的一個具體反映。換一種說法，人們有時也把它說成是說明性的知識與行動性的知識之間的差異。在數學里，我們通常關心的是說明性的描述（是什么），而在計算機科學里，人們則通常關心行動性的描述（怎么做）[17]。

怎樣才能計算出平方根呢？最常用的就是牛頓的逐步逼近方法。這一方法告訴我們，如果對x的平方根值有了一個猜測y，那么就可以通過執行一個簡單操作，得到一個更好的猜測（它更接近實際平方根的值）：只需要求出y和x/y的平均值[18]。例如，我們可以用這種方式計算2的平方根，假定初始值是1：

繼續這一計算過程，我們就能得到2的平方根的越來越好的近似值。

現在，讓我們用函數的語言來描述這一計算過程。開始時，我們有被開方的數值（要做的就是計算它的平方根）和一個猜測值。如果猜測值對我們的用途而言已經足夠好，工作就完成了。如若不然，就需要重復上述計算過程去改進這個猜測值。我們可以把這一基本策略寫成下面的函數：

改進猜測值的方法，就是求出它與被開方數除以這個舊猜測的平均值：

其中

我們還必須說明什么是“足夠好”。下面的做法只是為了說明問題，它實際上并不是一個很好的檢測方法（參看練習1.7）。這里的想法是，不斷改進答案直至它足夠接近平方根，使其平方與被開方數之差小于某個事先確定的誤差值（這里用的是0.001）[19]：

最后，還需要一種方法啟動整個工作。例如，對任何數，我們都可以猜其平方根為1：

如果把這些聲明都送給解釋器，我們就可以像使用其他函數一樣使用sqrt了：

這個sqrt程序也說明，至今已經介紹的這個簡單的函數式語言，已經足以寫出可以用其他語言（例如C或Pascal）寫出的任何純粹數值計算的程序了。這件事看起來可能很讓人吃驚，因為在我們的語言里甚至沒有包括任何迭代結構（循環，它們可用于指揮計算機去一遍遍地做某些事情）。而在另一方面，sqrt_iter展示了如何不用特殊的迭代結構來實現迭代，其中只需要使用常規的函數調用能力[20]。

練習1.6 Alyssa P.Hacker不喜歡條件表達式的語法，因為其中涉及符號?和:。她問：“為什么我不能直接聲明一個常規的條件函數，其應用的工作方式就像條件表達式呢？”[21]Alyssa的朋友Eva Lu Ator斷言確實可以這樣做，并聲明了一個名為conditional的函數：

Eva給Alyssa演示了她的程序：

她很高興地用自己的conditional函數重寫了求平方根的程序：

當Alyssa試著用這個函數去計算平方根時會發生什么情況？請給出解釋。

練習1.7 在計算很小的數的平方根時，用is_good_enough檢測不是很有效。還有，在實際計算機里，算術運算總以一定的有限精度進行。這會使我們的檢測不適合用于對很大的數的計算。請解釋上述論斷，并用例子說明對很小的和很大的數，這種檢測都可能失效。實現is_good_enough的另一策略是監視猜測值在一次迭代中的變化情況，當變化的值相對于猜測值之比很小時就結束。請設計一個采用這種終止測試方式的平方根函數。對很大的和很小的數，這一策略都能工作得更好嗎？

練習1.8 求立方根的牛頓法基于如下事實，如果y是x的立方根的一個近似值，那么下式能給出一個更好的近似值：

請利用這個公式，實現一個類似平方根函數的求立方根的函數。（在1.3.4節，我們將看到如何實現一般的牛頓法，它是這里的求平方根和立方根函數的抽象。）