confused about function as instance of Functor in haskell

25
votes

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

using Maybe a for example:

 fmap show (Just 1)
 result is : Just "1"

same as saying:

Just (show 1)

but when (->) is used as a Functor (in Control.Monad.Instances)

import Control.Monad.Instances
(fmap show Just) 1
result is : "Just 1"

that is, Just is applied first, then show is applied. In another example ,result is same:

 fmap (*3) (+100) 1
 result is 303

why not *3 first, then +100?

5
haskellfunctor

5 Answers

26
votes

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.

34
votes

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).

19
votes

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 = (.)
6
votes

fmap for (->) is defined like fmap = (.). So, (fmap f g) x is (f . g) x is f (g x). In your case (*3) ((+100) 1), which equals 3 * (100 + 1) which results in 303.

1
votes

In order to form a function type, you need 2 kind parameters for (->), that is the single input argument type and the return type.

A Functor can only take 1 type parameter, so you have to nail down the input argument type(since it's the first one from left to right), which makes the return type of the function to be the type parameter of the Functor.

So for function (the Functor) a->b, you need to give fmap a function ff of type b->xxx other than a->xxx to work, and that means the function ff can only be applied after a->b is apply.