Haskell Foldable树实现疑问：mempty与mappend的类型推导及实现

1. mempty和mappend的来源 #

foldMap是Foldable类型类的核心方法，它的类型签名要求返回值属于Monoid类型类。mempty是Monoid的单位元，mappend是Monoid的二元合并操作——这两个函数都直接来自Monoid类型类，Haskell会根据上下文自动匹配对应的Monoid实例，不需要额外显式声明，只要当前作用域能找到Monoid的定义即可。

2. 类型信息推导 #

先明确foldMap的标准类型：

foldMap :: (F.Foldable t, Monoid m) => (a -> m) -> t a -> m

对于我们的Tree实例：

• 处理Empty时，foldMap f Empty返回mempty，其类型就是foldMap要求的返回类型m，保证类型一致。
• 处理Node x l r时，F.foldMap f l的类型是m，f x的类型是m（因为f的类型是a->m），F.foldMap f r同样是m，三个m类型的值通过mappend合并后，最终返回值还是m，完全符合foldMap的类型约束。

3. F.foldl (+) 0 testTree的推导过程 #

F.foldl的默认实现依赖于foldMap，我们一步步拆解逻辑：

• (+)是Num a => a -> a -> a，0是Num a => a，Haskell会自动把这个Num类型对应到Sum Monoid（Sum的mappend就是+，mempty就是0）。
• 具体执行时，F.foldl (+) 0 testTree会触发foldMap，此时传入的映射函数f是Sum，即把树中每个元素x转换成Sum x。
• foldMap Sum testTree会遍历整棵树：空节点返回mempty（也就是Sum 0），非空节点则递归合并左子树的结果、当前节点的Sum x、右子树的结果。
• 最后foldl会自动把合并后的Sum值拆包，取出内部的数值，最终得到和直接用(+)累加所有节点元素相同的结果。

补充说明 #

选择用foldMap实现Foldable是因为它是最简洁的核心实现——只要完成foldMap的定义，Foldable提供的其他所有折叠相关方法（比如foldr、sum、product）都能通过默认实现自动生效，这也是《Learn You a Haskell》采用这种写法的原因。

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