如何遍历树结构并更改其数据类型

Question

我正在尝试在Haskell中实现huffman编码，并使用以下两种数据结构：

data Htree = Leaf Char | Branch Htree Htree deriving Show
data Wtree = L Integer Char | B Integer Wtree Wtree deriving Show

其中Wtree首先根据每个字符的频率/权重创建。在构建Wtree之后，我们知道树的结构，我不再需要每个叶子/分支的权重，所以我想将Wtree转换为Htree，但我在解决这个问题时遇到了麻烦。

createHtree :: Wtree -> Htree
createHtree(L _ char) = Leaf char
createHtree(B _ w1 w2) = Branch createHtree(w1) createHtree(w2)

这是我尝试的解决方案，但它无法编译

预期的结果是，正如我提到的从Wtree到Htree的转换，只需要删除Wtree的整数部分。

Answer 1

您可以通过仅使用单个数据类型并按您希望在每个节点上存储的数据类型对其进行参数化来简化此任务：

data HTree a = Leaf a Char | Branch a (HTree a) (HTree a)

然后，你的加权树是HTree Integer的，而你的未加权树是HTree ()的，表明你不希望在树中存储额外的数据。这样，Haskell可以清楚地看到你的两种类型是密切相关的 - 与你在问题中发布的代码，它们似乎是两种完全不相关的类型。如果您另外打开一个无害的语言扩展，则可以使用这种密切的关系来避免自己编写转换！

{-# LANGUAGE DeriveFunctor #-}
import Data.Functor ((<$))
data HTree a = Leaf a Char
             | Branch a (HTree a) (HTree a)
             deriving Functor
stripLabels :: HTree a -> HTree ()
stripLabels = (() <$)

请注意，现在stripLabels非常简单，您甚至不需要定义它：您只需在使用站点内联它即可。