[Haskell-cafe] Huffman Codes in Haskell

[John Lato]

> From: Max Rabkin <max.rabkin at gmail.com>
>
> This seems like an example of list-chauvinism -- what Chris Okasaki
> calls a communal blind spot of the FP community in Breadth-First
> Numbering: Lessons from a Small Exercise in Algorithm Design --
> http://www.eecs.usma.edu/webs/people/okasaki/icfp00.ps
>

Thanks for sharing; this was an interesting (and short!) read.

I would like to see other Haskeller's responses to this problem.  I'll
restate it here hoping to get replies from those who haven't read the
paper yet:

Assume you have a type of labeled binary trees:

data Tree a = E | T a (Tree a) (Tree a)

and you are to produce a function

bfnum :: Tree a -> Tree Int

that performs a breadth-first numbering of the tree (starting with 1),
preserving the tree structure.

How would you implement bfnum?  (If you've already read the paper,
what was your first answer?)

For the record, my solution doesn't rely on any other data structures
or laziness AFAICT, and I think it would fit into the Level-Oriented
category of solutions.

John