Skip to content

Instantly share code, notes, and snippets.

@umairsd umairsd/huffman.hs
Created Oct 7, 2015

Embed
What would you like to do?
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.