如何为红黑树正确实现Monoid？遇类型推导错误求助

问题描述 #

1. Monoid实例声明错误 #

尝试为红黑树编写Monoid实例，相关Haskell代码如下：

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

instance (Ord a) => Monoid (Tree a) where
    mempty = Leaf
    l1 `mappend` l2 = foldl (\x y ->insert y x) l1 l2


instance Foldable Tree where
   foldr _ z Leaf = z
   foldr f z (Node d _ l r) = foldr f (f d (foldr f z r)) l
   foldl _ z Leaf = z
   foldl f z (Node d _ l r) = foldl f (f (foldl f z l) d) r

...

insert :: (Ord a) => a -> Tree a -> Tree a
insert x s = makeBlack $ ins s
  where ins Leaf  = Node x Red Leaf Leaf
        ins (Node d c l r)
          | x < d  = balance d c (ins l) r
          | x == d = Node d c l r
          | x > d  = balance d c l (ins r)
        makeBlack (Node d _ l r) = Node d Black l r

报错信息：

• Could not deduce (Semigroup (Tree a)) arising from the superclasses of an instance declaration
  from the context: Ord a
    bound by the instance declaration at src/RedBlackTree.hs:19:10-35
• In the instance declaration for ‘Monoid (Tree a)’
| 19 | instance (Ord a) => Monoid (Tree a) where
| ^^^^^^^^^^^^^^^^^^^^^^^^^^

已知insert需要Ord约束，但实例中约束的使用存在问题。

2. 附加疑问：fmap与foldMap的区别 #

已实现fmap，但不理解它和foldMap的区别。

解决方案与解释 #

1. 修复Monoid实例错误 #

从GHC 8.4版本开始，Monoid类的超类是Semigroup——定义Monoid实例前必须先定义对应的Semigroup实例，你的代码直接声明Monoid却未提供Semigroup实例，因此触发报错。

同时，你的mappend逻辑是将第二个树的元素逐个插入第一个树，这个操作依赖Ord a约束，因此Semigroup和Monoid实例都需要带上该约束。修改后的代码如下：

-- 先定义Semigroup实例，实现合并逻辑
instance (Ord a) => Semigroup (Tree a) where
    (<>) l1 l2 = foldl (\x y -> insert y x) l1 l2

-- 再定义Monoid实例，复用Semigroup的(<>)作为mappend
instance (Ord a) => Monoid (Tree a) where
    mempty = Leaf
    mappend = (<>)

2. fmap与foldMap的区别 #

• fmap：属于Functor类，签名为fmap :: (a -> b) -> f a -> f b。作用是将函数应用到容器的每一个元素，返回结构完全相同的新容器，仅元素被转换。比如对红黑树执行fmap (+1) tree，树的形状、颜色不变，仅所有节点的数值加1。
• foldMap：属于Foldable类，签名为foldMap :: Monoid m => (a -> m) -> f a -> m。作用是先将容器内每个元素转换为Monoid类型的值，再用Monoid的<>（即mappend）合并为单一值。比如foldMap Sum tree会计算树中所有元素的和；foldMap (\x -> [x]) tree会将树中元素按遍历顺序转为列表。简言之，foldMap是“转换+折叠”的组合，最终输出的是一个Monoid值，而非容器。

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