Huffman Tree in Haskell

Question

I am really new in Haskell and I am trying to create a Huffman Tree and I can't figure it out how until the end.

My definition for the tree looks like this: data HuffTree = Node Int HuffTree HuffTree | Leaf (Int, Char)

So far, I have a function insTree :: HuffTree -> HuffTree -> HuffTree that inserts a Node with it's subtrees in a tree and returns the new tree. A function makePair :: HuffTree -> HuffTree -> HuffTree that takes two trees and makes a new one having as subtrees the original two trees and as value the sum of the values in the first two trees. And a function value :: HuffTree -> Int that returns the value from each node.

My problem is with the function makeHuffTree :: [(Int, Char)] -> HuffTree which looks like this:

makeHuffTree :: [(Int, Char)] -> HuffTree
makeHuffTree lst = merge leafList
    where
        leafList = map (\ ((x,c)) -> Leaf (x,c)) lst
        merge [] = []
        merge [t] = [t]
        merge (t1 : t2 : tree) = insTree (makePair t1 t2) tree

I know it is a problem with this function but I don't know how to deal with it. The error that I get is this:

Couldn't match expected type `[a0]' with actual type `HuffTree'
In the return type of a call of `insTree'
In the expression: insTree (makePair t1 t2) tree
In an equation for `merge':
    merge (t1 : t2 : tree) = insTree (makePair t1 t2) tree

Can you give a hint on how to solve this problem?

Artyom Artyom · Accepted Answer · 2013-04-07T23:01:06

What is the type of merge’s result?

If it’s HuffTree, then the merge [t] = [t] line is absurd. If it isn’t, then the makeHuffTree lst = merge leafList line is absurd.

The line merge (t1 : t2 : tree) = insTree (makePair t1 t2) tree is absurd either way because tree is a list and insTree is supposed to take a HuffTree, not a list.

I am not familiar with the Huffman tree building algorithm. But I think that:

merge [] = [] is clearly not needed here, as there isn’t a valid tree that corresponds to an empty list.
merge [t] should return t. I can’t be sure about that, but I am just following the types.
merge (t1 : t2 : tree) should return insTree (makePair t1 t2) (merge tree). I’m following the types again. In case you’re confused about that, remember that in pattern (a:b:cs), only a and b are elements of the list; cs is the remainder of the list, which is just another list.

My point is: always follow the types. You should be able to point your finger at any expression and say “Aha, you’re of type T!”. And then you can point your finger on the function which takes that expression and say accusingly “What the heck, you can’t have an argument of this type!“ (by the by, the compiler is usually happy to lend you one of its long fingers, just as it does in its helpful error message). And then you think “What do I have at my disposal to make a value of needed type from that value?”, apply just the right function to fix the offending argument, and that’s pretty much it. Oh, and if you don’t have any suitable function, you write one.

Huffman Tree in Haskell

1 Answers