makeTree.lhs
Turn a frequency table into a Huffman tree
(c) Simon Thompson, 1995.
> module MakeTree ( makeTree ) where
> import Types ( Tree(Leaf,Node), Bit(L,R), HCode, Table )
Convert the trees to a list, then amalgamate into a single
tree.
> makeTree :: [ (Char,Int) ] -> Tree
> makeTree = makeCodes . toTreeList
Huffman codes are created bottom up: look for the least
two frequent letters, make these a new "isAlpha" (i.e. tree)
and repeat until one tree formed.
The function toTreeList makes the initial data structure.
> toTreeList :: [ (Char,Int) ] -> [ Tree ]
> toTreeList = map (uncurry Leaf)
The value of a tree.
> value :: Tree -> Int
> value (Leaf _ n) = n
> value (Node n _ _) = n
Pair two trees.
> pair :: Tree -> Tree -> Tree
> pair t1 t2 = Node (v1+v2) t1 t2
> where
> v1 = value t1
> v2 = value t2
Insert a tree in a list of trees sorted by ascending value.
> insTree :: Tree -> [Tree] -> [Tree]
> insTree t [] = [t]
> insTree t (t1:ts)
> | (value t <= value t1) = t:t1:ts
> | otherwise = t1 : insTree t ts
Amalgamate the front two elements of the list of trees.
> amalgamate :: [ Tree ] -> [ Tree ]
> amalgamate ( t1 : t2 : ts )
> = insTree (pair t1 t2) ts
Make codes: amalgamate the whole list.
> makeCodes :: [Tree] -> Tree
> makeCodes [t] = t
> makeCodes ts = makeCodes (amalgamate ts)