[Haskell-cafe] Huffman Codes in Haskell

Lyndon Maydwell maydwell at gmail.com
Wed Jun 23 11:24:27 EDT 2010

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


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

More information about the Haskell-Cafe mailing list