Haskell中为n叉树实现带中序遍历的Foldable实例

你的代码存在明显逻辑漏洞：处理带子女节点时，既没处理当前节点x，也没处理第一个子树t，导致折叠结果缺失关键元素，自然无法通过有序性测试。

错误代码分析 #

原代码的第二个分支：

foldr f b (NodeL x (t:ts)) = foldr f (foldr f b ts)

这里完全忽略了t和x，仅折叠了除第一个子树外的其他子树，漏掉了当前节点和第一个子树的遍历，这是核心问题。

正确实现方案 #

我们沿用二叉树中序遍历的扩展逻辑：先中序遍历第一个子树，访问当前节点，再依次中序遍历剩余子树，以下是两种可行实现：

方式1：直接实现foldr

data TreeL a = NodeL a [TreeL a] deriving (Show, Eq)

instance Foldable TreeL where
  -- 叶子节点：直接将当前节点应用到折叠函数
  foldr f b (NodeL x []) = f x b
  -- 非叶子节点：按「第一个子树 → 当前节点 → 剩余子树」的顺序折叠
  foldr f b (NodeL x (t:ts)) = foldr f (f x (foldr (foldr f) b ts)) t

逻辑解释：

• foldr (foldr f) b ts：将剩余所有子树按中序遍历折叠到初始值b，得到剩余子树的折叠结果
• f x (...)：把当前节点x插入到剩余子树折叠结果的前面（对应遍历顺序中节点在剩余子树之前）
• foldr f (...) t：把第一个子树t的折叠结果放在最前面，符合中序遍历顺序

方式2：通过foldMap实现（更简洁直观）

利用Foldable默认foldr基于foldMap的特性，直接描述遍历顺序：

data TreeL a = NodeL a [TreeL a] deriving (Show, Eq)

instance Foldable TreeL where
  foldMap f (NodeL x ts) = case ts of
    [] -> f x
    (t:rest) -> foldMap f t <> f x <> foldMap (foldMap f) rest

这里foldMap直接定义了遍历的元素顺序：第一个子树的映射结果，拼接当前节点的映射结果，再拼接剩余子树的映射结果。对于列表[]来说，<>就是列表拼接，因此foldr (:) []会直接得到中序遍历的元素列表，完全符合你的测试需求。

验证示例 #

比如对于树：

testTree = NodeL 3 [NodeL 1 [], NodeL 2 []]

使用foldr (:) [] testTree会得到[1,3,2]，如果测试用例的树结构保证第一个子树节点值小于当前节点、剩余子树节点值大于当前节点，就能得到有序列表。

内容的提问来源于stack exchange，提问作者Омар Ларрондо