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 )
From HaskellWiki. In Haskell, the Monoid typeclass (not to be confused with Monad) is a class for types which have a single most natural operation for combining values, together with a value which doesn't do anything when you combine it with others (this is called the identity element).
Functors and monoids were both wrappers around a value that allow us to execute operations on them. In the case of functors it was map in the case of monoids it was compose , where compose is a single operation. Now monads. Monad's are both a functor and a monoid.
Strings, lists, and sequences are essentially the same monoid. An introduction for object-oriented programmers. This article is part of a series about monoids. In short, a monoid is an associative binary operation with a neutral element (also known as identity).
There are three answers to your question, one captious and one unhelpful and one abstract:
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.
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...
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With