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

Question

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:

1. If Ftree could not be Empty, would it no longer be a Monoid since there is no identity value.

2. How would you implement mappend with this tree? Can you just arbitrarily graft two trees together willy nilly?

3. 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 )

Answer 1

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.