3

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.

3
  • 1
    You did not define the empty case, nor did you apply f on a for the Branch case. Mar 1, 2018 at 7:37
  • 1
    For future questions: usually it is advisable to copy paste the exact compiler message. By looking at the message, you can usually already get a good idea what is wrong. Mar 1, 2018 at 8:03
  • By the way, GHC can now derive Functor instances as well, if you require deriving (....,Functor) and enable a GHC extension. It is still a good beginner exercise to code such instances by hand, since that will make you more familiar with the behavior of fmap for your functors.
    – chi
    Mar 1, 2018 at 10:55

2 Answers 2

8

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

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)
2
  • 1
    I can imagine a use for distinguishing between Leaf x and Branch x Empty Empty; the former may not be converted to an interior node by an insert function, while the latter may. It depends on what you want to model. At best, I would put the alternate definition at the end of the answer, or omit it altogether.
    – chepner
    Mar 1, 2018 at 16:58
  • @chepner Fair enough. Mar 1, 2018 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.