在 Haskell 中难以实现哈夫曼树

Question

我正在努力学习Haskell，但发现它真的很难，而且在线资源也不多。我似乎对递归调用的外观不太了解，希望能指出正确的方向。我正在尝试获取一棵树和 return 每个带有存储在那里的符号的叶节点，以及到达那里所采用的路径。（因此输入 (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, ????)]

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

Answer 1

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

假设左子树编码为：

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

假设右子树编码为：

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

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

[(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 都会有一条空路径，反映出你不需要轮流从那个叶子到达同一个叶子的事实：

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]

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

Answer 2

答案很好，但使用 (++) 值得警惕。通常，如果您不是咖啡师，它可能会导致您的代码运行对于特定输入非常缓慢，在这种情况下是一棵不平衡的树。

原因是（N个元素的列表）++（1个元素的列表）必须构造一个包含N+1个元素的全新列表。因此，以这种方式一次只添加几个元素可能会很慢。

避免这种情况的一种方法是使用中间函数，而不是 returning 列表，returning 函数在传递列表时 return 列表。这样您就可以组合函数（速度很快）并在最后构造列表，现在可以从左到右完成而无需重新创建元素。

下面是一个使用此方法的 encode 函数示例：

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

encode :: HTree a -> [(a, [Bool])]
encode tree = go [] tree [] where
  go :: [Bool] -> HTree a -> [(a, [Bool])] -> [(a, [Bool])]
  go path (Leaf leaf) = ((leaf, path):)
  go path (Fork left right) = go (False:path) left . go (True:path) right

请注意，您实际上并不需要类型签名，为了清楚起见，我只是将它们包括在内（这可能是一种很好的做法），但仅删除了 3 行：

encode tree = go [] tree [] where
  go path (Leaf leaf) = ((leaf, path):)
  go path (Fork left right) = go (False:path) left . go (True:path) right

注意这个 return 是从叶到根的路径，如果你想让它们从根到叶，你可以在最后反转它们或者再次使用我的 return 函数技巧。

在 Haskell 中难以实现哈夫曼树

Difficulty implementing Huffman tree in Haskell

haskell

functional-programming

huffman-code