[Haskell-cafe] Huffman Codes in Haskell

[John Lato]

On Wed, Jun 23, 2010 at 4:35 PM, Daniel Lyons <fusion at storytotell.org> wrote:
> On Wed, Jun 23, 2010 at 03:41:29PM +0100, John Lato wrote:
>> How would you implement bfnum?  (If you've already read the paper,
>> what was your first answer?)
>
> This was my first answer, and it is wrong, but I thought it was
> slightly clever, so here it is:
>
> bfnum :: Tree a -> Tree Int
> bfnum tree = bfnum' tree 1
>  where
>     bfnum' E _ = E
>     bfnum' (T _ l r) i = T i (bfnum' l (i*2)) (bfnum' r ((i*2)+1))
>
> If you have an incomplete tree, it will skip though.
>
> I didn't realize it was wrong until I finished reading the paper
> though, so I don't have a better solution that actually works.
>

That was my first try too.  If this answer did work, I don't think the
question would be interesting.

John