如何通过实例实现filter？求自定义Tree类型的filter实例示例及与fmap区别

首先补全你的Tree定义中依赖的Color类型（假设是红黑树的颜色定义）：

data Color = Red | Black deriving (Show)
data Tree a = Leaf | Node a Color (Tree a) (Tree a) deriving (Show)

Haskell标准库中没有专门对应filter操作的类型类（filter最初是为List设计的），所以需要为自定义的Tree类型手动实现过滤函数，以下是具体实现：

实现filterTree函数 #

我们通过递归遍历树的每个节点，保留满足条件的节点，并将不满足条件节点的子树中符合要求的部分合并：

-- 辅助函数：合并两棵树，将左树的所有节点附加到右树的左侧分支
mergeTrees :: Tree a -> Tree a -> Tree a
mergeTrees Leaf t = t
mergeTrees (Node x color left right) t = Node x color left (mergeTrees right t)

-- 核心过滤函数：保留Tree中满足条件的元素
filterTree :: (a -> Bool) -> Tree a -> Tree a
filterTree _ Leaf = Leaf
filterTree f (Node x color left right)
  | f x = Node x color (filterTree f left) (filterTree f right)
  | otherwise = mergeTrees (filterTree f left) (filterTree f right)

测试示例 #

-- 构造测试用的树
testTree :: Tree Int
testTree = Node 5 Red
            (Node 3 Black Leaf Leaf)
            (Node 7 Red
              (Node 6 Black Leaf Leaf)
              (Node 2 Red Leaf Leaf))

-- 调用过滤函数，筛选出大于4的元素
filteredTree = filterTree (>4) testTree
-- 输出结果：Node 5 Red Leaf (Node 7 Red (Node 6 Black Leaf Leaf) Leaf)

与fmap的核心差异 #

先看Tree的Functor实例（这是fmap的基础实现）：

instance Functor Tree where
  fmap _ Leaf = Leaf
  fmap f (Node x color left right) = Node (f x) color (fmap f left) (fmap f right)

两者的核心区别：

• 作用目标不同：
  • fmap是转换元素：遍历树的每个节点，将元素通过给定函数映射为新值，但完全保留树的原有结构（节点数量、层级关系不变）。比如fmap (+1) testTree会把所有节点的元素加1，原有的3、2等节点依然存在，只是值变成了4、3。
  • filterTree是筛选元素：根据条件保留或移除节点，树的结构会被修改（不满足条件的节点会被删除，其子树中符合条件的节点会被合并保留）。比如filterTree (>4) testTree会移除3、2这两个节点，只保留5、7、6。
• 结果结构变化：
  • fmap的输出树与输入树结构完全一致，仅元素值不同。
  • filterTree的输出树节点数量可能减少，甚至可能变成空的Leaf（当所有元素都不满足条件时）。

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