Haskman树在Haskell

Question

我是Haskell的新手,我正在尝试创建一个霍夫曼树,直到最后我都无法弄明白.

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

到目前为止,我有一个函数insTree :: HuffTree -> HuffTree -> HuffTree,在树中插入带有子树的Node并返回新树.一个函数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

你能否提一下如何解决这个问题？

Answer 1

结果是什么类型的merge？

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

这条线merge (t1 : t2 : tree) = insTree (makePair t1 t2) tree是荒谬的,因为它tree是一个列表,insTree并且应该采用a HuffTree而不是列表.

我不熟悉霍夫曼树构建算法.但我认为:

• merge [] = [] 这里显然不需要,因为没有对应于空列表的有效树.
• merge [t]应该回来t.我无法确定这一点,但我只是遵循这些类型.
• merge (t1 : t2 : tree)应该回来insTree (makePair t1 t2) (merge tree).我再次关注这些类型.如果你对此感到困惑,请记住在模式中(a:b:cs),只有a并且b是列表的元素; cs是列表的其余部分,这只是另一个列表.

我的观点是:始终遵循类型.你应该能够指出任何表情并说"啊哈,你是T型!".然后你可以指出那个接受该表达式的函数,并指责"什么哎,你不能有这种类型的论证!"(通过编译,通常,编译器通常很乐意借给你一个长手指,就像它有用的错误消息一样).而且那么你认为"我有什么在我手上,使从所需类型的值,该值？",运用恰到好处的功能来修复有问题的说法,这就是这么多了.哦,如果你没有任何合适的功能,你可以写一个.