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

我正在努力使用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

最佳答案

让我们假设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