在Haskell中难以实现霍夫曼树

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)

然后你走了！现在剩下的就是定义基本情况：Leafbe 的路径应该是什么？好吧，根据您给出的示例，每个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在最后一个代码段中将其重命名为。