Haskell 中的霍夫曼代码（制作树）

Question

所以这是一个关于 Huffman Tress 的长问题。我正在尝试制作一棵树和一个代码 Table。

这是我的类型

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

这是我尝试制作一棵树的功能

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

这是我尝试制作的代码Table

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)

代码错误 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)]

你有没有发现任何错误，或者你能告诉我为什么这两个代码都不适合我吗？

Answer 1

Expected type: Value
Actual type: Number

从报错信息中可以看出，下面的表达式有什么问题：

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

因为 HTree 定义为：

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

Leaf 接受 frequency（数字）作为第一个参数，character（值）作为第二个参数。因此，我们只需要交换表达式中的参数：

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

同样在v函数的定义中：

v (Leaf n _ ) = n

在type Occurence的定义中：

type Occurence  = (Number, Value)

并且在 makeLeaf 中还有：

makeLeaf (n, c) = Leaf n c

完成这些步骤后，您的代码应该可以成功编译

Haskell 中的霍夫曼代码（制作树）

Huffman code in Haskell (Make Tree)

haskell

huffman-code