Haskell - Mapping a function over a Rose Tree

Question

If I define a Rose tree as

data RTree = Node a [RTree a]
    deriving(Show, Eq)

How would I go about defining a map function for it? The map function is to be defined as

map_rose_tree :: (a -> b) -> RTree a -> RTree b

Answer 1

The easiest way is to enable the DeriveFunctor extension and derive Functor:

{-# LANGUAGE DeriveFunctor #-}

data RTree a
    = Node a [RTree a]
    deriving (Show, Eq, Functor)

map_rose_tree = fmap

But if you wanted to define the instance yourself you'll need to pattern match on the RTree constructor:

instance Functor RTree where
    fmap f (Node a children) = Node _ _

You'll have to fill in the two _ yourself. If you have a new enough version of GHC, you can compile this and get errors telling you the types of the holes (_) along with relevant bindings that you can use to implement it. The first hole is pretty easy, the second one is a little more challenging, but I assure you it can be solved with only fmap, f, a, and children.