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は、リストの線形再帰的な性質を利用して、それらを簡単にスキップできるようにすることです。

最後に、最上位ノードでは、結果を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

unfoldTree を使用して Tree を返す (おそらく a)

まず、データ コンストラクターに 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 を使用して返すモナディック バージョン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 に答える