I have this data type:

data F a b = F (a -> b)

My task is to make this type an instance of the Functor class. I understand how to do this with the usual examples. i.e. Maybe.

Usually, the given function is applied to the value which is extracted from the wrapper. Then the result is replaced in the same wrapper type. The wrapper in the case of the Maybe type being Just.

However, my data type represents a function of type a -> b. I don't understand how to transfer this concept to use a wrapped function. The reason to create this data type as well as the way to implement this idea are both lost on me.

I'm assuming I'm not fully understanding the concept behind functors or just missing the intention behind the given task where I must specifically define and use the custom data type above...

Please help me to correct the following...

instance Functor (F a) where

CodePudding user response：

A function is already an instance of Functor. So you can make use of the DeriveFunctor extension:

{-# LANGUAGE DeriveFunctor #-}

data F a b = F (a -> b) deriving Functor

if you want to manually implement an instance of functor, you can look at the types. If you are implementing this for a function, then the signature of fmap should be:

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

and thus for f ~ (->) a, this means:

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

or more compact:

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

there is only one straightforward implementation for such fmap. If you are then implementing this for instance Functor (F a), the only difference is to unwrap the function from the F data constructor and wrap the result back in an F data constructor.

CodePudding user response：

I think the other answers address how to write an instance once you know what instance you want to write, but don't give a very good intuition for working out what instance you should want to write in the first place. In this answer, I'll attempt to do that.

I'm going to start very simple. The simplest thing that could possibly be: a functor that doesn't even have any values in it is really, really easy to fmap over.

data F0 a = F0
instance Functor F0 where fmap f F0 = F0

Okay, let's step up our game slightly. What if we've got one value? Well, we just apply our function to that value. Sensible.

data F1 a = F1 a
instance Functor F1 where fmap f (F1 a0) = F1 (f a0)

Once we get to two values, it may not be blindingly obvious what should happen. But I'm going to claim that the most natural thing is to apply the incoming function to both values:

data F2 a = F2 a a
instance Functor F2 where fmap f (F2 a0 a1) = F2 (f a0) (f a1)

With three, we want to apply f to all the values:

data F3 a = F3 a a a
instance Functor F3 where fmap f (F3 a0 a1 a2) = F3 (f a0) (f a1) (f a2)

The pattern continues like this: no matter how many as one of these types contain, the right thing for fmap to do is to apply f to all of them.

In fact, the pattern is so regular, that I think we can abstract it. Let's write types that have zero, one, two, three, and so on values (rather than fields). So:

data N0
data N1 = N1_0
data N2 = N2_0 | N2_1
data N3 = N3_0 | N3_1 | N3_2

These types aren't parameterized at all. Rather than being the collection of values, like F3 a was, an N3 is just an index. In fact, if we wanted, we could write an indexing function:

index3 :: F3 a -> N3 -> a
index3 (F3 a0 a1 a2) n = case n of
    N3_0 -> a0
    N3_1 -> a1
    N3_2 -> a2

This is kind of frustrating, though. We need a new indexing function for each size. It would be nice if things were a bit more uniform -- once we have a type for indices, we'd like to automatically get a container with those values as indices. How can we do that? Well, one way is to just store the indexing function itself; a pre-applied version of index3, for example. So, for our new type F, we'll have

F N3 a ~= N3 -> a

and our new size-independent indexing will just return that function. As a quick example, where before we might have written x = F3 5 16 (-92), now we'll write something like this:

x ~= \n -> case n of
   N3_0 -> 5
   N3_1 -> 16
   N3_2 -> (-92)

You can see how this might be thought of as a pre-applied index. Thinking about fmap quickly, we can use our definition from above: fmap f (F3 a0 a1 a2) = F3 (f a0) (f a1) (f a2). So:

fmap f x ~= \n -> case n of
    N3_0 -> f 5
    N3_1 -> f 16
    N3_2 -> f (-92)

You might want to pause here and think about how you might write a function that did this transformation on x for some specific f like \v -> v 1 or so. So it would have a type like foo :: (N3 -> Int) -> (N3 -> Int). Note that foo shouldn't have to do any pattern matching; x, which we are going to pass in to foo as its first argument, already has the pattern match of interest in it, so foo should be able to use x as its "pattern matcher".

Let's write down our new type:

data F n a = F (n -> a)

Okay. Now I've led you down the garden path, and we can have a grounded thought about what the functor instance should do. It should apply the incoming function to all the values, no matter their index!

With that intuition, I suspect the instance itself will come quite naturally (though perhaps not easily! it can be hard to figure out what the natural choice is).

instance Functor (F n) where
    fmap f (F index) = F (\n -> {- ... -})