Defining fmap for a RoseTree-CodePudding

I'm trying to write a Functor instance for RoseTree datatype.

data Rose a = MkRose a [Rose a]
    deriving (Eq, Show)

instance Functor Rose where

fmap f (MkRose a children) = MkRose (f a) (fmap f children)

I really thought this would work but I get :

Expected type: [a]

Actual type: [Rose a]

for children, could anyone explain to me where I went wrong?

CodePudding user response：

data Rose a = MkRose a [Rose a]
    deriving (Eq, Show)


instance Functor Rose where
  fmap f (MkRose a []) = MkRose (f a) []
  fmap f (MkRose a roses) = MkRose (f a) ((fmap . fmap) f roses)

The problem you are facing is due to the fact that the children of Rose are packed away in an additional data structure, namely the list []. So you have a recursive data structure that at each step has infinitely many branches, e.g. recursion paths. In other words, it's not one path like in a list, it's not only 2 or three paths like in a binary tree or similar where the branches are normally named with specific data constructors, but each node can have infinitely many children.

So, you need to drill down to access the values you are seeking by using an fmap . fmap construct. The right fmap (for which there is a built-in Functor provided by the ghc, goes over each element of the list and passes them over to the left fmap which drills into the MkRose values for which you have written the Functor.

If you look at the signature of fmap you have:

fmap :: Functor f => (a -> b) -> f a -> f b

Applying this to [] gives:

fmap @[] :: (a -> b) -> [a] -> [b]

This is the signature of the right fmap in fmap . fmap in our case.

Similarly, applying fmap to Rose gives the signature:

fmap @Rose :: (a -> b) -> Rose a -> Rose b

The composition of these 2 guys gives the output of the right one as input to the left one and the left one acts with f on its input which are roses.

CodePudding user response：

When f :: a -> b, fmap f has type F a -> F a for any one functor F of our choice. For example, we might use it as

fmap f :: [a] -> [b]
fmap f :: Rose a -> Rose b   -- in recursive calls
fmap f :: Maybe a -> Maybe b
fmap f :: IO a -> IO b
...

You get the point, I think. However, if we have two functors, then fmap f alone does not suffice. For instance we do NOT have

fmap f :: Maybe [a] -> Maybe [b]

because fmap only works with a single functor, while here we have two (Maybe and []). If we need to work with nested functors, we need to fmap more:

f             :: a -> b
fmap f        :: [a] -> [b]               -- add []
fmap (fmap f) :: Maybe [a] -> Maybe [b]   -- add Maybe

In your case, you need something of type [Rose a] -> [Rose b], which involves two functors, so you also have to fmap twice.