This is problem 50 in https://wiki.haskell.org/99_questions/46_to_50. The website has more elegant Haskell solutions, but I wanted to get feedback on how the code I wrote on my own below could be improved.
import Data.List data Tree a = Leaf a Int | Internal (Tree a) (Tree a) Int instance (Eq a) => Eq (Tree a) where (Leaf a ac) == (Leaf b bc) = (a == b) && (ac == bc) (Internal a1 a2 ac) == (Internal b1 b2 bc) = (a1 == b1) && (a2 == b2) && (ac == bc) _ == _ = False instance (Eq a) => Ord (Tree a) where a <= b = (freq a) <= (freq b) freq :: Tree a -> Int freq (Leaf _ c) = c freq (Internal _ _ c) = c leafMap :: [(a, Int)] -> [Tree a] leafMap list = map (\(a, count) -> Leaf a count) list extractMinFreq :: (Eq a) => [Tree a] -> (Tree a, [Tree a]) extractMinFreq list = (mf , delete mf list) where mf = minimum list collapseLowest :: (Eq a) => [Tree a] -> [Tree a] collapseLowest list = (collapsePair s1 s2):xs where (s1,y) = extractMinFreq list (s2, xs) = extractMinFreq y treeBuilder :: (Eq a) => [Tree a] -> Tree a treeBuilder list = case len of 0 -> error "Empty" 1 -> list !! 0 _ -> treeBuilder $ collapseLowest list where len = length list collapsePair :: Tree a -> Tree a -> Tree a collapsePair x y = Internal x y $ (freq x) + (freq y) prefixBuilder :: Tree Char -> String -> [(Char, String)] prefixBuilder (Leaf a _) prefix = [(a, prefix)] prefixBuilder (Internal a b _) prefix = (prefixBuilder a $ prefix ++ "0") ++ (prefixBuilder b $ prefix ++ "1") huffman :: [(Char, Int)] -> [(Char, String)] huffman list = prefixBuilder (treeBuilder $ leafMap list) "" main = print $ huffman [('a',45),('b',13),('c',12),('d',16),('e',9),('f',5)]