in-order traversalを使用して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がflatTreeに再帰呼び出しを行うのではなく、木の平坦化を実現するためにflattenTreeからfoldTreeを呼び出したい使用しています。誰も助け.Can（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の第2引数は、リスト[a]に単一の要素aを注入何かであるべきであり、最初は大きなリストを作成する要素を持つ2つのリストを組み合わせたものでなければなりません。

---

ちなみに、GHCはちょうどタイプの構造を見ることによって、あなたのためにflatTree関数を記述することができます。 flatTree :: Tree a -> [a]は、Foldableクラスの一部であるtoList :: Foldable f => f a -> [a]のタイプと一致します。あなたがする必要があるのは、魔法の言葉である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コンストラクタの定義を調整することによって変更できます。