以 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
的那门公开课。