CODEWITHSUNDEEP
haskellmonoids
Bercovici Adrian
Bercovici Adrian

Reputation: 9360

Getting identity for type parameter?

I have the following type that i want to be an instance of Monoid typeclass.I do not know how to set a parametrized field to the identity.Is there any way when using parametrized type to get the identity of that type ?

data Tree a=Leaf a | Node a (Tree a) (Tree a) |Empty deriving (Eq,Show)

instance Monoid Tree where
    mempty=Empty
    mappend a Empty=a
    mappend a b=Node (identity) x y

As you can see i need the simple field to be set to the identity of the parameter type.

Example

mappend::Tree Int
mappend (Leaf 1) (Leaf 2)=Node 0 (Leaf 1) (Leaf 2)

mappend::Tree []
mappend (Leaf [1,2])(Leaf [2,3])=Node [] (Leaf [1,2])(Leaf [2,3])

Upvotes: 1

Views: 80

Answers (2)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476699

This can only happen if a itself is a Monoid type as well, so we can write this as:

instance Monoid a => Monoid (Tree a) where
    mempty = Empty
    mappend Empty a = a
    mappend a Empty = a
    mappend a b = Node mempty a b

The above will not work for an Int, since an Int is not a Monoid. There are two very popular candidates (ℕ, +, 0), and (ℕ, ×, 1). You can however make use of Sum which is the representation of the former monoid.

The mempty in the body of the last line is thus not the mempty we are defining, but the mempty of type a.

That being said, if you define a Monoid Tree like that, it means that you consider a Node mempty (Node mempty a b) c == Node mempty a (Node mempty b c), since this is required by the monoid laws. So the deriving Eq is not completely in "harmony" here with the mappend. The mappend operator (in mathematics typically denoted as ⊕), should satisfy the condition ∀ a,b,c∈ S: a⊕(b⊕c) = (a⊕b)⊕c.

You either should implement Eq yourself differently, or you should try to come up with another structure for your monoid.

Upvotes: 9

dfeuer
dfeuer

Reputation: 48591

This is not an answer, but it's far too long for a comment. As Willem Van Onsem suggests, your Monoid instance isn't lawful. I suspect you probably want one of two things:

A free magma

The free magma over a type can be defined

data Magma a = Branch (Magma a) (Magma a) | Leaf a | Empty
  deriving Show

This isn't naturally a monoid, but it's sometimes useful to pretend it's one:

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

-- For recent GHC, add this instance
instance Semigroup (Magma a) where
  (<>) = Branch

This can be used with a fold to gain insight into the structure of that fold. To get a sense of how this works, compare the results of applying foldMap Leaf to [1..20], Data.Sequence.fromList [1..20], and Data.Set.fromList [1..20].

A (particular) free monad

Consider generalizing your tree to allow different types in the internal nodes than in the leaves:

data Tree a b = Node a (Tree a b) (Tree a b) | Leaf b
  deriving (Show, Eq)

(This turns out to be the free monad over the functor Tree a, defined

data TreeF a b = NodeF a b b

but we don't really need to get into the details of what that means.)

The monad operation for the Tree a monad is a sort of "grafting", where the leaves are replaced by trees.

instance Functor (Tree a) where
  fmap f (Leaf b) = Leaf (f b)
  fmap f (Node a l r) = Node a (fmap f l) (fmap f r)

instance Applicative (Tree a) where
  pure = Leaf
  (<*>) = ap
  liftA2 = liftM2

instance Monad (Tree a) where
  Leaf b >>= f = f b
  Node a l r >>= f = Node a (l >>= f) (r >>= f)

You can think of >>= as supporting a sort of vertical appending, where the tree grows downward from its leaves.

Upvotes: 2

Related Questions