Сглаживание дерева в 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 хотите позвонить foldTree из flattenTree реализовать уплощение дерева вместо того, чтобы сделать рекурсивный вызов flatTree. (Использование foldTree функции в flattenTree) .Can кто поможет мне о том, как его интегрировать.

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.