第基于Python實(shí)現(xiàn)層次性數(shù)據(jù)和閉包性質(zhì)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

對(duì)鏈表的映射

另外一個(gè)特別擁有用的操作時(shí)將某種操作應(yīng)用于一個(gè)鏈表的所有元素，得到所有結(jié)果構(gòu)成的表。下面的過程將一個(gè)鏈表中的所有元素按給定因子做一次縮放：

defscale_list(items,factor):

ifitemsisNone:

returnNone

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

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

defmy_map(proc,items):

ifitemsisNone:

returnNone

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(lambdax:x**2,LinkedList(1,2,3,4,5))))

#1--4--9--16--25

這里的公共模式，其實(shí)就類似于設(shè)計(jì)模式中的模板方法，參見設(shè)計(jì)模式：模板方法。

現(xiàn)在我們可以用map給scale_list一個(gè)新定義：

defscale_list(items,factor):

returnLinkedList(my_map(lambdax:x*factor,items))

print(scale_list(LinkedList(1,2,3,4,5),10))

#10--20--30--40--50

map是一種很重要的結(jié)構(gòu)，不僅因?yàn)樗砹艘环N公共模式，而且因?yàn)樗⑵鹆艘环N處理表的高層抽象（與今日的Scala何其相似?。诶习姹镜膕cale_list中，程序的遞歸結(jié)構(gòu)將人的注意力吸引到對(duì)表中元素的逐個(gè)處理中。通過map定義的scale_list抑制了這種細(xì)節(jié)層面上的情況，強(qiáng)調(diào)的是從元素表到結(jié)果表的一個(gè)縮放變換。這兩種定義形式之間的差異，并不在于計(jì)算機(jī)會(huì)執(zhí)行不同的計(jì)算過程（其實(shí)不會(huì)），而在于我們對(duì)同一個(gè)過程的不同思考方式。從作用上看，map幫我們建起了一層抽象屏障，將實(shí)現(xiàn)表轉(zhuǎn)換過程的實(shí)現(xiàn)，與與如何提取表中元素以及組合結(jié)果的細(xì)節(jié)隔離開。

2.層次性結(jié)構(gòu)

注意，由于下面由于我們會(huì)涉及更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，我們統(tǒng)一將序列就用Python內(nèi)置的列表表示。

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

遞歸是處理樹結(jié)構(gòu)的一種很自然的工具，因?yàn)槲覀兂３？梢詫?duì)于樹的操作歸結(jié)為對(duì)它們的分支的操作，再將這種操作歸結(jié)為對(duì)分支的分支的操作，如此下去，直至達(dá)到了樹的葉子。如類似2.2.1中用length統(tǒng)計(jì)序列長度，我們通過以下代碼統(tǒng)計(jì)樹葉數(shù)目：

defcount_leaves(tree):

ifnottree:

return0

elifisinstance(tree,int):

return1

else:

returncount_leaves(tree[0])+count_leaves(tree[1:])

tree=[[1,2],3,4]

print(count_leaves(tree))#4

對(duì)樹的映射

map是處理序列的一種強(qiáng)有力抽象，與此類似，map與遞歸結(jié)合也是處理樹的一種強(qiáng)有力抽象。類似于2.2.1中用scale_list過程對(duì)序列元素進(jìn)行縮放，我們也可以設(shè)計(jì)scale_tree過程，該過程以一個(gè)因子和一棵葉子為數(shù)值的樹作為參數(shù)，返回一顆具有同樣形狀的樹，該樹中的每個(gè)數(shù)值都乘以了這個(gè)因子：

defscale_tree(tree,factor):

ifnottree:

return[]

ifisinstance(tree,int):

returntree*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]]

實(shí)現(xiàn)scale_tree的另一種方法是將樹看成子樹的序列，并對(duì)它使用map。我們?cè)谶@種序列上做映射，一次對(duì)各棵子樹做縮放，并返回結(jié)果的表。對(duì)于基礎(chǔ)情況，也就是當(dāng)被處理的樹是樹葉時(shí)，就直接用因子去乘它：

defscale_tree(tree,factor):

returnlist(map(lambdasub_tree:scale_tree(sub_tree,factor)

ifisinstance(sub_tree,list)

elsesub_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語言內(nèi)置的map，當(dāng)然也可以自己實(shí)現(xiàn)my_map，如下：

defmy_map(proc,items):

ifitems==[]:

return[]

else:

return[proc(items[0])]+my_map(proc,items[1:])

3.序列做為一種約定的界面

數(shù)據(jù)抽象可以讓我們?cè)O(shè)計(jì)出不被數(shù)據(jù)表示細(xì)節(jié)糾纏的程序，使程序保持很好的彈性。在這一節(jié)里，我們將要介紹與數(shù)據(jù)結(jié)構(gòu)有關(guān)的另一種強(qiáng)有力的設(shè)計(jì)原理使用約定的界面。

在1.3節(jié)中我們看到，通過實(shí)現(xiàn)為高階過程的程序抽象，可以讓我們抓住處理數(shù)值數(shù)據(jù)的一些程序模式。而在復(fù)合數(shù)據(jù)上工作做出類似的操作，則對(duì)我們操控?cái)?shù)據(jù)結(jié)構(gòu)的方式有著深刻的依賴性。如考慮一個(gè)與2.2.2節(jié)中的count_leaves類似的過程，它以一棵樹為參數(shù)，計(jì)算出那些值為奇數(shù)的葉子的平方和：

defsum_odd_squares(tree):

ifnottree:

return0

elifisinstance(tree,int):

iftree%2==1:

returntree**2

else:

return0

else:

returnsum_odd_squares(tree[0])+sum_odd_squares(tree[1:])

從表面上看，這一過程與下面的過程很不一樣。下面的這個(gè)過程給定一個(gè)整數(shù)nn，對(duì)k?nk?n計(jì)算Fib(k)并篩選出其中為偶數(shù)的值，其中Fib(k)為第kk個(gè)Fibonacci數(shù)（設(shè)第0個(gè)Fibonacci數(shù)為0）：

deffib(n):

ifn==0:

return0

elifn==1:

return1

else:

returnfib(n-1)+fib(n-2)

該過程表示如下：

defeven_fibs(n):#枚舉從0到n的整數(shù)

defnext(k):

ifkn:

return[]

else:

f=fib(k)#對(duì)每個(gè)整數(shù)計(jì)算其fib

iff%2==0:#過濾結(jié)果，選出其中偶數(shù)

return[f]+next(k+1)#累積結(jié)果

else:

returnnext(k+1)

returnnext(0)

print(even_fibs(5))#[0,2](即[011235]中的偶數(shù)為[0,2])

雖然sum_odd_squares過程和even_fibs過程結(jié)構(gòu)式差異非常大，但是對(duì)于兩個(gè)計(jì)算的抽象描述卻會(huì)揭露出它們間極大的相似性。sum_odd_squares過程：

枚舉出一棵樹的樹葉過濾它們，選出其中的奇數(shù)對(duì)選出的每一個(gè)數(shù)求平方用+累積起得到的結(jié)果

而sum_odd_squares過程：

枚舉從00到nn的整數(shù)對(duì)每個(gè)整數(shù)計(jì)算相應(yīng)的Fibonacci數(shù)過濾它們，選出其中的偶數(shù)用connect累計(jì)得到的結(jié)果

注意，connect函數(shù)用于對(duì)將兩個(gè)數(shù)值對(duì)象連接為列表或?qū)?shù)值對(duì)象加入一個(gè)列表，定義如下：

defcon(x,y):

#y規(guī)定為int，x可以為int或list

ifisinstance(x,int):

return[x]+[y]

else:

returnx+[y]

信號(hào)工程師可能會(huì)發(fā)現(xiàn)，這種過程其實(shí)可以描述為信號(hào)流過一系列的級(jí)聯(lián)處理步驟，每個(gè)步驟實(shí)現(xiàn)程序方案中的一部分。如下圖所示：

遺憾的是，上面兩個(gè)過程的定義并沒有展現(xiàn)這種信號(hào)流結(jié)構(gòu)。具體地說，我們的兩個(gè)過程將enumerate工作散布在程序中各處，并將它與map、filter和reduce混在一起。如果我