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