[Haskell-cafe] Huffman Codes in Haskell

[Lyndon Maydwell]

I made (presumably) inefficient huffman algorithm not too long ago:

http://www.hpaste.org/fastcgi/hpaste.fcgi/view?id=26484#a26484

I guess it doesn't normally need to be terribly efficient as the
result can be stored in a map of some sort.

On Wed, Jun 23, 2010 at 10:41 PM, John Lato <jwlato at gmail.com> wrote:
>> 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
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>