1.3 函數式編程經典示例

本節基于John Hughes的論文“Why Functional Programming Matters”，來分析一個函數式編程的經典實例，這篇文章出自論文集Research Topics in Functional Programming。

此論文深入分析了函數式編程，并提供了幾個例子，我們只分析其中的一個：用Newton-Raphson算法求解函數（平方根函數）。

該算法的許多實現都是通過loops顯式管理狀態的，比如Hughes的論文中就給出了一段Fortran代碼，通過有狀態的命令式流程求解。

算法的主體是如何根據當前的近似值計算出下一個近似值。函數next_()以sqrt(n)的當前近似值x為參數，計算出下一個近似值，并確保最終解就在之前近似值的范圍內，代碼如下所示。

        def next_(n, x):
            return (x + n / x) / 2

該函數計算出一系列值，相近兩個值的距離每次迭代減半，所以會迅速收斂到a=，即a=。這里沒有將迭代函數命名為next()，以避免與Python的內置函數發生沖突，使用next_()保證在不沖突的前提下盡量清晰地表達出函數的功能。

在命令提示符界面使用該函數，如下所示。

        >>> n = 2
        >>> f = lambda x: next_(n, x)
        >>> a0 = 1.0
        >>> [round(x,4) for x in (a0, f(a0), f(f(a0)), f(f(f(a0))), )]
        [1.0, 1.5, 1.4167, 1.4142]

首先定義收斂到的lambda表達式并賦值給變量f，將變量a0作為初始值，然后對一系列遞歸值求值：a1= f（a0）、a2 = f（f（a0）），等等。將這些函數放在一個生成器表達式中，便于對返回值做指定精度的四舍五入，從而使計算結果更易讀，并便于doctest使用。該序列會快速地向收斂。

我們可以編寫一個函數，生成一個含ai的無限長序列，向平方根收斂。

        def repeat(f, a):
            yield a
            for v in repeat(f, f(a)):
                yield v

該函數利用近似函數f()和初始值a生成近似值。如果把近似函數替換成前面定義的next_()函數，就可以得到關于參數n平方根的一系列近似值。

其中repeat()函數要求f()函數只有一個參數，而定義的next_()函數有兩個參數。可以用一個匿名函數對象lambda x: next_(n, x)綁定其中一個變量，創建next_()函數的部分綁定版本。

Python的生成器函數不能自動實現遞歸，必須顯式迭代遞歸結果，并一個一個單獨生成計算結果。使用return repeat(f, f(a))并不能多次循環生成一系列值，而會結束迭代并返回一個生成器表達式。

有兩種方法可以返回一系列值，而不是生成器表達式。

? 編寫顯式for循環：for x in some_iter: yield x

? 使用yield from語句：yield from some_iter

從遞歸生成器表達式中返回結果，這兩種方法的效果相同，這里傾向于使用yield from語句。不過在有些情況下，yield結合復雜表達式，往往比相應的映射和生成器表達式更清晰。

當然，我們并不想計算無限長序列，只要兩次迭代的近似值足夠接近，就可以任取其中一個作為最終解。通常用希臘字母ε表示兩個值足夠接近，這里的含義是計算平方根的誤差上限。

在Python中，我們需要設法從無限序列中一次取一個值，通常把復雜的遞歸包裹在簡單的接口函數中，見如下代碼片段。

        def within(ε, iterable):
            def head_tail(ε, a, iterable):
                b = next(iterable)
                if abs(a-b) <= ε: return b
                    return head_tail(ε, b, iterable)
            return head_tail(ε, next(iterable), iterable)

首先定義了內部函數head_tail()，以誤差允許范圍ε、可迭代序列中的一個值a和可迭代序列的剩余部分iterable為參數，iterable的下一個值與變量b綁定。如果|a-b|≤ε，兩個值距離足夠近，表明已找到平方根的解；否則以b為參數，遞歸調用函數head_tail()，以獲取下一次迭代的近似值。

函數within()只需要用參數iterable的第一個值初始化內部的head_tail()函數，后面由遞歸自動完成。

有些函數式語言允許將一個值放回可迭代序列，在Python中，這類似于用unget()或者previous()方法將一個值追加到迭代器中，然而Python的可迭代數據結構并沒有提供這種高級功能。

結合上面3個函數next_()、repeat()和within()，即可創建求平方根函數。

        def sqrt(a0, ε, n):
            return within(ε, repeat(lambda x: next_(n, x), a0))

repeat()函數基于next_(n, x)函數生成一個（可能的）無限長序列，當兩次迭代值之差小于ε時，within()即停止序列繼續生成值。

使用這個sqrt()函數需要提供一個初始值a0和誤差值ε，表達式sqrt(1.0, .0001, 3)表示從初始估計值1.0開始計算，誤差值為0.0001。對于大多數應用，初始值可以選擇1.0，不過初始值與實際平方根越接近，函數收斂越快。

以上近似算法的最初版本是用Miranda語言編寫的，可以看到Miranda和Python的實現之間有一些顯著區別，主要是Miranda可以構建cons，可以通過類似于unget的方式將值放回可迭代對象中。Miranda和Python的這種對比說明了Python適用于實現多種函數式編程技術。