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 =
-- your implementation here
[]
main =
Html.text
(if (test) then
"Your implementation passed all tests."
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
- 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
.