1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
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
|
