Haskell：从其位表示重建二叉树

Question

我正在将霍夫曼编码算法重写为 Haskell 新手练习，我正在努力改造我使用以下技术序列化的树：
- 以深度优先预序从根开始遍历树
- 遇到一个节点 put 0 followed by recurse on left then right childs
- 遇到一个 Leaf put 1 后跟符号 byte

我的序列化代码：

serializeHtree :: (Ord a) => CodeDict a -> HTree a -> [Bit]
serializeHtree dict (Leaf a) = I : (myLpad $ dict M.! a)
serializeHtree dict (Branch l r) = O : (serializeHtree dict r ++ serializeHtree dict l)

其中：
- CodeDict 是一个从 a 到 [Bit]
的映射 - myLpad 将可变长度的霍夫曼编码填充为 0 使其成为固定长度
- Bit 是由 O 和 I

构造的我自己的数据类型

例如，

上面的树将表示为：
0100000000001000001001000001010100000110100000111

现在要反序列化它，我知道我必须逐位读取流并且：
- 遇到一个 1 用下一个字节做一个叶子
- 遇到 0 使分支在左子树和右子树上递归

但是我的方法失败了，这是我的反序列化代码（这次没有功能）：

deserializeHtree :: [Bit] -> HTree a
deserializeHtree (x:xs) = case x of
    'O' -> Branch (deserializeHtree xs) (deserializeHtree xs)
    'I' -> Leaf (head xs)

感谢支持

Answer 1

您需要编写一个解析器，使用适合递归的类型。

在顶层你确实想要 [Bit] -> HTree a（可能将 a 限制为某种类型 class，但我会忽略这一点）。但是，要启用递归，您需要

parser :: [Bit] -> (HTree a, [Bit])
-- or, if you need to handle failure
parser :: [Bit] -> Maybe (HTree a, [Bit])

这个想法是 parser 被提供了要解析的位。然后它尝试解析 first 树，该树表示在这些位的 prefix 中。如果成功，它会 returns 一个 HTree a 和超出（未消耗）位的列表。

返回未消耗的位对于 Branch 需要解析两个子树至关重要。您解析第一个，获取未消耗的位，然后使用它们启动右子树的解析器。

这个主题对于一个 SO 答案来说太广泛了，但是如果你 google 对 "Haskell parser monad" 你应该找到很多例子。

Haskell：从其位表示重建二叉树

Haskell: rebuild binary tree from its bits representation

haskell

recursion

binary-tree

huffman-code