# CSCE 314: Programming Languages

# Homework —Supplement

## Objective

In this assignment you have additional data types to manipulate. This is good practice to improve your Haskell skills.

## Instructions

- Since there can be many different implementations for these questions, the output can differ substantially. Thus, we don't provide test functions, so you'll have to use your judgement by referring to the examples we give. (This is good practice, in general, where you need to write code and convince yourself it works by posing your own test cases.)

## Huffman Coding

A Huffman code is a type of optimal prefix code used for lossless data compression. The process of finding such a code is called Huffman coding, which derives a variable-length code table for a set of source symbols according to the frequency of occurrence for symbol. More common symbols are represented using fewer bits than less common symbols, which permits (as you might imagine) compression.

Given a set of source symbols, Huffman coding works as follows:

- Calculate the weight (frequency of occurrence) of each symbol and sort these (symbol, weight) pairs by weight in ascending order.

- Create a binary tree with these pairs. The process begins with leaves
containing the weight of the symbols they represent. Then a new node, whose
children are the two nodes with smallest weights is created, so that the new
node's weight is equal to the sum of its children's weights. With the previous
two nodes merged into one node, the procedure is repeated until only one node
remains. That node is the root of the Huffman tree.

- With your Huffman tree constructed, we can get the variable-length code table by traversing all the paths from the root to each of the leaves. As a common convention, bit '0'
represents following the left child and bit '1' represents following the right child.

The following illustration gives an example of Huffman coding process just described.

Implement a Haskell function that given a set of source symbols, outputs the Huffman code.

huffmanCode :: String -> [(Char,String)]

Here is an example of the function being called:

*Main> huffmanCode "abfabcaecedba" [('a',"11"),('b',"01"),('c',"100"),('d',"001"),('e',"101"),('f',"000")]

**Note:** Refer to the "freqs" function on Pg. 54 of the textbook
(Hutton, Programming in Haskell, 2nd edition) to implement a Haskell function to
count the frequency of each symbol. Try to use the following data type to
construct
the Huffman tree.

data Tree a b = Branch b (Tree a b) (Tree a b) | Leaf a type HuffmanTree = Tree (Char,Int) Int

## Trie

Trie, a.k.a. "digital tree", "radix tree" or "prefix tree", is a kind of search tree—an ordered tree data structure used to store a dynamic set or associative array where the keys are usually strings. (It is usually pronounced "try", not "tree".) Unlike a binary search tree, no node in a trie stores the key associated with that node; instead, its position in the tree defines the key with which it is associated. For all the descendants of a node, they share a common prefix string associated with that node. The root is associated with an empty string. Values are not necessarily associated with every node. Rather, only leaves and some inner nodes that correspond to keys of interest store values.

The following graph (from Wikipedia's page on the Trie) represents an example of trie, which stores keys "A","to", "tea", "ted", "ten", "i", "in", and "inn" with corresponding values 15, 7, 3, 4, 12, 11, 5 and 9.

Consider the following data type.

import Data.Map data Trie a = Trie { value :: Maybe a, children :: Data.Map Char (Trie a)} type IntTrie = Trie Int

Implement a Haskell function that takes a list as input, outputs the trie storing the list.

listToTrie :: [(String, Int)] -> IntTrie

Implement another Haskell function that takes a trie as input, outputs the corresponding list.

trieToList :: IntTrie -> [(String, Int)]

Here is an example of the function being called:

*Main> listToTrie [("i",5),("a",3),("an",2)] Trie {value = Nothing, children = fromList [('i',Trie {value = Just 5, children = fromList []}),('a',Trie {value = Just 3, children = fromList [('n',Trie {value = Just 2, children = fromList []})]})]}

### Acknowledgements

We (Mengyuan Chao) made use of the following information in constructing these questions.
Huffman coding: https://en.wikipedia.org/wiki/Huffman_coding

Trie: https://en.wikipedia.org/wiki/Trie

### Check your answers

See the note above in the instructions—if you come up with an especially trying (or trie-ing) input, share it on Piazza!