Порядок бинарных деревьев Haskell со сгибом

Я определил свой тип данных BinTree, который описывает мои бинарные деревья:

data BinTree a = Empty | Node a (BinTree a) (BinTree a) deriving (Show,Eq)

После этого я реализовал три функции сортировки для бинарных деревьев: preorder, inorder и postorder:

preorder :: BinTree a -> [a]
preorder Empty = []
preorder (Node x lt rt) = [x] ++ preorder lt ++ preorder rt

inorder :: BinTree  a -> [a]
inorder Empty = []
inorder (Node x lt rt) = inorder lt ++ [x] ++ inorder rt

postorder :: BinTree a -> [a]
postorder Empty = []
postorder (Node x lt rt) = postorder lt ++ postorder rt ++ [x]

Чтобы улучшить свои функции порядка, я реализовал функцию foldTree (которая работает как обычная функция foldr, но с бинарными деревьями):

foldTree :: (a -> b -> b -> b) -> b -> BinTree -> b
    foldTree f e Empty = e
    foldTree f e (Node x lt rt) = f x (foldTree f e lt) (foldTree f e rt)

И теперь я застрял, потому что я не могу понять, как совместить функции порядка с foldTree.

Может кто-нибудь дать мне подсказку, пожалуйста?


fold haskell binary-tree inorder preorder
person Theresa    schedule 31.01.2021    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Если под комбинацией вы подразумеваете реализацию каждой из трех функций с использованием последней, то этот мой недавний ответ кажется полезным , например

preorder  t  =  foldTree (\a l r -> (a :) . l . r) id t []
inorder   t  =  foldTree (\a l r -> l . (a :) . r) id t []
postorder t  =  foldTree (\a l r -> l . r . (a :)) id t []

Пробуем:

> t = Node 1 (Node 2 Empty (Node 3 Empty Empty)) (Node 4 (Node 5 Empty Empty) Empty)
{-
                 1
        2                 4
     .      3         5       .
          .   .     .   .
-}

> inorder t
[2,3,1,5,4]

> preorder t
[1,2,3,4,5]

> postorder t
[3,2,5,4,1]

Правильный тип вашей функции, конечно,

foldTree :: (a -> b -> b -> b) -> b -> BinTree a -> b
--                                            ^^^
person Will Ness    schedule 10.02.2021