[Haskell-cafe] Huffman Codes in Haskell

[John Lato]

Thanks for providing this.  I think this is pretty close to one of the
solutions he presents in the paper.

It seems that part of what prompted Okasaki to investigate this
further was trying to solve the problem in a strict language (ML)
after he saw a solution which relies upon laziness.  What I think is
especially interesting about that is AFAICT his proposed solution
would work with an infinite tree, assuming the language supports lazy
data structures.

On Fri, Jun 25, 2010 at 11:03 AM, Thomas Horstmeyer
<horstmey at mathematik.uni-marburg.de> wrote:
>
>> How would you implement bfnum?  (If you've already read the paper,
>> what was your first answer?)
>>
> Actually, my first thought was "Just traverse the tree twice." Then it
> dawned on me, that the tree could be of infinite size and I settled for the
> following solution:
>
> bfsn :: Tree a -> Tree Int
> bfsn E = E
> bfsn t = f [t] [] 0
>  where
>    f :: [Tree a] -> [Tree a] -> Int -> Tree Int
>    f (T _ E E : xs) ys n = T n E E
>    f (T _ t1 E : xs) ys n = T n (f (t1:children xs) (children ys) (n +
> length xs + length ys + 1)) E
>    f (T _ E t2 : xs) ys n = T n E (f (t2:children xs) (children ys) (n +
> length xs + length ys + 1))
>    f (T _ t1 t2 : xs) ys n = T n t1' t2'
>      where
>        t1' = f (t1:t2:children xs) (children ys) m
>        t2' = f (t2:children  xs) (children ys ++ children [t1]) (m+1)
>        m = length xs + length ys + n + 1
>
> children :: [Tree a] -> [Tree a]
> children  [] = []
> children (E:xs) = children xs
> children (T _ E E:xs) = children xs
> children (T _ E t2:xs) = t2:children xs
> children (T _ t1 E:xs) = t1:children xs
> children (T _ t1 t2:xs) = t1:t2:children xs
>
> One could perhaps rewrite it into something more elegant (less cases for the
> f-function, write children as a map), but you wanted the first answer.
> I am going to have a look at the paper now...
>
> Thomas
>
>