How do you implement monoid interface for this tree in haskell?

functional-programming, haskell, monoids

Solution

There are three answers to your question, one captious and one unhelpful and one abstract:

The captious answer

instance Monoid (Ftree a) where
    mempty = Empty
    mappend = Branch

This is an instance of the `Monoid` type class, but does not satisfy any of the required properties.

The unhelpful answer

What Monoid do you want? Just asking for a monoid instance without further information is like asking for a solution without giving the problem. Sometimes there is a natural monoid instance (e.g. for lists) or there is only one (e.g. for `()`, disregarding questions of definedness). I don’t think either is the case here.

BTW: There would be an interesting monoid instance if your tree would have data at internal nodes that combines two trees recursively...

The abstract answer

Since you gave a `Monad (Ftree a)` instance, there is a generic way to get a `Monoid` instance:

instance (Monoid a, Monad f) => Monoid (f a) where
    mempty = return mempty
    mappend f g = f >>= (\x -> (mappend x) `fmap` g)

Lets check if this is a Monoid. I use `<> = mappend`. We assume that the `Monad` laws hold (I did not check that for your definition). At this point, recall the Monad laws written in do-notation.

Our `mappend`, written in do-Notation, is:

mappend f g = do
  x <- f
  y <- g
  return (f <> g)

So we can verify the monoid laws now:

Left identity

mappend mempty g
≡ -- Definition of mappend
do 
  x <- mempty
  y <- g
  return (x <> y)
≡ -- Definition of mempty
do 
  x <- return mempty
  y <- g
  return (x <> y)
≡ -- Monad law
do 
  y <- g
  return (mempty <> y)
≡ -- Underlying monoid laws
do 
  y <- g
  return y
≡ -- Monad law
g

Right identity

mappend f mempty 
≡ -- Definition of mappend
do
  x <- f
  y <- mempty
  return (x <> y)
≡ -- Monad law
do
  x <- f
  return (x <> mempty)
≡ -- Underlying monoid laws
do 
  x <- f
  return x
≡ -- Monad law
f

And finally the important associativity law

mappend f (mappend g h)
≡ -- Definition of mappend
do
  x <- f
  y <- do
    x' <- g
    y' <- h
    return (x' <> y')
  return (x <> y)
≡ -- Monad law
do
  x <- f
  x' <- g
  y' <- h
  y <- return (x' <> y')
  return (x <> y)
≡ -- Monad law
do
  x <- f
  x' <- g
  y' <- h
  return (x <> (x' <> y'))
≡ -- Underlying monoid law
do
  x <- f
  x' <- g
  y' <- h
  return ((x <> x') <> y')
≡ -- Monad law
do
  x <- f
  x' <- g
  z <- return (x <> x')
  y' <- h
  return (z <> y')
≡ -- Monad law
do
  z <- do
    x <- f
    x' <- g
    return (x <> x')
  y' <- h
  return (z <> y')
≡ -- Definition of mappend
mappend (mappend f g) h

So for every (proper) Monad (and even for every applicative functor, as Jake McArthur pointed out on #haskell), there is a Monoid instance. It may or may not be the one that you are looking for.

Problem

Please excuse the terminology, my mind is still bending. The tree: ``` data Ftree a = Empty | Leaf a | Branch ( Ftree a ) ( Ftree a ) deriving ( Show ) ``` I have a few questions: If `Ftree` could not be `Empty`, would it no longer be a `Monoid` since there is no identity value. How would you implement `mappend` with this tree? Can you just arbitrarily graft two trees together willy nilly? For binary search trees, would you have to introspect some of the elements in both trees to make sure the result of `mappend` is still a BST? For the record, some other stuff `Ftree` could do here: ``` instance Functor Ftree where fmap g Empty = Empty fmap g ( Leaf a ) = Leaf ( g a ) fmap g ( Branch tl tr ) = Branch ( fmap g tl ) ( fmap g tr ) instance Monad Ftree where return = Leaf Empty >>= g = Empty Leaf a >>= g = g a Branch lt rt >>= g = Branch ( lt >>= g ) ( rt >>= g ) ```

Original source