confused about function as instance of Functor in haskell

the type of fmap in Functor is:

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

it looks like ,first apply function (a -> b) to the parameter of f a to create a result of type b, then apply f to it, and result is f b

That is the type of fmap, but your interpretation of what that type means is wrong.

You seem to assume that f a has one parameter, and that that parameter has type a.

Consider xs :: [a]:

• Perhaps xs = [].
• Perhaps xs = [x1].
• Perhaps xs = [x1, x2].
• ...

The type f a is a functor f with a single type parameter a. But values of type f a do not necessarily take the form F x, as you can see from the first and third cases above.

Now consider fmap f xs:

• Perhaps fmap f xs = [].
• Perhaps fmap f xs = [f x1].
• Perhaps fmap f xs = [f x1, f x2].
• ...

We don't necessarily apply f at all (first case)! Or we might apply it more than once (third case).

What we do is replace the things of type a, with things of type b. But we leave the larger structure intact --- no new elements added, no elements removed, their order is left unchanged.

---

Now let's think about the functor (c ->). (Remember, a functor takes one type parameter only, so the input to (->) is fixed.)

Does a c -> a even contain an a? It might not contain any as at all, but it can somehow magic one out of thin air when we give it a c. But the result from fmap has type c -> b: we only have to provide a b out of that when we're presented with a c.

So we can say fmap f x = \y -> f (x y).

In this case, we're applying f on demand --- every time the function we return gets applied, f gets applied as well.

It needs to be defined that way to make the types work out. As you pointed out, the type of fmap is:

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

Let's consider the case when the functor f is ((->) c)

(Note: we'd actually like to write this as (c ->), i.e. functions from c, but Haskell doesn't allow us to do this.)

Then f a is actually ((->) c a), which is equivalent to (c -> a), and similarly for f b, so we have:

fmap :: (a -> b) -> (c -> a) -> (c -> b)

i.e. we need to take two functions:

• f :: a -> b
• g :: c -> a

and construct a new function

• h :: c -> b

But there's only one way to do that: you have to apply g first to get something of type a, and then apply f to get something of type b, which means that you have to define

instance Functor ((->) c) where
    fmap f g = \x -> f (g x)

or, more succinctly,

instance Functor ((->) c) where
    fmap = (.)

The fmap instance for (->) r (i.e. functions) is literally just composition. From the source itself:

instance Functor ((->) r) where
    fmap = (.)

So, in your example, we can just replace fmap with (.), and do some transformations

fmap (*3) (+100) 1 => 
(.) (*3) (+100) 1  =>
(*3) . (+100) $ 1  => -- put (.) infix
(*3) (1 + 100)     => -- apply (+100)
(1 + 100) * 3         -- apply (*3)

That is, fmap for functions composes them right to left (exactly the same as (.), which is sensible because it is (.)).

To look at it another way (for (double) confirmation!), we can use the type signature:

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

-- specialised to the function functor (I've removed the last pair of brackets)
fmap :: (a -> b) -> (r -> a) -> r -> b 

So first the value of type r (the third argument) needs to be transformed into a value of type a (by the r -> a function), so that the a -> b function can transform it into a value of type b (the result).