如何定义 listTree 使其在线性时间内运行？

Question

listTree' :: Tree a -> [a]
listTree' t = foldTree f z t []
    where
    f = undefined
    z [] = []

需要帮助解决 f。当我插入 f a b c = a ++ [b] ++ c 时出现错误

data Tree a 
    = Tip
    | Bin (Tree a) a (Tree a)
    deriving (Show, Eq)


foldTree :: (b -> a -> b -> b) -> b -> Tree a -> b
foldTree f z Tip         = z
foldTree f z (Bin l x r) = f (foldTree f z l) x (foldTree f z r)

这里是 foldTree 和树的数据类型

Answer 1

为了实现线性时间，你应该让 foldTree f z t return 一个接受列表的函数并且 return 是一个列表。

这意味着对于 z 一个叶子，我们只是 return 给定的列表，因此我们不添加任何值。对于 f 我们将获取列表，用右子树调用它，然后在该列表前面加上那个 Bin 节点的值，最后用左子树调用它，所以：

listTree' :: Tree a -> [a]
listTree' t = foldTree f id t []
    where <strong>f x y z ls = x (y: z ls)</strong>

这里ls就是我们要处理的列表，z是一个函数，把右子树的items放在ls前面，y是存储在该节点中的值，x 是一个将左子树的项目添加到列表中的函数。

我们可以定义f，如如f x y z = x . (y:) . z。因此，我们首先应用为右子树生成的函数，然后在列表前添加 y，然后通过左子树的函数运行。

如何定义 listTree 使其在线性时间内运行？

How to define listTree so that it runs in linear time?

tree

time

haskell

fold