如何定义listTree函数通过foldTree返回树所有元素的有序列表

错误原因分析 #

• 运算符使用错误：你使用了数值运算符+做列表拼接，Haskell中+仅支持数值类型运算，列表拼接需要使用++运算符。这是类型报错的核心诱因，类型提示你实际得到Tree [a] -> [a]，本质是编译器错误推断了节点值的类型，误以为你需要节点存储的是列表类型，才能够参与+运算，和你声明的Tree a -> [a]不匹配。
• 参数类型不匹配：foldTree传入的折叠函数f的三个参数类型分别是[a]（左子树折叠结果）、a（当前节点存储的值）、[a]（右子树折叠结果），你直接把三个参数做拼接，第二个参数不是列表类型，无法直接参与拼接，需要先转为单元素列表[curVal]。
• 变量命名冲突：你在f的参数里使用了z作为参数名，和外层定义的初始值z = []重名，虽然不影响运行但容易引发逻辑混淆，建议修改参数名增加可读性。

正确实现 #

如果你需要的是二叉搜索树的升序有序列表，对应中序遍历逻辑，f函数定义如下：

listTree :: Tree a -> [a]
listTree = foldTree f z
    where
    f leftResult curVal rightResult = leftResult ++ [curVal] ++ rightResult
    z = []

如果需要其他遍历顺序的列表，调整拼接顺序即可：

• 前序遍历：[curVal] ++ leftResult ++ rightResult
• 后序遍历：leftResult ++ rightResult ++ [curVal]

内容的提问来源于stack exchange，提问作者Shriyu Gaglani