CODEWITHSUNDEEP
haskell
Haskell-newb
Haskell-newb

Reputation: 149

Haskell - fmap and foldMap for Tree

im new to haskell and im a bit stuck i have 

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

I want to crate an fmap and a foldMap , so i tried 

instance Functor Tree where
    fmap f (Leaf x) = Leaf (f x)
    fmap f (Branch a left right) = Branch a (fmap f left) (fmap f right)

and it simply doesn't work and i don't understand why , i'm pretty sure the problem is here 

.. = Branch a (fmap f left) (fmap f right)

anyway i could really use some help for the fmap and foldMap ,actually i have an idea but i don't have the right syntax.

thanks for the help.

Upvotes: 3

Views: 1831

Answers (2)

user4601931
user4601931

Reputation: 5285

As an aside, I think that your data declaration maybe isn't quite right (or rather is not standard). Typically one defines

data Tree a = Nil | Node a (Tree a) (Tree a)

That is, a Tree is either an empty node (Nil), or a Node that contains a value and two subtrees. In this way, you can represent a nonempty tree with no branches as Node a Nil Nil.

Anyway, to properly define the Functor instance for this type (the instance for your Tree type is similar), you need to define fmap :: (a -> b) -> Tree a -> Tree b for the all the possible values of type Tree a -- in this case, the empty value and the nonempty value. You're on the right track with your implementation, but you forgot to apply f to the value contained in the nonempty node:

instance Functor Tree where
  fmap _ Nil = Nil -- nothing to fmap in this case
  fmap f (Node a left right) = Node (f a) (fmap f left) (fmap f right)

Upvotes: 3

Nicola Gigante
Nicola Gigante

Reputation: 3266

You are forgetting to apply the function f on the as contained in the Branch nodes as well, otherwise you only apply the function on the leaves. Moreover, you are forgetting a case for the Empty constructor.

instance Functor Tree where
  fmap f Empty = Empty
  fmap f (Leaf x) = Leaf (f x)
  fmap f (Branch a left right) = Branch (f a) (fmap f left) (fmap f right)

Upvotes: 8

Related Questions