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

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.

Solutions

Solutions