1 files changed, 21 insertions, 0 deletions
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