
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
From: Max Rabkin
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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe