P50 - 霍夫曼编码
Huffman codes
官方模块：
Problems.P50核心函数：huffman
题目描述
给定字符及其频率，生成最优前缀码（霍夫曼编码）。频率越高的字符编码越短。
函数签名
1huffman :: [(Char, Int)] -> [(Char, String)]
实现
方法一：列表排序构建树
1import Data.List (sortOn)
2
3data HuffmanTree = Leaf Char | Branch HuffmanTree HuffmanTree
4
5huffman :: [(Char, Int)] -> [(Char, String)]
6huffman [] = []
7huffman [(c,_)] = [(c,"0")]
8huffman frequencies = codes (snd (head (build initial)))
9 where
10 initial = sortOn fst [(w, Leaf c) | (c,w) <- frequencies]
11
12 build [tree] = [tree]
13 build ((w,a):(v,b):rest) =
14 build (sortOn fst ((w + v, Branch a b) : rest))
15 build [] = []
16
17codes :: HuffmanTree -> [(Char, String)]
18codes = walk ""
19 where
20 walk prefix (Leaf c) = [(c, prefix)]
21 walk prefix (Branch left right) =
22 walk (prefix ++ "0") left ++ walk (prefix ++ "1") right
反复取出权重最小的两棵树合并，用 sortOn 维护有序列表。
方法二：使用优先队列
1import Data.List (insertBy, sortOn)
2import Data.Ord (comparing)
3
4huffman :: [(Char, Int)] -> [(Char, String)]
5huffman [] = []
6huffman [(c,_)] = [(c,"0")]
7huffman frequencies = codes (buildQueue initial)
8 where
9 initial = sortOn fst [(w, Leaf c) | (c,w) <- frequencies]
10
11 buildQueue [tree] = snd tree
12 buildQueue ((w1,a):(w2,b):rest) =
13 buildQueue (insertBy (comparing fst) (w1 + w2, Branch a b) rest)
insertBy (comparing fst) 只比较权重，不要求 HuffmanTree 具有 Ord 实例；每次合并后把新树插回正确位置。
方法三：codes 用差分字符串优化
1codesShowS :: HuffmanTree -> [(Char, String)]
2codesShowS tree = [(c, build "") | (c, build) <- walk id tree]
3 where
4 walk prefix (Leaf c) = [(c, prefix)]
5 walk prefix (Branch left right) =
6 walk (prefix . ('0' :)) left
7 ++ walk (prefix . ('1' :)) right
ShowS 就是 String -> String。追加一位编码变成函数组合，只有到叶子时才把构造器应用到空串，避免在每层复制前缀。
测试
1>>> let table = huffman [('a',45),('b',13),('c',12),('d',16),('e',9),('f',5)]
2>>> all (\(_,code) -> not (null code)) table
3True
4>>> huffman [('a',2),('b',1)]
5[('b',"0"),('a',"1")]
6>>> codesShowS (Branch (Leaf 'a') (Leaf 'b'))
7[('a',"0"),('b',"1")]