1

我已将我的一般树声明如下

data GeneralTree a = EmptyTree | Node a [GeneralTree a]

我已经建立了这个 GeneralTree 的一个实例。现在我想将它转换为在Data.Tree中声明的 Tree 类型。我该怎么做？

我想写一个如下类型的函数

convertTree :: GeneralTree a -> Tree a

但我在处理空树时遇到了麻烦，因为在树的 Data.Tree 定义中没有对应的树。

4

1 回答 1

3

由于Maybe的定义， 只能在树的顶层使用Tree a。这只会避免 'pure' 的转换EmptyTree，这听起来不错，因为目标类型中不可能有等效值。然后，正如我在第一个答案中所说，适应以后出现的唯一方法EmptyTree是利用 list 的线性递归性质，从而可以轻松地跳过它们。

最后，对于顶部节点，我们必须将结果包装成一个Maybe类型以避免转换为 pure EmptyTree。然后，我们就可以毫无顾虑地在子森林上合理地工作了。

这导致了这个版本，这是最容易遵循的。

convertGTree :: GeneralTree a -> Maybe (Tree a)
convertGTree EmptyTree             = Nothing
convertGTree (GNode a forestGTree) = Just (Node a forest)
    where 
      forest = buildForest forestGTree
      buildForest :: [GeneralTree a] -> [Tree a]
      buildForest []     = []
      buildForest (x:xs) = case x of  
        GNode n forest -> (Node n (buildForest forest)) : (buildForest xs) 
        _              -> buildForest xs

插图测试，

>>> let testGeneralTree = GNode "0" [GNode "1" [GNode "2" [], EmptyTree], GNode "3" [EmptyTree]]
>>> putStrLn . drawTree . fromJust . convertGTree $ testGeneralTree
0
|
+- 1
|  |
|  `- 2
|
`- 3

使用展开树并返回一棵树（也许是一棵树）

首先，避免将 Node 用于数据构造函数，因为 Tree 数据类型已经在使用它，否则您将遇到名称冲突。这就是为什么我们选择这样重新定义它，

data GeneralTree a = EmptyTree | GNode a [GeneralTree a] 
    deriving (Show)

EmptyTree您可以通过中间Maybe类型来处理这个问题。
首先，我通过一个在幕后buildSafeTree使用的函数。 一个助手帮助管理案例并在遇到值时返回 Nothing。 构建安全树后，我们可以使用 清理它，其中的技巧将通过语句的大小写跳过值。unfoldTree
EmptyTree
cleanSafeTreecleanForestNothing

下面的代码，

testGeneralTree = GNode "0" [GNode "1" [GNode "2" [], EmptyTree], GNode "3" [EmptyTree]]

convertTree :: GeneralTree a -> Tree a
convertTree = cleanSafeTree . buildSafeTree

buildSafeTree :: GeneralTree a -> Tree (Maybe a)
buildSafeTree = 
  unfoldTree helper 
    where 
      helper :: GeneralTree a -> (Maybe a, [GeneralTree a]) 
      helper EmptyTree       = (Nothing, []) 
      helper (GNode a trees) = (Just a, trees)


cleanSafeTree :: Tree (Maybe a) -> Tree a 
cleanSafeTree tree@(Node (Just root) forest) = 
  Node root (cleanForest forest) 
    where 
      cleanForest :: Forest (Maybe a) -> Forest a
      cleanForest []     = []
      cleanForest (x:xs) = case x of  
        Node Nothing _      -> cleanForest xs
        Node (Just x) trees -> (Node x (cleanForest trees)) : (cleanForest xs)

一些测试，

>>> testGeneralTree 
GNode "0" [GNode "1" [GNode "2" [],EmptyTree],GNode "3" [EmptyTree]]

>>> putStrLn . drawTree .  convertTree $ testGeneralTree
0
|
+- 1
|  |
|  `- 2
|
`- 3

>>> putStrLn . drawTree . fmap show . buildSafeTree $ testGeneralTree
Just "0"
|
+- Just "1"
|  |
|  +- Just "2"
|  |
|  `- Nothing
|
`- Just "3"
   |
   `- Nothing

使用unfoldForest时间更短。

convertTrees :: GeneralTree a -> Tree a
convertTrees (GNode a forest) = 
  Node a (cleanForest . unfoldForest helper $ forest) 
    where
      -- build a Forest of Tree (Maybe a) from GeneralTree a
      toTreeMaybe :: GeneralTree a -> (Maybe a, [GeneralTree a])
      toTreeMaybe EmptyTree           = (Nothing, [])
      toTreeMaybe (GNode a subForest) = (Just a , subForest)
      -- Clean the Maybe a, for a Forest of Tree Maybe a
      fromMaybe :: Forest (Maybe a) -> Forest a
      fromMaybe []     = []
      fromMaybe (x:xs) = case x of    
        Node Nothing _     -> cleanForest xs
        Node (Just x) trees -> (Node x (cleanForest trees)) : (cleanForest xs)

使用 UnfoldTreeM 返回的 Monadic 版本Maybe (Tree a)

使用的解决方案unfoldTreeMonadic

convertMonadicTrees :: GeneralTree a -> Maybe (Tree a)
convertMonadicTrees = unfoldTreeM helper where 
    helper :: GeneralTree a -> Maybe (a, [GeneralTree a]) 
    helper EmptyTree       = Nothing
    helper (GNode a trees) = Just (a, trees)

主要区别在于，它不返回任何内容，那么如果 GeneralTree 包含 EmptyTree 值，它将被丢弃。

>>> testGeneralTree2 
GNode 0 [GNode 1 [GNode 2 [],EmptyTree],GNode 3 [EmptyTree]]
>>> convertMonadicTrees testGeneralTree2
Nothing
于 2013-05-10T00:11:32.457 回答