Haskell中(预置)位串重构Huffman树
我有以下Haskell多态数据类型：
data Tree a = Leaf Int a | Node Int (Tree a) (Tree a)树将在0和1s的位串中被压缩。'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'))(间距不重要，但不适合一行)。
我很少有使用树的经验，尤其是在实现代码时。对于如何在纸面上解决这个问题，我有一个模糊的想法(使用类似于堆栈的方法来处理深度/层次)，但我还是有点迷茫。
任何帮助或想法都是非常感谢的！
回答 3
Stack Overflow用户
发布于 2016-12-24 03:04:20
好的，这里有一个简单的(临时的，但更容易理解)的方法。
我们需要购买一个函数parse，其类型如下：
parse :: [Int] -> Tree Char您提到的带有堆栈的方法是必需的。在这里，我们只需要递归调用。堆栈将由编译器构建，它将只将每个递归调用存储在其中(至少您可以这样想，如果您愿意，或者忽略所有这一段)。
因此，其思想如下:每当您找到一个0时，您需要对该算法进行两个递归调用。第一个递归调用将读取树的一个分支(左侧)。第二个需要以列表的其余部分作为参数进行调用。第一次递归调用留下的其余部分。因此，我们需要一个具有以下类型的auxiliar函数parse' (现在我们返回一个对，它是列表的其余部分的第二个值)：
parse' :: [Int] -> (Tree Char, [Int])接下来，您可以看到一段代码，其中的0案例和前面描述的一样。
对于1的情况，我们只需要取下接下来的7个数字，并以某种方式将它们变成一个字符(我将toChar的定义留给您)，然后，只返回一个Leaf和列表的其余部分。
parse' (0:xs) = let (l, xs') = parse' xs
(r, xs'') = parse' xs' in (Node 0 l r, xs'') --xs'' should be []
parse' (1:xs) = let w = toChar (take 7 xs) in (Leaf 0 w , drop 7 xs)最后，我们的解析函数只调用辅助解析函数并返回对的第一个元素。
parse xs = fst $ parse' xsStack Overflow用户
发布于 2016-12-24 01:53:53
嗯，你在试图从一个比特流中解析一个字节树。解析是建立某种结构的代价之一:我们将以https://rkrishnan.org/files/wadler-1985.pdf的风格编写一个小型解析器组合器库，这将允许我们以惯用的函数风格编写代码，并将大量工作委托给机器。
将旧韵转换成单台变压器的语言，并将"string“读为”位字符串“，我们就有了
newtype Parser a = Parser (StateT [Bool] [] a)
deriving (Functor, Applicative, Monad, Alternative)
runParser :: Parser a -> [Bool] -> [(a, [Bool])]
runParser (Parser m) = runStateT m解析器是一种一元计算，它在布尔流上有状态地运行，生成一组成功解析的as. GHC的GeneralizedNewtypeDeriving超能力允许我删除Monad等的样板实例。
因此，我们的目标是编写一个Parser (Tree SevenBits) --一个返回布尔七叉树的解析器。(您可以在空闲时通过实例 for Tree并使用fmap将7位转换为Tree。)我将使用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从输入流中提取七个布尔值的序列，并将它们打包成一个元组。我们将使用它填充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的结构如何反映Tree类型本身的结构。这是起作用的应用程序解析。我们可以交替地构建这个解析器，首先使用one解析任意位，然后使用对该位的case分析来确定我们是应该继续解析一对树还是解析叶子。在我看来，这个版本更简单、更声明性和更少冗长。
此外，将此代码的清晰度与@behzad.funi的foldr-based解决方案的低级样式进行比较。我的设计允许您使用标准函数(如liftA2和<|> )声明性地向机器描述语法，而不是构建一个显式的有限状态机，它在解析节点和叶子之间切换--这是一种令人感兴趣的想法--我的设计允许您使用标准函数(如<|>和<|>)来描述语法，并相信抽象会做正确的事情。
无论如何，这里我解析的是一个简单的树，它由一对包含(二进制编码的)数字Leaf和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)),[])]Stack Overflow用户
发布于 2016-12-24 00:54:34
做一个正确的折叠：
import Data.Char (chr)
data Tree a = Leaf a | Node (Tree a) (Tree a)
deriving Show
build :: [Int] -> [Tree Char]
build xs = foldr go (\_ _ -> []) xs 0 0
where
nil = Leaf '?'
go 0 run 0 0 = case run 0 0 of
[] -> Node nil nil:[]
x:[] -> Node x nil:[]
x:y:zs -> Node x y :zs
go 1 run 0 0 = run 0 1
go _ _ _ 0 = error "this should not happen!"
go x run v 7 = (Leaf $ chr (v * 2 + x)): run 0 0
go x run v k = run (v * 2 + x) (k + 1)然后：
\> head $ build [0,0,0,1,1,1,0, ...] -- the list of 01s as in the question
Node (Node (Node (Leaf 'k') (Leaf 't'))
(Node (Node (Leaf 'q') (Leaf 'g')) (Leaf 'r')))
(Node (Leaf 'w') (Leaf 'a'))https://stackoverflow.com/questions/41309180
复制相似问题
腾讯云开发者
