How to properly implement a monoid for a red-black tree?-CodePudding

Good afternoon, I am trying to write a RB Tree monoid, the code is about this:

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

The problem is the declaration of the monoid:

• 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 | ^^^^^^^^^^^^^^^^^^^^^^^^^^

I understand that in order to use insert the values must be comparable, but it seems that I have somehow misdirected the (Ord a) in the instance

Bonus question: I also implemented fmap, but didn't understand the difference from foldMap

CodePudding user response：

It's not Ord that's the problem. If you look closely at the error message you got, it starts with "Could not deduce (Semigroup (Tree a)) arising from the superclasses of an instance declaration". In other words, in order to have an instance of Monoid (Tree a), you need to first have an instance for Semigroup (Tree a). Fortunately, this is easy to add:

instance (Ord a) => Semigroup (Tree a) where
    (<>) = mappend

(A perhaps more idiomatic approach would be to define <> in the Semigroup instance using the foldl definition you were using for mappend, and then in your instance for Monoid, simply leave out the definition of mappend.)

Bonus: The difference between fmap and foldMap is clear from their types. For your tree, fmap would have the type (a -> b) -> Tree a -> Tree b, indicating that it is mapping the internal a values to b values. On the other hand, foldMap would have the type Monoid m => (a -> m) -> Tree a -> m. You could choose to call foldMap with m ~ Tree b, in which case foldMap reduces to fmap, but you could also choose to call it with m ~ [b] or some other monoid.