Haskell中Tree类型的Foldable实例foldr函数实现问题

关于“枢纽元素”的说明 #

你提到的“枢纽元素”在这里就是每个树/子树的根节点，也就是Tree val left right构造器中的val字段，无需额外查找，直接从构造器中即可获取。

现有代码的问题 #

你当前的foldr实现遍历顺序为 右子树 → 左子树 → 根节点，与需求的根节点 → 左子树 → 右子树（前序遍历）完全相反，因此输出结果不符合预期。

正确实现 #

instance Foldable Tree where
    foldr _ b Empty = b
    foldr op b (Tree val left right) = op val (foldr op (foldr op b right) left)

逻辑解释 #

• 空树直接返回初始累积值b
• 非空树时：
  1. 先处理根节点val，将其通过操作符op与后续遍历结果结合
  2. 先完成右子树的遍历（foldr op b right），将结果作为左子树遍历的初始累积值
  3. 左子树遍历完成后，最终与根节点的操作结果结合，实现根→左→右的前序遍历顺序

验证示例 #

使用你提供的调用：

foldr (++) [] (Tree "m" (Tree "b" (Tree "a" Empty Empty) (Tree "g" Empty Empty)) (Tree "z" Empty Empty))

该实现会按顺序拼接字符串："m" → "b" → "a" → "g" → "z"，最终得到期望输出："mbagz"

内容的提问来源于stack exchange，提问作者Adnan Eren Güngörmüş