SICP 2.2: 層次性資料和閉包性質(Python實作)

緒論

序對可以為我們提供用于構造復合資料的基本“粘接劑”，鑒于Python中tuple中元素不可變的性質，我們通過list來實作序對，如[1, 2]，Python的PyListObject物件中實際是存放的是PyObject*指標， 所以可以將PyListObject視為vecter<PyObject*>，這是一種盒子與指標表示方式(list內的元素表示為一個指向物件盒子的指標)，對于[1, 2]，可將其視為以下結構：

我們不僅可以用[]去組合起各種數值，也可以用它取組合起其它序對，這樣，序對就是一種通用的建筑砌塊，通過它可以構造所有不同種類的資料結構來，比如想組合數值1, 2, 3, 4，我們可以用[[1, 2], [3, 4]]的方式(下圖左)，也可以用[[1, [2, 3]], 4](下圖右)：

可以構建元素本身也是序對的序對，這種能力稱為[]的閉包性質，注意，這里的閉包是來自抽象代數的術語（不是Python語法中那個閉包），抽象代數中，如果將某個運算（操作）作用于某個集合的特定元素 ，產出的仍然是該集合的元素，則稱該集合元素在該運算之下封閉，我們這里說組合資料物件的操作滿足閉包性質，指通過它組合起資料物件得到的結果本身還可以通過同樣的操作再進行組合，

閉包性質可以使我們構建層次性的結構，這種結構由一些部分構成，而其中的各個部分又是由它們的部分構成，并且可以繼續下去，下面我們介紹用序對來表示序列和樹，

2.2.1 序列的表示

利用序對可以夠造出的一類有用結構是序列——一批資料物件的有序匯集，利用序對表示序列的方式很多，一種最直接的表示方式為[1, [2, [3, [4, None]]]]如下圖所示：

我們不妨將這種通過嵌套序對形成的序列稱為鏈表，因為Python本身不內置鏈表結構，我們不妨用序對來實作鏈表：

class LinkedList():
    def __init__(self, *items) -> None:
        """提供兩種初始化方式:序對或多個元素
        """
        if isinstance(items[0], list):
            self.pair = items[0]
        else:
            self.pair = self._construct(*items)

    def _construct(self, *items):
        """遞回地構造鏈表
        """
        if items == ():
            return None
        else:
            item, *rest = items
            return [item, self._construct(*rest)]

    def __repr__(self):
        """重寫列印函式
        """
        return "-->".join(map(str, self._flatten(self.pair)))

    def _flatten(self, pair):
        """遍歷鏈表，回傳其一維展開
        """
        if pair is None:
            return []
        else:
            return [pair[0]] + self._flatten(pair[1])

    @property
    def head(self):
        """獲取鏈表頭部元素
        """
        return self.pair[0]

    @property
    def rest(self):
        """獲取鏈表頭部元素之外的元素，并以鏈表形式回傳
        """
        if self.pair[1] is None:
            return None
        else:
            return LinkedList(self.pair[1])

這樣，我們就可以方便地構造鏈表并將其列印輸出了：

print(LinkedList(1, 2, 3, 4))
# 1-->2-->3-->4

注意，None用于表示序對的鏈結束，在語言設計上可能有以下爭論：None應該是個普通的名字嗎？None應該算是一個普通的名字嗎？None應該算是一個符號嗎？他應該算是一個空表嗎？在Python中，解決此問題的手段是將None的型別規定為<class 'NoneType'>，

表操作

利用序對將元素的序串列示為鏈表之后，我們就可以使用常規的程式設計技術，通過獲取鏈表的head和rest的方式完成對鏈表的各種操作了，如下面的程序list-ref實際引數是一個表和一個數n，它回傳這個表中的第n項：

def list_ref(items, n):
    if n == 0:
        return items.head
    else:
        return list_ref(items.rest, n-1)

print(list_ref(LinkedList(1, 4, 9, 16, 25), 3)) # 16

length程序則用于回傳表中的項數：

def length(items):
    if items is None:
        return 0
    else:
        return 1 + length(items.rest)

print(length(LinkedList(1, 3, 5, 7))) # 4

或者寫為迭代的形式(此處用尾遞回的形式，即遞回呼叫是整個函式體中最后執行的陳述句且它的回傳值不屬于運算式的一部分時，這樣就無需保存回傳值，可在常數空間內執行迭代型計算):

# 以迭代的方式計算lengths(尾遞回)
def length(items):
    def length_iter(a, count):
        if a is None:
            return count
        else:
            return length_iter(a.rest, count + 1)
    return length_iter(items, 0)

print(length(LinkedList(1, 3, 5, 7))) # 4

當然， Python解釋器默認是不開啟尾遞回優化的，需要用其他黑魔法實作，參考《Python開啟尾遞回優化!》

還有一種常見操作是append，如對odds：[1, 3, 5, 7]、squares:[1, 4, 9, 16, 25]、append(odds, squares) 得[1 3 5 7 1 4 9 16 25]，append(squares, odds)得[1 4 9 16 25 1 3 5 7]，也可以通過遞回實作：

def append(lk_list1, lk_list2):
    if lk_list1 is None:
        return lk_list2.pair
    else:
        return [lk_list1.head, append(lk_list1.rest, lk_list2)]


odds = LinkedList(1, 3, 5, 7)
squares = LinkedList(1, 4, 9, 16, 25)
print(LinkedList(append(odds, squares))) # 1-->3-->5-->7-->1-->4-->9-->16-->25
print(LinkedList(append(squares, odds))) # 1-->4-->9-->16-->25-->1-->3-->5-->7

對鏈表的映射

另外一個特別擁有用的操作時將某種操作應用于一個鏈表的所有元素，得到所有結果構成的表，下面的程序將一個鏈表中的所有元素按給定因子做一次縮放：

def scale_list(items, factor):
    if items is None:
        return None
    else:
        return [items.head * factor, scale_list(items.rest, factor)]

print(LinkedList(scale_list(LinkedList(1, 2, 3, 4, 5), 10)))
# 10-->20-->30-->40-->50

我們可以抽象出這一具有一般性的想法，將其中的公共模式表述為一個高階函式(接收其它函式做為引數)，

def my_map(proc, items):
    if items is None:
        return None
    else:
        return [proc(items.head), my_map(proc, items.rest)]

print(LinkedList(my_map(abs, LinkedList(-10, 2.5, -11.6, 17))))
# 10-->2.5-->11.6-->17
print(LinkedList(my_map(lambda x: x**2, LinkedList(1, 2, 3, 4, 5))))
# 1-->4-->9-->16-->25

這里的公共模式，其實就類似于設計模式中的模板方法，參見設計模式：模板方法，

現在我們可以用map給scale_list一個新定義：

def scale_list(items, factor):
    return LinkedList(my_map(lambda x: x*factor, items))

print(scale_list(LinkedList(1, 2, 3, 4, 5), 10))
# 10-->20-->30-->40-->50

map是一種很重要的結構，不僅因為它代表了一種公共模式，而且因為它建立起了一種處理表的高層抽象（與今日的Scala何其相似！），在老版本的scale_list中，程式的遞回結構將人的注意力吸引到對表中元素的逐個處理中，通過map定義的scale_list抑制了這種細節層面上的情況，強調的是從元素表到結果表的一個縮放變換，這兩種定義形式之間的差異，并不在于計算機會執行不同的計算程序（其實不會），而在于我們對同一個程序的不同思考方式， 從作用上看，map幫我們建起了一層抽象屏障，將實作表轉換程序的實作，與與如何提取表中元素以及組合結果的細節隔離開，

2.2.2 層次性結構

注意，由于下面由于我們會涉及更復雜的資料結構，我們統一將序列就用Python內置的串列表示，

我們下面來看元素本身也是序列的序列，比如我們可以認為[[1, 2], 3, 4]是將[1, 2]做為元素加入序列[3, 4]而得，這種表結構可以看做是樹，即序列中的元素就是樹的分支，而那些本身也是序列的元素就形成了樹中的子樹：

遞回是處理樹結構的一種很自然的工具，因為我們常常可以將對于樹的操作歸結為對它們的分支的操作，再將這種操作歸結為對分支的分支的操作，如此下去，直至達到了樹的葉子，如類似2.2.1中用length統計序列長度，我們通過以下代碼統計樹葉數目：

def count_leaves(tree):
    if not tree:
        return 0
    elif isinstance(tree, int):
        return 1
    else:
        return count_leaves(tree[0]) + count_leaves(tree[1:])
tree = [[1, 2], 3, 4]
print(count_leaves(tree)) # 4

對樹的映射

map是處理序列的一種強有力抽象，與此類似，map與遞回結合也是處理樹的一種強有力抽象，類似于2.2.1中用scale_list程序對序列元素進行縮放，我們也可以設計scale_tree程序，該程序以一個因子和一棵葉子為數值的樹作為引數，回傳一顆具有同樣形狀的樹，該樹中的每個數值都乘以了這個因子：

def scale_tree(tree, factor):
    if not tree:
        return []
    if isinstance(tree, int):
        return tree * factor
    else:
        return [scale_tree(tree[0], factor)] + scale_tree(tree[1:], factor)

tree = [1, [2, [3, 4], 5], [6, 7]]
print(scale_tree(tree, 10))
# [10, [20, [30, 40], 50], [60, 70]]

實作scale_tree的另一種方法是將樹看成子樹的序列，并對它使用map，我們在這種序列上做映射，一次對各棵子樹做縮放，并回傳結果的表，對于基礎情況，也就是當被處理的樹是樹葉時，就直接用因子去乘它：

def scale_tree(tree, factor):
    return list(map(lambda sub_tree: scale_tree(sub_tree, factor)
                    if isinstance(sub_tree, list)
                    else sub_tree * factor, tree))
tree = [1, [2, [3, 4], 5], [6, 7]]
print(scale_tree(tree, 10))
# [10, [20, [30, 40], 50], [60, 70]]

此處的map我們直接采用Python語言內置的map，當然也可以自己實作my_map，如下：

def my_map(proc, items):
    if items == []:
        return []
    else:
        return [proc(items[0])] + my_map(proc, items[1:])

2.2.3 序列做為一種約定的界面

資料抽象可以讓我們設計出不被資料表示細節糾纏的程式，使程式保持很好的彈性，在這一節里，我們將要介紹與資料結構有關的另一種強有力的設計原理——使用約定的界面，

在1.3節中我們看到，通過實作為高階程序的程式抽象，可以讓我們抓住處理數值資料的一些程式模式，而在復合資料上作業做出類似的操作，則對我們操控資料結構的方式有著深刻的依賴性，如考慮一個與2.2.2節中的count_leaves類似的程序，它以一棵樹為引數，計算出那些值為奇數的葉子的平方和：

def sum_odd_squares(tree):
    if not tree:
        return 0
    elif isinstance(tree, int):
        if tree % 2 == 1:
            return tree**2
        else:
            return 0
    else:
        return sum_odd_squares(tree[0]) + sum_odd_squares(tree[1:])

從表面上看，這一程序與下面的程序很不一樣，下面的這個程序給定一個整數\(n\)，對\(\forall k \leqslant n\)計算Fib(k)并篩選出其中為偶數的值，其中Fib(k)為第\(k\)個Fibonacci數（設第0個Fibonacci數為0）：

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

該程序表示如下：

def even_fibs(n):  # 列舉從0到n的整數
    def next(k):
        if k > n:
            return []
        else:
            f = fib(k)  # 對每個整數計算其fib
            if f % 2 == 0:  # 過濾結果，選出其中偶數
                return [f] + next(k + 1)  # 累積結果
            else:
                return next(k+1)
    return next(0)
print(even_fibs(5)) # [0, 2] (即[0 1 1 2 3 5]中的偶數為[0, 2])

雖然sum_odd_squares程序和even_fibs程序結構式差異非常大，但是對于兩個計算的抽象描述卻會揭露出它們間極大的相似性，sum_odd_squares程序：

• 列舉出一棵樹的樹葉
• 過濾它們，選出其中的奇數
• 對選出的每一個數求平方
• 用+累積起得到的結果

而 sum_odd_squares程序：

• 列舉從\(0\)到\(n\)的整數
• 對每個整數計算相應的Fibonacci數
• 過濾它們，選出其中的偶數
• 用connect累計得到的結果

注意，connect函式用于對將兩個數值物件連接為串列或將數值物件加入一個串列，定義如下：

def con(x, y):
    # y規定為int，x可以為int或list
    if isinstance(x, int):
        return [x] + [y]
    else:
        return x + [y]

信號工程師可能會發現，這種程序其實可以描述為信號流過一系列的級聯處理步驟，每個步驟實作程式方案中的一部分，如下圖所示：

遺憾的是，上面兩個程序的定義并沒有展現這種信號流結構，具體地說，我們的兩個程序將enumerate作業散布在程式中各處，并將它與map、filter和reduce混在一起，如果我們能夠重新組織這一程式，使信號流結構明顯表現在寫出的程序中，將會大大提高代碼的清晰性，

其中map、filter、reduce算子可以采用Python內置函式，也可以自己實作，自己實作的話可以這樣寫：

def my_map(proc, sequence):
    if not sequence:
        return []
    else:
        return [proc(sequence[0])] + my_map(proc, sequence[1:])


print(my_map(lambda x: x**2, [1, 2, 3, 4, 5]))
# [1, 4, 9, 16, 25]


def my_filter(predicate, sequence):
    if not sequence:
        return []
    elif predicate(sequence[0]):
        return [sequence[0]] + my_filter(predicate, sequence[1:])
    else:
        return my_filter(predicate, sequence[1:])


print(my_filter(lambda x: x % 2, [1, 2, 3, 4, 5]))
# [1, 3, 5]


# print(list(accumulate([1,2,3])))

def my_reduce(op, sequence):
    if sequence[-1] and not sequence[:-1]:
        return sequence[-1]
    else:
        return op(my_reduce(op, sequence[:-1]), sequence[-1])

print(my_reduce(add, [1, 2, 3, 4, 5])) # 15
print(my_reduce(mul, [1, 2, 3, 4, 5])) # 120
print(my_reduce(con, [1, 2, 3, 4, 5])) # [1, 2, 3, 4, 5]

為了簡便起見，我們下面map、filter、reduce算子統一采用Python內置函式，

除了這三個算子之外，我們還需要列舉(enumerate)出需要處理的資料序列，對于even-fibs，我們需要生成一個給定區間里的整數序列：

def enumerate_interval(low, high):
    if low > high:
        return []
    else:
        return [low] + enumerate_interval(low + 1, high)

print(enumerate_interval(2, 7)) # [2, 3, 4, 5, 6, 7]

對于sum_odd_squares，則需要列舉出一棵樹的所有樹葉：

# 列舉一棵樹所有的樹葉：
def enumerate_tree(tree):
    if not tree:
        return []
    elif isinstance(tree, int):
        return [tree]
    else:
        return enumerate_tree(tree[0]) + enumerate_tree(tree[1:])

print(enumerate_tree([1, [2, [3, 4], 5]])) # [1, 2, 3, 4, 5]

現在，我們就可以像上面的信號流圖那樣重新構造sum_odd_squares和even-fibs了，

sum_odd_squares的構造方法如下：

def sum_odd_squares(tree):
    return reduce(add,
                  map(lambda x: x**2,
                      filter(lambda x: x % 2,
                             enumerate_tree(tree))))

print(sum_odd_squares([1, 2, 3, 4, 5])) # 35

even-fibs的構造方法如下：

def even_fibs(n):
    return reduce(con,
                  filter(lambda x: not x % 2,
                         map(fib,
                             enumerate_interval(0, n))))

print(even_fibs(5)) #[0, 2]

將程式表示為一些針對序列的操作，這樣做的價值就愛在于能幫助我們得到模塊化的程式設計，而在工程設計中，模塊化結構是控制復雜性的一種威力強大的策略，如同信號處理中設計者從標準的過濾器和變換裝置中選出一些東西來級聯，從而構造出各種系統，同樣地，序列操作也形成了一個可以混合和匹配使用的標準程式元素庫，

如我們在另一個產生前\(n+1\)個Fibonacci數的平方的程式里，就可以使用取自程序sum_odd_squares和even-fibs的片段：

def list_fib_squares(n):
    return reduce(con,
                  map(lambda x: x**2,
                      map(fib,
                          enumerate_interval(0, n))))

print(list_fib_squares(5)) # [0, 1, 1, 4, 9, 25]

也可以重新安排有關的各個片段，將它們用在產生一個序列中所有奇數的平方之乘積的程式里：

def product_of_squares_of_odd_elements_sequence(sequence):
    return reduce(mul,
                  map(lambda x: x**2,
                      filter(lambda x: x % 2, sequence)))

print(product_of_squares_of_odd_elements_sequence([1, 2, 3, 4, 5])) # [0, 1, 1, 4, 9, 25]

我們同樣可以采用序列操作的方式，重新去形式化各種常規的資料處理應用，假定有一個人事記錄的序列，現在希望找出其中薪水最高的程式員的工資，假定有一個salary回傳記錄中的工資，謂詞函式is_programmer檢查某個記錄是不是程式員，此時我們就可以寫：

def salary_of_hightest_paid_programmer(records):
    return reduce(max,
                  map(salary,
                      filter(is_programmer, records)))

在這里，用表實作的序列被做為一種方便的界面，我們可以利用這種界面去組合起各種處理模塊，

參考

• [1] Abelson H, Sussman G J. Structure and interpretation of computer programs[M]. The MIT Press, 1996.
• [2] 陳儒. Python原始碼剖析：深度探索動態語言核心技術[M]. 電子工業出版社, 2008.
• [3] https://zh.wikipedia.org/wiki/尾呼叫
• [4] https://segmentfault.com/a/1190000007641519
• [5] https://zh.wikipedia.org/zh-tw/模板方法
• [6] https://www.zhihu.com/question/26549715/answer/34336593

標籤：其他

上一篇：Python資料結構與演算法（1）

下一篇：【轉譯】在中國失敗的美國公司