import Data.List
import Data.Ord (comparing)
import Control.Arrow

data HTree a = Leaf a | Branch (HTree a) (HTree a)
    deriving Show

huffman :: [(a, Int)] -> [(a,String)]

huffman xs = serialize "" $ huffcon $ sortBy (comparing fst) $ map (\(x,y) -> (y, Leaf x)) xs
huffcon [(_,a)] = a
huffcon ((v1,t1):(v2,t2):rst) = huffcon $ sortBy (comparing fst) $ (v1+v2,Branch t1 t2):rst

serialize s (Leaf l) = [(l,s)]
serialize s (Branch t1 t2) = (serialize ('0':s) t1) ++ (serialize ('1':s) t2)

huffman' :: [(a,Int)] -> [(a,String)]
huffman' xs = huffcon' $ sortBy (comparing fst) [(y,[(x,"")]) |(x,y) <- xs]
huffcon' [(_,a)] = a
huffcon' ((v1,l1):(v2,l2):rst) = huffcon' $ sortBy (comparing fst) $ 
    (v1+v2,(map (fst &&& ('0':).snd) l1)++(map (fst &&& ('1':).snd) l2)):rst