I have this data type:

data Arf a = Ser a [Arf a] deriving Show

When instantiating Functor this code works:

instance Functor Arf where
    fmap f [] = []
    fmap f (Ser x xs) = Ser (f x) (map (fmap f) x)

Why is (map (fmap f) x) used instead of (fmap f x) in the second argument to Ser?

CodePudding user response：

I think there's a typo in your code: at the very end of the last line, it should be xs instead of x.

With that out of the way, let's discuss the maps.

The inner fmap maps the function f over the Arf a type. So you might observe that in this case:

fmap f :: Arf a -> Arf b

But those Arf a values are in a list! So how do you apply a function that transforms a single Arf a value to a whole list of those values? With map of course!

So the outer map applies to the whole list:

map (fmap f) :: [Arf a] -> [Arf b]

CodePudding user response：

(Fixing as per Fyodor's comment...)

Why is (map (fmap f) xs) used instead of (fmap f xs) in the second argument to Ser?

What is the second argument to Ser? It's a [Arf a], i.e. a list of Arfs.

How do you apply f to the elements in the xs list? You do map ??? xs...

But what is the ??? function?

Well, you want it to apply f to the inside those Arfs, so you need it to call recursively the same fmap function that you are defining, hence ??? === fmap f.

Therefore map (fmap f) xs.