为BinSearchTree实现foldr函数，求正确性校验及优化建议

首先明确：对于二叉搜索树（BST），Foldable实例的foldr应该遵循中序遍历（左子树 → 当前节点 → 右子树），这样遍历出来的元素是升序的，符合BST的语义。

看你的代码：

foldr f x (Branch left a right) = f a (foldr f y right)
       where y = foldr f x left

这个实现的遍历顺序是当前节点 → 右子树 → 左子树，完全不符合BST的预期。拆解执行逻辑就能看出来：

1. 先把左子树折叠到初始值x得到y
2. 再把右子树折叠到y
3. 最后用f把当前节点a和右子树的折叠结果结合

对应的元素处理顺序是：右子树的所有元素先被f处理，接着是当前节点a，最后是左子树的元素——这和BST的有序遍历逻辑完全相反。

正确的实现 #

要实现中序遍历的foldr，应该先递归处理左子树，把当前节点和右子树的折叠结果作为左子树折叠的初始值。代码如下：

instance Foldable BinSearchTree where 
  foldr _ x Empty = x
  foldr f x (Branch left a right) = foldr f (f a (foldr f x right)) left

验证例子 #

构建一个简单的测试BST：

testTree :: BinSearchTree Int
testTree = Branch (Branch Empty 1 Empty) 2 (Branch Empty 3 Empty)

用foldr (:) [] testTree测试：

• 你的实现会得到[2,3,1]，完全无序
• 正确实现会得到[1,2,3]，符合BST的升序遍历预期

如果用依赖顺序的函数（比如字符串拼接），差异会更明显：foldr (\c s -> s ++ [c]) [] testTree，你的实现得到"321"，正确实现得到"123"。

内容的提问来源于stack exchange，提问作者el Kusn