坐 Huffman coding 为条例看函数式编程

不等编程即为不同解决问题之思绪

解决一个问题产生不少思路,比如:

  1. 过程式(C语言):将缓解问题的点子诠释变成几何手续来控制数据。
  2. 面向对象式
    (Java/Ruby):以目标呢骨干单位,定义其一言一行控制该中间状态,通过不同目标中的通力合作解决问题。
  3. 函数式(Lisp):一切都为函数,用贯通的思辨方式定义过程,常用递归。
  4. 组合式:将不同的缓解智结合起来,golang
    经常会面以面向对象与过程式组合起来。

示例: Huffman编码

为此 Lisp 的一个方言 Scheme 来贯彻:

输入 '((A 1) (B 3) (C 2)), A B C 为带动编码字符,1 2 3 为出现次数。
输出 '((b 0) (a 0 1) c 1 1)

概念叶子节点

(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
的同校也许对端的代表方法有点陌生,其实就是用括号表示办法调用,括号里之率先个职务是道名称,后面的是调整用该法的参数。

面的几乎实施代码定义了叶子节点 leaf 及有关函数。

概念树节点
(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)))

平等的道理,定义了用来在组织 Huffman 树中非叶子的节点 tree
及其有关取值函数。

以不变应万变 list 构造方法
(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 的以第一个只取出,让后递归调用 `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
可明白啊将点滴个要素做成为一个 list。
乍一看这所谓“插入”元素的办法有些意想不到,而且没有因此外临时变量。其思路将整插入的经过用递归调用的法意味着:
用过程(函数)代替了临时变量。举了例子:(adjoin-set 3 '(1 2)),执行顺序是:

(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)

好看看在履行序列中,推迟 cons
的实行,用参数求值压栈从而省去了即变量。在 make-leaf-set
中思路为同:不断地于 paris 中取元素,交给 adjoin-set 插入到 list
中。整个编写过程遭到几近用程序流畅地发挥了咱们的解题思路。

Huffman树构造方法

以插入元素这种简易的问题被函数式威力还远远没有反映出,请看下构造
Huffman树 的函数实现:

(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))))))

差一点行代码就以组织 Huffman树 的骨干逻辑表达清楚了:将随 weight 升序 leaves
的先头片个将出来做成一个 tree node,adjoin-set 到剩余的 leaves
中,然后连重复这操作,直到 leaves 中就剩余零星独因素,将马上片个要素最
最终 Huffman树 的左右子树,然后回来。怎么样?一气呵成。

编码

本着 Huffman树 全体历编码的落实吗是概括得起种植考虑的美感:
先行进行左子树遍历,直到找到叶子节点,构造成结果 list
中一个元素,然后回到上亦然交汇递归,进入右子树,不断重复直到遍历完所有节点。

(define (encode tree)
  (define (visit n bits)
    (if (leaf? n)
      ; 找到了一个叶子节点
      (cons (symbol-leaf n) bits)
      ; 用 cons 对 visit 的递归调用
      (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)

详见代码请进
github

ps: 本篇用到有些《计算机程序的组织和分析》代码。强烈建议大家读 MIT
的立即宗公开课。