# Creating a code table for a Huffman tree

Our ultimate goal is to have a list in which each element gives the route on a tree to a particular letter. E.g.

('t',[L])

means go left from the top to code for a t

Similarly:

('a',[R,L])

means go right then left from the top to code for an a

So, we want to be able to do this:

*Main> codeTable (codes "tab")

[('t',[L]),('a',[R,L]),('b',[R,R])]

and the question is how?

Well, step one is to ask what granularity we need to take the input data on. And the answer is: we can take the input data one at a time.

Questions two and three are: what should our final and transition actions look like? Well, let's start with the final action. The final action for any particular leaf is going to yield something like this:

('a',[R,L])

we can restate that as: the final action as we move through a tree is to take a leaf and return the character there as well as the entire path to it.

Having stated the final action, we see what our transition action must be, *we need to build up the entire path to that element as we make the transitions*

The final code from SJT's implementation shows these final and transition actions as the solution to our problem:

```
```-- Making a table from a Huffman tree.

codeTable :: Tree -> Table

codeTable = convert []

-- Auxiliary function used in conversion to a table. The first argument is

-- the HCode which codes the path in the tree to the current Node, and so

-- codeTable is initialised with an empty such sequence.

convert :: HCode -> Tree -> Table

-- Action Final

convert cd (Leaf c n) = [(c,cd)]

`-- Action Transition`

convert cd (Node n t1 t2)

= (convert (cd++[L]) t1) ++ (convert (cd++[R]) t2)

- metaperl's blog
- Login to post comments