Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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 )
like image 226
xiaolingxiao Avatar asked Feb 24 '13 18:02

xiaolingxiao


People also ask

What are Monoids in Haskell?

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

Are functors Monoids?

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.

Is list 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).


1 Answers

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.

like image 161
Joachim Breitner Avatar answered Oct 13 '22 22:10

Joachim Breitner