haskell - 如何定义 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返回一个接受列表并返回列表的函数。
这意味着对于 z , 一个叶子，我们只是返回给定的列表，因此我们不添加任何值。对于 f我们将获取列表，用右子树调用它，然后在该列表前面加上 Bin 的值节点，最后用左子树调用它，所以:

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

这里ls因此是我们需要处理的列表，z是将右子树的项添加到 ls 的函数, y是存储在该节点中的值，x是一个将左子树的项添加到列表中的函数。
我们可以定义 f , 如 @chi says如 f x y z = x . (y:) . z .因此，我们首先应用为右子树生成的函数，然后在列表前面加上 y ，然后通过左子树的函数运行它。