不同編程即為不同解決問題的思路
解決一個問題有很多思路煮落，比如：
- 過程式(C語言)：將解決問題的方式分解成若干步驟來控制數(shù)據(jù)澜建。
- 面向?qū)ο笫?(Java/Ruby)：以對象為基本單位署恍，定義其行為控制其內(nèi)部狀態(tài)碧查，通過不同對象之間的協(xié)作解決問題约啊。
- 函數(shù)式(Lisp)：一切皆為函數(shù)喻喳，用連貫的思維方式定義過程另玖，常用遞歸。
- 組合式：將不同的解決方式組合起來表伦，golang 經(jīng)常會將面向?qū)ο笈c過程式組合起來谦去。
示例： Huffman編碼
用 Lisp 的一個方言 Scheme 來實現(xiàn)：
輸入 '((A 1) (B 3) (C 2)), A B C 為帶編碼字符，1 2 3 為出現(xiàn)次數(shù)蹦哼。
輸出 '((b 0) (a 0 1) c 1 1)
定義葉子節(jié)點
(define (make-leaf symbol weight)
(list 'leaf symbol weight))
(define (leaf? object)
(eq? (car object) 'leaf))
(define (symbol-leaf object)
(cadr object))
(define (weight-leaf object)
(caddr object))
如果沒有接觸過 lisp 的同學(xué)可能對上面的表示方式有點陌生鳄哭，其實就是用括號代表方法調(diào)用，括號里的第一個位置是方法名稱纲熏，后面的是調(diào)用該方法的參數(shù)妆丘。
上面的幾行代碼定義了葉子節(jié)點 leaf 及相關(guān)函數(shù)锄俄。
定義樹節(jié)點
(define (make-code-tree left right)
(list
left
right
(append (symbols left) (symbols right))
(+ (weight left) (weight right))))
(define (left-branch tree) (car tree))
(define (right-branch tree) (cadr tree))
(define (symbols tree)
(if (leaf? tree)
(list (symbol-leaf tree))
(caddr tree)))
(define (weight tree)
(if (leaf? tree)
(weight-leaf tree)
(cadddr tree)))
同樣的道理，定義了用于在構(gòu)造 Huffman 樹中非葉子的節(jié)點 tree 及其相關(guān)取值函數(shù)勺拣。
有序 list 構(gòu)造方法
(define (adjoin-set x set)
;如果 set 為空奶赠，則返回以 x 作為唯一元素的 list
(cond ((null? set)
(list x))
;如果 set 的第一個元素的 weight 大于 x 的 weight，則將 x 和 set 組合成一個新的 list 返回
((> (weight (car set)) (weight x))
(cons x set))
; 否則將 set 的以第一個只取出药有，讓后遞歸調(diào)用 `adjoin-set`
(else (cons (car set) (adjoin-set x (cdr set))))))
(define (make-leaf-set pairs)
(if (null? pairs)
'()
(let ((pair (car pairs)))
(adjoin-set (make-leaf (car pair) (cadr pair))
(make-leaf-set (cdr pairs))))))
adjoin-set 的功能就是 x 插入到有序 list set 中车柠，保證插入后的 list 仍然有序。lisp 中的 cond 可理解為 其他語言中的 switch塑猖，而 cons 可理解為將兩個元素結(jié)合成一個 list。 乍一看這個所謂“插入”元素的方法有點奇怪谈跛，而且沒有用任何臨時變量羊苟。其思路將整個插入的過程用遞歸調(diào)用的方式表示： 用過程（函數(shù)）代替了臨時變量。舉了例子：(adjoin-set 3 '(1 2))感憾，執(zhí)行順序是：
(cons 1 (adjoin-set 3 '(2)))
(cons 1 (cons 2 (adjoin-set 3 '())))
(cons 1 (cons 2 (cons 3 '())))
(cons 1 (cons 2 '(3)))
(cons 1 '(2 3))
'(1 2 3)
可以看到在執(zhí)行序列中蜡励，推遲 cons 的執(zhí)行，用參數(shù)求值壓棧從而省去了臨時變量阻桅。在 make-leaf-set 中思路也一樣：不斷地從 paris 中取元素凉倚，交給 adjoin-set 插入到 list 中。整個編寫過程中基本上用程序流暢地表達(dá)了我們的解題思路嫂沉。
Huffman樹構(gòu)造方法
在插入元素這種簡單的問題中函數(shù)式威力還遠(yuǎn)遠(yuǎn)沒有體現(xiàn)出來稽寒，請看下面構(gòu)造 Huffman樹 的函數(shù)實現(xiàn)：
(define (make-tree leaves)
(cond ((or (null? (car leaves)) (null? (cadr leaves)))
(error "leaves is not enough"))
((null? (cddr leaves))
(make-code-tree (car leaves) (cadr leaves)))
(else (make-tree (adjoin-set (make-code-tree (car leaves) (cadr leaves)) (cddr leaves))))))
幾行代碼就將構(gòu)造 Huffman樹 的核心邏輯表達(dá)清楚了：將按 weight 升序 leaves 的前兩個拿出來做成一個 tree node，adjoin-set 到剩下的 leaves 中趟章，然后不斷重復(fù)這個操作杏糙，直到 leaves 中只剩下兩個元素，將這兩個元素最為 最終 Huffman樹 的左右子樹蚓土，然后返回宏侍。怎么樣？一氣呵成蜀漆。
編碼
對 Huffman樹 遍歷編碼的實現(xiàn)也是精煉得有種思維的美感：
先進行左子樹遍歷谅河，直到找到葉子節(jié)點，構(gòu)造成結(jié)果 list 中一個元素确丢，然后回到上一層遞歸绷耍，進入右子樹，不斷重復(fù)直到遍歷完所有節(jié)點蠕嫁。
(define (encode tree)
(define (visit n bits)
(if (leaf? n)
; 找到了一個葉子節(jié)點
(cons (symbol-leaf n) bits)
; 用 cons 對 visit 的遞歸調(diào)用
(cons (visit (left-branch n) (cons 0 bits))
(visit (right-branch n) (cons 1 bits)))))
(visit tree '()))
;測試
(define leaf-set (make-leaf-set '((A 1) (B 3) (C 2))))
(define tree (make-tree leaf-set))
(encode tree) ; outputs: ((b 0) (a 0 1) c 1 1)
詳細(xì)代碼請進 github
ps: 本篇用到部分《計算機程序的構(gòu)造與解析》代碼锨天。強烈建議大家學(xué)習(xí) MIT 的這門公開課。
