[Haskell-cafe] Huffman Codes in Haskell

[Thomas Horstmeyer]

> How would you implement bfnum?  (If you've already read the paper,
> what was your first answer?)
> 
Actually, my first thought was "Just traverse the tree twice." Then it 
dawned on me, that the tree could be of infinite size and I settled for 
the following solution:

bfsn :: Tree a -> Tree Int
bfsn E = E
bfsn t = f [t] [] 0
   where
     f :: [Tree a] -> [Tree a] -> Int -> Tree Int
     f (T _ E E : xs) ys n = T n E E
     f (T _ t1 E : xs) ys n = T n (f (t1:children xs) (children ys) (n + 
length xs + length ys + 1)) E
     f (T _ E t2 : xs) ys n = T n E (f (t2:children xs) (children ys) (n 
+ length xs + length ys + 1))
     f (T _ t1 t2 : xs) ys n = T n t1' t2'
       where
         t1' = f (t1:t2:children xs) (children ys) m
         t2' = f (t2:children  xs) (children ys ++ children [t1]) (m+1)
         m = length xs + length ys + n + 1

children :: [Tree a] -> [Tree a]
children  [] = []
children (E:xs) = children xs
children (T _ E E:xs) = children xs
children (T _ E t2:xs) = t2:children xs
children (T _ t1 E:xs) = t1:children xs
children (T _ t1 t2:xs) = t1:t2:children xs

One could perhaps rewrite it into something more elegant (less cases for 
the f-function, write children as a map), but you wanted the first answer.
I am going to have a look at the paper now...

Thomas