1

我是 Haskell 的新手，我正在尝试创建一棵 Huffman 树，但直到最后我都无法弄清楚。

我对树的定义如下所示：data HuffTree = Node Int HuffTree HuffTree | Leaf (Int, Char)

到目前为止，我有一个函数insTree :: HuffTree -> HuffTree -> HuffTree可以在树中插入一个节点及其子树并返回新树。一个函数makePair :: HuffTree -> HuffTree -> HuffTree，它采用两棵树并生成一棵新树，将原始两棵树作为子树，并将前两棵树中的值的总和作为值。value :: HuffTree -> Int以及一个从每个节点返回值的函数。

我的问题是makeHuffTree :: [(Int, Char)] -> HuffTree看起来像这样的函数：

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

我知道这是这个功能的问题，但我不知道如何处理它。我得到的错误是这样的：

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

你能提示如何解决这个问题吗？

4

1 回答 1

7

的结果类型是什么merge？

如果是HuffTree，那么这merge [t] = [t]条线是荒谬的。如果不是，那么这makeHuffTree lst = merge leafList条线是荒谬的。

无论哪种方式，这条线merge (t1 : t2 : tree) = insTree (makePair t1 t2) tree都是荒谬的，因为tree它是一个列表，并且insTree应该采用一个HuffTree，而不是一个列表。

我不熟悉霍夫曼树构建算法。但我认为：

  • merge [] = []这里显然不需要，因为没有对应于空列表的有效树。
  • merge [t]应该返回t。我不能确定，但​​我只是按照类型。
  • merge (t1 : t2 : tree)应该返回insTree (makePair t1 t2) (merge tree)。我再次关注类型。如果您对此感到困惑，请记住在 pattern 中(a:b:cs)，只有aandb是列表的元素；cs是列表的其余部分，这只是另一个列表。

我的观点是：始终遵循类型。你应该能够将手指指向任何表情并说“啊哈，你是 T 型！”。然后你可以将你的手指指向接受该表达式的函数并指责说：“见鬼，你不能有这种类型的参数！”（顺便说一句，编译器通常很乐意借给你它的一个长手指，就像它在有用的错误消息中所做的那样）。然后你会想“我有什么可以从那个值中创建一个需要类型的值？”，应用正确的函数来修复有问题的参数，差不多就是这样。哦，如果你没有任何合适的函数，你写一个。

于 2013-04-07T23:01:06.863 回答