From 13c0046a6dbd41b15358e76856922144ac76e768 Mon Sep 17 00:00:00 2001 From: Joe Zhao Date: Sat, 4 Apr 2015 17:38:20 +0800 Subject: +46 +47 +48 +49 +50 --- H50.hs | 21 +++++++++++++++++++++ 1 file changed, 21 insertions(+) create mode 100644 H50.hs (limited to 'H50.hs') diff --git a/H50.hs b/H50.hs new file mode 100644 index 0000000..c422775 --- /dev/null +++ b/H50.hs @@ -0,0 +1,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 -- cgit v1.2.3-70-g09d2