Problem 50b - Huffman Encoding

Huffman coding uses variable bit length codes to efficiently encode data. In Problem 50a we find the frequencies of each value of our input data. Now use that to build the Huffman codes. See the steps to build a Huffman code from the frequency data here.

You'll need a binary tree to build the codes. You should complete Problems 54 through 61 before attempting this problem.

Example

huffman [('a',45),('b',13),('c',12),('d',16),('e',9),('f',5)] == 
[('a',"0"),('b',"101"),('c',"100"),('d',"111"),('e',"1101"),('f',"1100")]

Unit Test

import Html
import List
import Set
import String


type alias Freq = (Char, Int)


huffman : List Freq -> List (Char, String)
huffman list =
    -- your implementation goes here
    []

main =
    Html.text
        (if (test) then
            "Your implementation passed all tests."
         else
            "Your implementation failed at least one test."
        )


test : Bool
test =
    let 
        codes = huffman [('a',45),('b',13),('c',12),('d',16),('e',9),('f',5)] 
    in
        List.all ((==) True)
          [ assertCodeLength codes 'a' 1
          , assertCodeLength codes 'b' 3
          , assertCodeLength codes 'c' 3
          , assertCodeLength codes 'd' 3
          , assertCodeLength codes 'e' 4
          , assertCodeLength codes 'f' 4
          , List.length codes == 6
          , 6 == List.length (Set.toList (Set.fromList codes))
          ]


assertCodeLength : List (Char, String) -> Char -> Int -> Bool
assertCodeLength codes c n = 
    case codes of
        [] -> False

        (ch, s) :: cs ->
            if ch == c then
                n == String.length s
            else
                assertCodeLength cs c n

Solutions

Solutions