haskell - 递归时如何存储树？ (霍夫曼解码)

Question

我正在尝试学习 Haskell。我正在尝试实现哈夫曼树。我的解码函数的参数是(基本上是“签名”):

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

因此，给定树和数字列表，我想返回解码后的消息。假设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