时间戳

首页 > 解决方案 > 在 Haskell 中难以实现 Huffman 树

haskell - 在 Haskell 中难以实现 Huffman 树

问题描述

我正在尝试学习 Haskell，但发现它真的很困难，并且没有很多在线资源。我似乎对递归调用的外观有一些严重的缺乏了解，并且希望能指出正确的方向。我正在尝试接收一棵树并返回每个叶节点以及存储在那里的符号，以及到达那里的路径。（因此输入 (Fork (Leaf x) (Leaf y)) 将具有输出 [(x,[False]) ,(y,[True])] ）。我的代码如下所示：

data htree a = Leaf a | Fork (htree a) (htree a) deriving (Show, Eq)

encode :: htree a -> [(a, [Bool])]
encode (Leaf a) = [(a, ????)]

我明白这没什么好说的。我已经确定了基本情况，即每当你到达一片叶子时，你返回存储在叶子上的符号，以及你到达那里的路径。左为假，右为真。我不确定如何将所有这些信息放在一起以继续我的代码。我会很感激这里的任何指导。

标签： haskellfunctional-programminghuffman-code

解决方案

考虑Fork. 它有两个子树，每个子树都有一些编码。

假设左子树编码为：

[(x, pathToX), (y, pathToY)]

假设正确的子树编码是：

[(a, pathToA), (b, pathToB)]

现在，你能看到整个 fork 的编码应该是什么吗？应该是这样的：

[(a, True : pathToA), (b, True : pathToB), (x, False : pathToX), (y, False : pathToY)]

你同意吗？如果没有，请考虑一下。也许通过一些小例子来工作。直到您同意这种情况。

看看我在那里做了什么？我False在左子树的每条路径前面加上 a，然后True在右子树的每条路径前面加上。

让我们用 Haskell 语法写下来：

encode (Fork left right) = prependToEach False (encode left) ++ prependToEach True (encode right)

现在你可能已经注意到我在这里作弊了：我使用了一个prependToEach不存在的函数。好吧，没关系，让我们定义它！

prependToEach x list = map (prepend x) list

看？为列表的每个元素添加一个事物只是在列表上映射一个单元素的前置函数。

当然，我又作弊了：目前还没有这个功能prepend。所以要有一个！

prepend x (a, path) = (a, x : path)

你去吧！现在剩下的就是定义基本情况：a 的路径应该Leaf是什么？好吧，根据您给出的示例，每个Leaf路径都会有一条空路径，这反映了您不需要轮流从那片叶子到同一片叶子的事实：

encode (Leaf a) = [(a, [])]

现在，把它们放在一起：

encode :: HTree a -> [(a, [Bool])]
encode (Leaf a) = [(a, [])]
encode (Fork left right) = prependToEach False (encode left) ++ prependToEach True (encode right)
    where
    prependToEach x list = map (prepend x) list
    prepend x (a, path) = (a, x : path)

现在我们了解了它是如何构造的以及为什么构造它，我们可以通过使用列表推导来稍微缩短它（尽管我认为这一步非常可选）：

encode :: HTree a -> [(a, [Bool])]
encode (Leaf a) = [(a, [])]
encode (Fork left right) = [(x, False : p) | (x, p) <- encode left] ++ [(x, True : p) | (x, p) <- encode right]

PS 请注意，不能命名htree类型，因为 Haskell 中的类型名称必须大写。您可能会注意到我HTree在最后的代码片段中将其重命名为。

推荐阅读