haskell - 在 Haskell 中难以实现 Huffman 树

Question

我正在尝试学习 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, ????)]

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

Answer 1

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

假设左子树编码为:

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

假设正确的子树编码是:

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

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

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

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

看看我在那里做了什么？我在前面加上 False到左子树中的每个路径，然后我在前面加上 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)

你去吧!现在剩下的就是定义基本情况: Leaf 的路径应该是什么？是？好吧，根据你给出的例子，每个 Leaf将有一条空路径，这反射(reflect)了您不需要轮流从那片叶子到同一片叶子的事实:

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]

附言注意一个类型不能命名 htree ，因为 Haskell 中的类型名称必须大写。你可能注意到我把它重命名为 HTree在我的最后一个片段中。