# Problem 50a - Huffman Encoding

Huffman coding uses variable bit length codes to efficiently encode data by giving the frequently found values short codes and rarely used values longer codes. The first step in Huffman encoding is to determine the frequency of every value in the input data.

## Example

``````freqs [1, 20, 20, 3, 3, 3, 3] == [(1, 1), (2, 20), (4, 3)]
``````

## Unit Test

``````import Html
import List
import String

freqs : List comparable -> List ( Int, comparable )
freqs list =
[]

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

test : Bool
test =
List.all ((==) True)
[ freqs [] == []
, sortFreqs (freqs [ 20, 3, 20, 3, 1, 3, 3 ]) == [ ( 1, 1 ), ( 2, 20 ), ( 4, 3 ) ]
, sortFreqs (freqs [ 20, 3, 20, 3, 1, 3, 3 ]) == [ ( 1, 1 ), ( 2, 20 ), ( 4, 3 ) ]
, sortFreqs (freqs [ 3, 3, -20, 1, 3, 3, -20 ]) == [ ( 1, 1 ), ( 2, -20 ), ( 4, 3 ) ]
, (List.head <| List.reverse <| sortFreqs <| freqs <| toChars "hello world") == Just ( 3, 'l' )
, sumFreqs freqs (toChars "hello world") == True
, sumFreqs freqs (toChars "Now isthetimeforallgoodmentocometothe...") == True
, sumFreqs freqs (toChars "Now is the time for all good men to come to the...") == True
, sumFreqs freqs (toChars "El pingüino frío añoró") == True
, sumFreqs freqs (toChars "Да, но фальшивый экземпляр!") == True
, sumFreqs freqs (toChars "ἄγγελον ἀθανάτων ἐριούνιον, ὃν τέκε Μαῖα") == True
]

sumFreqs : (List a -> List ( Int, a )) -> List a -> Bool
sumFreqs f list =
List.sum (List.map fst (f list)) == List.length list

sortFreqs : List ( Int, a ) -> List ( Int, a )
sortFreqs list =
List.sortBy (\( l, v ) -> l) list

toChars : String -> List Char
toChars s =
case String.uncons s of
Nothing ->
[]

Just ( c, cs ) ->
c :: toChars cs
``````

# Hints

1. Look at Problem 9 and Problem 10. Can you use or modify those solutions to this problem? Note we are assuming the type of the input list will be a `comparable`.