CPSC 425 Spring 2006
Huffman Coding in ML

Recall that Huffman coding is a compression technique that uses a variable-length code constructed from the frequency counts of the objects being represented. In this program you will use ML to build a Huffman tree for a given list of (item, frequency) pairs.

Your top-level function huffman : ('a * int) list -> 'a Hufftree should take a list of (item,frequency) tuples and return a Huffman tree of items built using those tuples. Some things to think about:

The ML interpreter does not display the tree nicely, so you can use my pretty-printer to display your tree after you build it. This code works with my Hufftree datatype; you may need to modify it to work with yours.

Note that your huffman function takes tuples holding any kind of element, but the pretty-printer assumes that it holds characters. Keep your huffman function general, but I will limit large test cases to characters.