如何在递归期间存储树？（霍夫曼解码）

Question

我正在努力学习 Haskell。我正在尝试实现霍夫曼树。我的解码函数的参数是（基本上，'signature'）：

decode :: HTree -> [Int] -> [Char]

所以，给定树和数字列表，我想 return 解码消息。假设 a = 01, b = 1, c = 001, d = 000.

当我可以使用两棵树进行解码时，我知道怎么做了。即：

decode :: HTree -> HTree -> [Int] -> [Char]

简而言之，保持第一棵树为原树，另一棵树根据[Int]中的下一个数字向左或向右走（如果是0，则向左走，如果是1，则走正确的）。重复此操作直到到达一片叶子，然后将叶子添加到 [Char] 的列表中并继续使用递归。但是，我试图只用一棵树来做到这一点，即：

decode :: HTree -> [Int] -> [Char]

但是我在遍历它寻找叶子时看不到如何存储原始 HTree。我有办法在 haskell?

中做到这一点

Answer 1

只需编写一个可以访问原始树的递归辅助函数：

decode :: HTree -> [Int] -> [Char]
decode orig = go orig
  where go :: HTree -> [Int] -> [Char]
        go curr = -- use both orig and curr here

How to store tree during recursion? (Huffman decoding)