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)