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)

huffman.hs

-- 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