Module Huffman

module Huffman: sig .. end
Module for performing Huffman coding.

This interface is agnostic about the type of characters that are used. The most typical use is to build char encodings from char lists, but other types are possible.


type bit = 
| Zero
| One
type 'a hufftree = 
| Leaf of 'a
| Node of 'a hufftree * 'a hufftree
type 'a encoding = 
| Empty
| Tree of 'a hufftree
val build_tree : 'a list -> 'a encoding
given a list of characters, build an optimal Huffman tree for encoding that list. If the input list is empty, then Empty should be returned; if the input list contains only repetitions of a single character c, then Singleton c should be returned.
val encode : 'a hufftree -> 'a list -> bit list
encode tree chars produces the bit list representing chars using the Huffman tree tree.

The characters in chars must all be represented in tree; if passed a malformed input, encode should raise an exception.

val decode : 'a hufftree -> bit list -> 'a list
decode tree bits decodes bits using the encoding scheme specified for the encode function.

It should raise an exception if bits is not valid according to tree.