haskell - 从Haskell中的(预序)位串重建霍夫曼树

Question

我有以下 Haskell 多态数据类型:

data Tree a = Leaf Int a | Node Int (Tree a) (Tree a)

树将被压缩为 0 和 1 的位串。 '0' 表示一个节点，然后是左子树的编码，然后是右子树的编码。 '1' 表示叶子，后跟 7 位信息(例如，它可能是一个字符)。每个节点/叶子也应该包含存储信息的频率，但这对于这个问题并不重要(所以我们可以在那里放任何东西)。

例如，从这个编码树开始

[0,0,0,1,1,1,0,1,0,1,1,1,1,1,1,0,1,0,0,0,0,1,1,1,1,0,0,0,1,1,1,
 1,0,0,1,1,1,1,1,1,1,0,0,1,0,0,1,1,1,1,0,1,1,1,1,1,1,0,0,0,0,1]

它应该回馈这样的东西

Node 0 (Node 0 (Node 0 (Leaf 0 'k') (Leaf 0 't')) 
       (Node 0 (Node 0 (Leaf 0 'q') (Leaf 0 'g')) (Leaf 0 'r'))) 
(Node 0 (Leaf 0 'w') (Leaf 0 'a'))

(间距并不重要，但它不适合一行)。

我几乎没有使用树的经验，尤其是在实现代码时。我对如何在纸上解决这个问题有一个模糊的想法(使用类似于堆栈的东西来处理深度/级别)，但我仍然有点迷茫。

任何帮助或想法表示赞赏!

Answer 1

好吧，您正在尝试从比特流中解析一棵字节树。解析是需要设置一些结构的情况之一:我们将编写一个微型解析器组合库，样式为How to Replace Failure by a List of Successes。 ，这将使我们能够以惯用的函数式风格编写代码，并将大量工作委托(delegate)给机器。

翻译the old rhyme进入 monad 转换器的语言，并将“string”读为“bit-string”，我们有

newtype Parser a = Parser (StateT [Bool] [] a)
    deriving (Functor, Applicative, Monad, Alternative)

runParser :: Parser a -> [Bool] -> [(a, [Bool])]
runParser (Parser m) = runStateT m

解析器是一种单子(monad)计算，它有状态地在 bool 值流上运行，产生一个成功解析的集合 a s。 GHC的 GeneralizedNewtypeDeriving super 大国允许我省略 Monad 的样板实例等。

那么，目标是写一个 Parser (Tree SevenBits) - 一个解析器，它返回一棵 bool 值的七元树。 (您可以在闲暇时通过 deriving a Word8 instance 将 Functor 和使用 Tree 的 7 位转换为 fmap。)我将使用 Tree 的以下定义。因为它更简单 - 我相信您可以弄清楚如何根据自己的目的调整此代码。

data Tree a = Leaf a | Node (Tree a) (Tree a) deriving Show

type SevenBits = (Bool, Bool, Bool, Bool, Bool, Bool, Bool)

这是一个解析器，它尝试从输入流中消耗一个位，如果它为空则失败:

one :: Parser Bool
one = Parser $ do
    stream <- get
    case stream of
        [] -> empty
        (x:xs) -> put xs *> return x

这是一个尝试从输入流中消耗特定位的方法，如果不匹配则失败:

bit :: Bool -> Parser ()
bit b = do
    i <- one
    guard (i == b)

在这里，我使用 replicateM 从输入流中提取一个由七个 bool 值组成的序列。并将它们打包成一个元组。我们将使用它来填充 Leaf节点的内容。

sevenBits :: Parser SevenBits
sevenBits = pack7 <$> replicateM 7 one
    where pack7 [a,b,c,d,e,f,g] = (a, b, c, d, e, f, g)

现在我们终于可以编写解析树结构本身的代码了。我们将在 Node 之间进行选择和 Leaf使用 <|> 的替代方案.

tree :: Parser (Tree SevenBits)
tree = node <|> leaf
    where node = bit False *> liftA2 Node tree tree
          leaf = bit True *> fmap Leaf sevenBits

如果 node成功地从流的头部解析了一个低位，它继续递归地解析左子树的编码，然后是右子树，使用 liftA2 对应用操作进行排序.诀窍是 node如果在输入流的头部没有遇到低位，则失败，这告诉 <|>放弃 node并尝试 leaf反而。

注意 tree 的结构反射(reflect)了 Tree的结构键入自己。这是工作中的应用解析。我们可以交替地构造这个解析器，首先使用 one解析任意位，然后使用 case对位进行分析，以确定我们应该继续解析一对树还是一片叶子。在我看来，这个版本更简单、更具声明性且不那么冗长。

还将这段代码的清晰度与@behzad.nouri 的 foldr 的低级风格进行比较。基于的解决方案。我的设计不是构建一个在解析节点和叶子之间切换的显式有限状态机——一个命令式的想法——我的设计允许您使用像 liftA2 这样的标准函数向机器声明式地描述语法。和 <|>并相信抽象会做正确的事情。

无论如何，我在这里解析一个由一对 Leaf 组成的简单树。 s 包含(二进制编码的)数字 0和 1 .如您所见，它返回单个成功解析和剩余位的空流。

ghci> runParser tree $ map (>0) [0, 1, 0,0,0,0,0,0,0, 1, 0,0,0,0,0,0,1]
[(Node (Leaf (False, False, False, False, False, False, False)) (Leaf (False, False, False, False, False, False, True)),[])]