前段時間的思考題的答案v2.0

01-25

給大家留一道Python的思考題 - 知乎專欄

前兩天的Python思考題，給大家一個參考答案 - 知乎專欄

hubo1016/pychecktype

前段時間出了個類型檢查函數的思考題，以及參考答案。有的時候一旦寫出一個有點通用性的東西，就會去想怎麼增加它的擴展性和易用性。

之前我們的演算法里已經解決了遞歸結構（自引用）帶來的各種問題，在之前的階段中我們是將這個問題看成了一個數學問題，這可以算是「技術」，但還不夠「工程」，如果有人想要利用這種演算法，就必須對整個演算法有比較深入的了解，根據原理重新實現自己需要的功能。而「工程」，需要讓使用者對這個演算法只有最小程度的了解，就可以充分利用它。要做到這一點，我們就需要對問題和演算法都有更深入的抽象。

-----------------------------------------------------------------------------------------------

我們之前的演算法中實現了對list和dict類型的遞歸結構的支持，現在我們想要將它推廣到一般性的遞歸數據結構中。首先我們將問題進一步抽象化：

我們有數據V和數據類型T，轉換的結果表示為f(V, T)。不幸的是直接計算f(V, T)的過程可能回過頭來依賴f(V, T)。好在f(V, T)是個純函數，對於相同的數據和類型永遠返回相同的結果。

------------------------------------------------------------------------------------------------

我們解決這個問題主要有兩種策略：

生成一個遞歸結構，如[]和{}中的那樣：首先創建一個空的結構存起來，然後遞歸，如果遞歸過程中又遇到了f(V, T)，直接返回提前保存了的引用，從而創建遞歸結構。
禁止自引用，如將標量轉換成只有一個元素的列表時候的情況：如果沒有經過其他遞歸結構直接重新調用了f(V, T)，則直接失敗

兩種情況都可以歸結為以下的過程：

準備 - 對於遞歸結構來說，創建空的結構並存起來；對於禁止遞歸來說，保存禁止遞歸的標記
遞歸 - 開始遞歸計算，如果遞歸中遇到了標記則進行相應的處理（直接返回或失敗）

-----------------------------------------------------------------------------------------------

做到這一步，我們接下來要為這個演算法提取一個面向工程的擴展介面，讓使用這個介面的人只需要對演算法有最小的了解即可。重新看上面的結論，對於標記的處理是固定的，需要擴展的只有：

如何創建空的結構（或者不創建，即禁止自引用）
如何遞歸計算

我們設計的介面也只要提供這樣的能力就足夠了，這就是答案2.0版本中對於類型檢查過程的抽象：

class CustomizedChecker(object): """ Inherit from this class to create a customized type checker """ def __init__(self, *args, **kwargs): """ Call bind() """ if args or kwargs: self.bind(*args, **kwargs) def bind(self): """ Allow delayed init """ pass def pre_check_type(self, value): """ First-step check for value. This step should not do any recursive check. :param value: value to be checked :return: An object if recursive creation if needed, or None if not needed. TypeMismatchException should be raised if there is something wrong. """ return None def final_check_type(self, value, current_result, recursive_check_type): """ Second-step check for value. This step can use recursive check. :param value: value to be checked :param current_result: value returned by pre_check_type. If this value is not None, the return value must be the same object. :param recursive_check_type: a function recursive_check_type(value, type) to be called to do recursive type check """ raise NotImplementedError

這裡比較重要的過程是pre_check_type和final_check_type兩個，其中pre_check_type的參數很直白，就是要檢查的值，在這個過程中不允許進行遞歸檢查，通常類只做最少最必要的檢查，然後選擇：

如果該類型支持遞歸，則創建一個空的結構，然後返回這個新創建的對象；
否則返回None，表示不支持直接遞歸

final_check_type是進行遞歸的地方，它有三個參數，value還是剛才的值，current_result是pre_check_type的返回值，如果pre_check_type返回了一個非None的對象，這個過程應該修改這個對象並返回相同的引用；否則應該返回一個新的對象。recursive_check_type是個函數，調用recursive_check_type就可以進行遞歸的類型檢查和類型轉換，在其中會自動處理自引用或者禁止自引用的邏輯，而擴展介面中不需要關心這些，實現細節都封閉在了recursive_check_type這個閉包中。這樣要擴展一個類型就非常容易了。

經過這一步之後，我們可以將以前的處理dict和list的代碼都統一重構成CustomizedChecker的子類，主函數中的邏輯也更加簡潔了：

def _customized_check(checker): if check_id in list_loop: raise TypeMismatchException(value, type_) current_result = checker.pre_check_type(value) if current_result is None: # Prevent an infinite loop list_loop.add(check_id) try: current_result = checker.final_check_type(value, None, lambda value, type: _check_type_inner(value, type, _recursive_check)) finally: list_loop.discard(check_id) else: current_check[check_id] = current_result # backup succedded check: it may depends on current result. If the type match fails, revert all succeeded check _new_recursive_check = (current_check, dict(succeded_check), failed_check, set()) checker.final_check_type(value, current_result, lambda value, type: _check_type_inner(value, type, _new_recursive_check)) # copy succeeded checks succeded_check.clear() succeded_check.update(_new_recursive_check[1]) return current_result

使用新的面向工程的介面，在做自定義擴展的時候就一點都不擔心會做錯了。

新版本的功能擴展到了什麼程度呢？代碼里有個例子，它可以檢查一個單鏈表，並將它轉換成一個雙向鏈表……這並不是極限，實際上它還可以將多叉樹轉換成二叉樹（孩子轉為左子樹，兄弟轉為右子樹），邊錶轉換成鄰接表，遞歸結構轉換成id標識的非遞歸結構等等……

它基本上變成一種新的編程語言了（捂臉）