使用fold实现二叉树上的映射

Question

我正在努力使用树定义地图foldBT.我的想法是将树转换为列表,将运算符映射到列表,然后将列表转换回树.但它听起来效率低,也没有利用foldBT...我试图运行,foldBT (*2) Nil (numTree [3,5,7]但ghci报告错误.我真的不明白这个功能foldBt是如何运作的.一个例子就是很棒.

data SimpleBT a = Nil | N a (SimpleBT a) (SimpleBT a) deriving (Show, Eq)

foldBT :: (a -> b -> b -> b) -> b -> SimpleBT a -> b
foldBT f e Nil = e
foldBT f e (N a left right) = f a (foldBT f e left) (foldBT f e right)

mapTree :: (a -> b) -> SimpleBT a -> SimpleBT b
mapTree f Nil = Nil
mapTree f (N a left right) = N (f a) (mapTree f left) (mapTree f right)

size :: SimpleBT a -> Int
size Nil = 0
size (N _ left right) = 1 + size left + size right

insert ::  SimpleBT a -> a -> SimpleBT a
insert Nil a = N a Nil Nil
insert (N x left right) a
  | size left <= size right = N x (insert left a) right
  | otherwise = N x left (insert right a)

numTree :: [a] -> SimpleBT a
numTree xs = foldl insert Nil xs

Answer 1

让我们假设mapTree f = foldBT g e,并解决g和e.定义foldBT说:

foldBT g e Nil = e

同时,从定义来看mapTree,我们得到:

mapTree f Nil = Nil

根据我们的假设mapTree f = foldBT g e,我们可以转换第二个方程并将其贴在第一个方程旁边:

foldBT g e Nil = Nil
foldBT g e Nil = e

所以e = Nil.

我们现在就做其他条款.定义foldBT说:

foldBT g e (N a left right) = g a (foldBT g e left) (foldBT g e right)

同时,mapTree定义说:

mapTree f (N a left right) = N (f a) (mapTree f left) (mapTree f right)

再次,使用我们的假设mapTree f = foldBT g e,我们现在可以重写这个等式,并将它贴在第一个等式旁边:

foldBT g e (N a left right) = N (f a) (foldBT g e left) (foldBT g e right)
foldBT g e (N a left right) = g a (foldBT g e left) (foldBT g e right)

所以g a = N (f a)将验证这个等式.将这些全部写在一个地方,我们得到:

mapTree f = foldBT g e where
    e = Nil
    g a = N (f a)

您可以内嵌的定义e以及g如果你喜欢; 我会.

mapTree f = foldBT (N . f) Nil