使用按順序遍歷扁平化haskell中的樹

Question

我想使用我定義的foldTree函數和按順序遍歷實現扁平化樹。在扁平化後應該返回一個列表。

data Tree t = Leaf t 
     | Tree (Tree t) t (Tree t) 


foldTree :: (t1 -> t -> t1 -> t1) -> (t -> t1) -> Tree t -> t1 
foldTree treeFn leafFn tree = 
case tree of 
    Leaf v -> leafFn v 
    Tree leftTree q rightTree -> treeFn (foldTree treeFn leafFn leftTree) q (foldTree treeFn leafFn rightTree) 


Input : foldTree (\t1 t t2->t1 + 5*t + t2) (\x->x+9) (Leaf 5) 
Expected Output : 14 

Input : foldTree (\t1 t t2->t1 + 3*t + t2) (\x->x+5) (Tree (Leaf 3) 2 (Leaf 4)) 
Expected Output : 23 

我嘗試下面的代碼，但它使用recursion.I想從flattenTree調用foldTree實現樹的扁平化，而不是製造遞歸調用flatTree的。（使用flattenTree foldTree功能）。可任何人的幫助我如何整合它。

flatTree :: Tree a -> [a] 
flatTree tree = 
case tree of 
    Leaf v -> [v] 
    Tree p v r -> (flatTree p) ++ [v] ++ (flatTree r) 

Input: flatTree (Tree (Leaf 5) 3 (Tree (Leaf 3) 2 (Leaf 4))) 
Expected output : [5,3,3,2,4] 

Answer 1

看看foldTree的類型。

foldTree :: (b -> a -> b -> b) -> (a -> b) -> Tree a -> b 

您可以看到b是變形的結果類型。 foldTree通過摺疊每個子樹來獲得結果b，然後使用摺疊函數將它們組合在一起。

既然你想要結果是一個扁平的樹元素列表，我們設置b ~ [a]。

foldTree :: ([a] -> a -> [a] -> [a]) -> (a -> [a]) -> Tree a -> [a] 

所以foldTree第二個參數應該是其注入的單個元素a到一個列表[a]，而首先應該是一個結合了兩個名單與元素做出更大的名單。

---

順便說一句，GHC是能夠編寫你flatTree功能對你來說，只要看一眼類型的結構。 flatTree :: Tree a -> [a]與toList :: Foldable f => f a -> [a]的類型匹配，該類型是Foldable類的一部分。所有你需要做的就是說出神奇的詞語，deriving Foldable，而GHC會吐出一個Foldable的實例。

{-# LANGUAGE DeriveFoldable #-} 

data Tree t = Leaf t 
      | Tree (Tree t) t (Tree t) 
      deriving Foldable 

flatTree :: Tree a -> [a] 
flatTree = toList 

由於方式的Tree構造被佈置，toList將執行有序遍歷。這可以通過調整Tree構造函數的定義來改變。