Re: [Haskell-cafe] Huffman Codes in Haskell
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
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
On Wed, Jun 23, 2010 at 03:41:29PM +0100, John Lato wrote:
How would you implement bfnum? (If you've already read the paper, what was your first answer?)
This was my first answer, and it is wrong, but I thought it was slightly clever, so here it is: bfnum :: Tree a -> Tree Int bfnum tree = bfnum' tree 1 where bfnum' E _ = E bfnum' (T _ l r) i = T i (bfnum' l (i*2)) (bfnum' r ((i*2)+1)) If you have an incomplete tree, it will skip though. I didn't realize it was wrong until I finished reading the paper though, so I don't have a better solution that actually works. -- Daniel
On Wed, Jun 23, 2010 at 4:35 PM, Daniel Lyons
On Wed, Jun 23, 2010 at 03:41:29PM +0100, John Lato wrote:
How would you implement bfnum? (If you've already read the paper, what was your first answer?)
This was my first answer, and it is wrong, but I thought it was slightly clever, so here it is:
bfnum :: Tree a -> Tree Int bfnum tree = bfnum' tree 1 where bfnum' E _ = E bfnum' (T _ l r) i = T i (bfnum' l (i*2)) (bfnum' r ((i*2)+1))
If you have an incomplete tree, it will skip though.
I didn't realize it was wrong until I finished reading the paper though, so I don't have a better solution that actually works.
That was my first try too. If this answer did work, I don't think the question would be interesting. John
On Wed, Jun 23, 2010 at 11:50 AM, Daniel Lyons
On Wed, Jun 23, 2010 at 05:41:17PM +0100, John Lato wrote:
If this answer did work, I don't think the question would be interesting.
"We don't have to be mean." - Buckaroo Banzai.
I certainly didn't want to upset anyone, and I'm sorry if I did. After all, I did say that was my first attempt too. I just meant that the reason the given solution doesn't work is exactly what leads to a more involved approach. John
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: http://community.haskell.org/~claus/GHood/ 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. Claus
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
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
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
John Lato wrote:
How would you implement bfnum? (If you've already read the paper, what was your first answer?)
My first idea was something similar to what is described in appendix A. However, after reading the paper, I wrote the following code: data Tree a = E | T a (Tree a) (Tree a) deriving Show bfnum :: Tree a -> Tree Int bfnum = num . bf bf :: Tree a -> [Tree a] bf root = output where children = go 1 output output = root : children go 0 _ = [] go n (E : rest) = go (pred n) rest go n (T _ a b : rest) = a : b : go (succ n) rest num :: [Tree a] -> Tree Int num input = root where root : children = go 1 input children go k (E : input) children = E : go k input children go k (T _ _ _ : input) ~(a : ~(b : children)) = T k a b : go (succ k) input children Maybe one could try to fuse bf and num. Tillmann
participants (6)
-
Claus Reinke -
Daniel Lyons -
John Lato -
Lyndon Maydwell -
Thomas Horstmeyer -
Tillmann Rendel