CODEWITHSUNDEEP
haskellhuffman-code
Gloria95
Gloria95

Reputation: 139

Huffman code in Haskell (Make Tree)

so this is kinda a long question about Huffman Tress. I am trying to make a Tree and a code Table.

Here are my Types 

module Types where

type Occurence  = (Value, Number)
type Occurences = [Occurence]
type Number     = Int
type Value      = Char
type Code       = [Directions]
type CodeTable  = [(Value, Code)]


data Directions = L | R deriving (Eq, Ord, Show)


data HTree      = Leaf {frequency :: Number, character:: Value} |
                  Node {frequency:: Number, 
                        leftChild:: HTree,
                        rightChild:: HTree} deriving Show


makeLeaf :: Occurence -> HTree
makeLeaf (c,n) = Leaf n c

Here is my attempt to an Make a Tree function 

module MakeTree(makeTree, treeFromTable) where
import Types

makeTree :: Occurences -> HTree
makeTree = makeCodes . toTreeList

toTreeList :: Occurences -> [HTree]
toTreeList = map (uncurry Leaf)

h :: [HTree] -> [HTree]
h (t1:t2:ts) = insertTree (join t1 t2) ts

makeCodes :: [HTree] -> HTree
makeCodes [t] = t
makeCodes ts = makeCodes (h ts)

join :: HTree -> HTree -> HTree
join t1 t2 = Node (freq1+freq2) t1 t2
    where
      freq1 = v t1
      freq2 = v t2

v :: HTree -> Int
v (Leaf _ n ) = n
v (Node n _ _) = n

insertTree :: HTree -> [HTree] -> [HTree]
insertTree t [] = [t]
insertTree t (t1:ts) 
     | v t < v t1 = t:t1:ts
     | otherwise = t1 : insertTree t ts

And here is my attempt to make a CodeTable 

constructTable :: HTree -> CodeTable
constructTable = convert []
      where
      convert :: Code -> HTree -> CodeTable
      convert hc (Leaf c n) = [(c, hc)]
      convert hc (Node n tl tr) = (convert (hc++[L]) tl) ++ (convert (hc++[R]) tr)

Error for Code Table 

CodeTable.hs:14:33: error:
    • Couldn't match type ‘Int’ with ‘Char’
      Expected type: Value
        Actual type: Number
    • In the expression: c
      In the expression: (c, hc)
      In the expression: [(c, hc)]
   |
14 |       convert hc (Leaf c n) = [(c, hc)]

Do you spot any mistakes or could you tell me why neither of this codes is working for me?

Upvotes: 1

Views: 422

Answers (1)

Igor Drozdov
Igor Drozdov

Reputation: 15045

Expected type: Value
Actual type: Number

It's quite clear from the error message, what's wrong with the following expression:

convert hc (Leaf c n) = [(c, hc)]

Since HTree defined as:

data HTree      = Leaf {frequency :: Number, character:: Value} |
                  Node {frequency:: Number, 
                        leftChild:: HTree,
                        rightChild:: HTree} deriving Show

Leaf accepts frequency (Number) as the first argument and character (Value) as the second. Thus, we need to just swap the arguments in the expression:

convert hc (Leaf n c) = [(c, hc)]

Also in the definition of v function:

v (Leaf n _ ) = n

In the definition of type Occurence:

type Occurence  = (Number, Value)

and in the makeLeaf as well:

makeLeaf (n, c) = Leaf n c

After these steps your code should compile successfully

Upvotes: 2

Related Questions