如何定义线性时间运行的listTree？求解Haskell代码中f的正确实现

你写的f a b c = a ++ [b] ++ c报错的核心原因是类型不匹配：
这里foldTree返回的不是列表，而是[a] -> [a]类型的差分函数，用于避免++的额外开销保证线性时间，你代码里foldTree f z t []就是把这个函数作用在空列表上得到最终结果。

正确实现 #

listTree' :: Tree a -> [a]
listTree' t = foldTree f z t []
    where
    -- leftFunc：左子树对应的差分函数，x：当前节点值，rightFunc：右子树对应的差分函数
    f leftFunc x rightFunc = \rest -> leftFunc (x : rightFunc rest)
    z = id -- 等价于你原来写的 z [] = []，空树直接透传传入的后缀列表

原理说明 #

差分函数的语义是将自身代表的列表拼接到入参的后缀列表前面：

• 比如代表列表[1,2]的差分函数就是\rest -> 1 : 2 : rest
• 中序遍历的拼接顺序是左子树结果 + 当前节点 + 右子树结果 + 后缀，对应到差分函数就是先把后缀传给右子树的差分函数得到右半部分结果，把当前节点拼到前面再传给左子树的差分函数，刚好得到整体拼接后的列表。

这种实现每个节点仅执行一次O(1)的(:)操作，整体遍历时间复杂度严格为线性。

内容的提问来源于stack exchange，提问作者Confused Programmer