haskell - 使用fold实现二叉树上的map

Question

我正在努力使用foldBT在树上定义 map 。我的想法是将树转换为列表，将运算符映射到列表上，然后将列表转换回树。但这听起来效率很低，而且也没有利用 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