如何在PureScript中为自定义Tree实现fold right（右折叠）

你当前的实现存在两个核心问题：

• foldr的Leaf分支错误：直接返回a忽略了初始值d，不符合foldr的类型签名（应返回累积值类型b，而非元素类型a），正确逻辑是用f将元素a与初始值d结合。
• foldr的Node分支逻辑错误：你直接将左右子树的折叠结果传入f，但f的类型是a -> b -> b，第一个参数必须是树中的元素a，而非折叠后的累积值b；同时右折叠的顺序应为先处理右子树，再将左子树的元素与右子树的折叠结果结合。

以下是修正后的完整实现：

data Tree a = Leaf a | Node (Tree a) (Tree a)

instance foldableTree :: Foldable Tree where
    -- 左折叠：先遍历左子树，再用左子树的折叠结果遍历右子树
    foldl f d (Node left right) = foldl f (foldl f d left) right
    foldl f d (Leaf a) = f d a

    -- 右折叠：先遍历右子树得到累积值，再用该值遍历左子树
    foldr f d (Node left right) = foldr f (foldr f d right) left
    foldr f d (Leaf a) = f a d

逻辑说明 #

• foldl（左折叠）：
  对于Node left right，先将初始值d与左子树做左折叠得到新的累积值，再用这个新值遍历右子树。元素处理顺序是左子树元素从左到右，接着右子树元素从左到右，比如Node (Leaf 1) (Leaf 2)用foldl (+) 0计算的是((0 + 1) + 2)。

• foldr（右折叠）：
  对于Node left right，先将初始值d与右子树做右折叠得到累积值，再用这个值遍历左子树。元素处理顺序是右子树元素从右到左，接着左子树元素从右到左，比如Node (Leaf 1) (Leaf 2)用foldr (+) 0计算的是(1 + (2 + 0))；若用foldr (:) []，会得到[1, 2]，符合预期的元素顺序。

内容的提问来源于stack exchange，提问作者Djordje Vuckovic