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

Question

我正在尝试在 haskell 中实现霍夫曼编码并使用以下两种数据结构：

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

其中首先根据每个字符的frequency/weight创建Wtree。 Wtree构造好后，我们知道了树的结构，我不再需要每个树的权重leaf/branch所以我想把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 非常简单，您甚至不需要定义它：您可以在使用站点内联它。

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

how to traverse a tree structure and change its data type

binary-tree

haskell

type-conversion

huffman-code