使用按顺序遍历扁平化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构造函数的定义来改变。