[Haskell-cafe] Huffman Codes in Haskell

Claus Reinke claus.reinke at talk21.com
Wed Jun 23 17:56:43 EDT 2010

>> 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.  
> How would you implement bfnum?  (If you've already read the paper,
> what was your first answer?)

That paper is indeed a useful read, provided one does
try to solve the puzzle as well as carefully check any
imagined solutions. 

I happened on it when I was working on the first GHood 
prototype, so my struggles happen to be documented 
(together with the popular foldl vs foldl' strictness) in 
the GHood paper and online examples:


The observation tool and problem turned out to be well
suited for each other: by observing both the input and
the result tree, one can see how traversal of the result
tree drives evaluation of the input tree (or not, if one
gets the strictness wrong;-).

You might find this useful when testing your solutions
or trying to get an intuition about dynamic strictness.


More information about the Haskell-Cafe mailing list