Skip to content

Instantly share code, notes, and snippets.

# umairsd/huffman.hs Created Oct 7, 2015

Huffman Codes - Creates a Huffman Tree from passed in array of (key, probability) pairs, and then generates all the codes by iterating over the tree (P50 in 99 Haskell Problems)
 -- Problem 50, 99 Haskell Problems (https://wiki.haskell.org/99_questions/46_to_50) {-# OPTIONS_GHC -Wall #-} import Data.Ord(comparing) import Data.List(sortBy) huffman :: [(Char, Int)] -> [(Char, String)] huffman = sortBy (comparing fst) . (serializeHTree . buildHTree . createHTreeList) -- Data type to represent a Huffman tree data HTree a = Leaf a Int | HNode Int (HTree a) (HTree a) deriving (Show) -- Creates a list of Leaf nodes, corresponding to each element of the input data createHTreeList :: [(Char, Int)] -> [HTree Char] createHTreeList = map (\(c,n) -> Leaf c n) . sortBy (comparing snd) -- Creates a Huffman Tree from a list of HTree nodes buildHTree :: [HTree a] -> HTree a buildHTree [] = error "Cannot create a Huffman tree from an empty list" buildHTree [x] = x buildHTree (x:y:xs) = buildHTree \$ sortBy (compareHTrees) \$ (HNode (intForHTree x + intForHTree y) x y) : xs -- Compares two HTrees nodes based on the integer frequency compareHTrees :: HTree a -> HTree a -> Ordering compareHTrees lTree rTree = compare (intForHTree lTree) (intForHTree rTree) -- Finds all the Huffman codes within the given tree serializeHTree :: HTree a -> [(a, String)] serializeHTree tree = serializeHelper tree "" where serializeHelper (Leaf c _) path = [(c, path)] serializeHelper (HNode _ lT rT) path = serializeHelper lT (path ++ "0") ++ serializeHelper rT (path ++ "1") -- Helper function to extract the integer (frequency) of the given HTree intForHTree :: HTree a -> Int intForHTree (Leaf _ n) = n intForHTree (HNode n _ _) = n
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.