Flip functor instance Haskell

Question

I need to write the Functor instances for the Flip datatype:

data K a b = K a
newtype Flip f a b = Flip (f b a) deriving (Eq, Show)

instance Functor (Flip K a) where
fmap=undefined

The solution I was given in class is:

instance Functor (Flip K a) where
    fmap f (Flip (K b)) = Flip (K (f b))

I really don't understand what's going on here and I'm beginning to doubt my whole understanding of data types and functors. What I do understand is this (please correct me if any of this is wrong):

• K is a data type that turns 2 parameters into a structure K a ( that only keeps the first parameter)
• Flip is a datatype that turns 3 arguments into a structure with one
• Because in fmap :: (a-> b) -> f a -> f b, f a has kind *, to write the Functor instance of Flip, we write it on the last type in Flip. Aka f and a are "constants" in a way, and we write the functor for the type b. I would write something like:

instance Functor (Flip f a) where
   fmap f (Flip x y z) = fmap Flip x y (f z)

I know that that is completely wrong but I'm not sure why.

Also, why would we bring K into the Functor instance of Flip? Can someone explain thoroughly the process of coming up with this solution and why it is correct?

Answer 1

• K is a data type that turns 2 parameters into a structure K a ( that only keeps the first parameter)

This isn't quite right. K a b is a data type formed using two parameters, but it's not really right to say that it "turns them into" anything. Instead, it's simply just stating to the world that there now exists a new type: K a b. "So what?" you might ask. Well, the second half of the data type defines how to make new values of this type. That part says, "You can make a new value of type K a b with this function I'll call K which has type a -> K a b." It's really important to recognize that there is a distinction between the type K and the constructor K.

So, it's not that K "only keeps the first parameter"—it's that the constructor K (which is a function) happens to not take any arguments of type b.

---

• Flip is a datatype that turns 3 arguments into a structure with one

Just as above, this is not quite right. The Flip declaration states that there can be values of type Flip f a b, and the only way to make them is by using the constructor Flip that has type f b a -> Flip f a b.

In case you're wondering how I'm coming up with the type signatures for the constructors K and Flip, it's not actually mysterious, and you can double check by typing :t K or :t Flip into GHCi. These types are assigned based entirely on the right hand side of the data type declaration. Also, note that the type name and constructor don't have to be the same. For instance, consider this data type:

data Foo a = Bar Int a | Foo String | Baz a a

This declares a type Foo a with three constructors:

Bar :: Int -> a -> Foo a
Foo :: String -> Foo a
Baz :: a -> a -> Foo a

Basically, each of the types after the constructor name are the arguments, in order, to the constructor.

---

• Because in fmap :: (a-> b) -> f a -> f b, f a has kind *, to write the Functor instance of Flip, we write it on the last type in Flip. Aka f and a are "constants" in a way, and we write the functor for the type b.

This is basically right! You could also say that f has kind * -> *. Since Flip has kind (* -> *) -> * -> * -> *, you need to provide it two type arguments (the first of kind * -> * and the second of kind *) to get it to the right kind. Those first two arguments become fixed ("constants" in a way) in the instance.

---

I would write something like: ... I know that that is completely wrong but I'm not sure why.

The reason your instance is completely wrong is that you've mixed up the type with the constructor. It doesn't make sense to put (Flip x y z) in the pattern position where you did because the constructor Flip only takes one argument—remember, it's type is Flip :: f b a -> Flip f a b! So you'd want to write something like:

instance Functor (Flip f a) where
   fmap f (Flip fxa) = ...

Now, what do you fill in for the ...? You have a value fxa :: f x a, and you have a function f :: x -> y, and you need to produce a value of type f y a. Honestly, I don't know how to do that. After all, what is a value of typ f x a? We don't know what f is?!

---

Also, why would we bring K into the Functor instance of Flip? Can someone explain thoroughly the process of coming up with this solution and why it is correct?

We saw just above that we can't write the Functor instance for an arbitrary f, but what we can do is write it for a particular f. It turns out that K is just such a particular f that works. Let's try to make it work:

instance Functor (Flip K a) where
  fmap f (Flip kxa) = ...

When f was arbitrary, we got stuck here, but now we know that kxa :: K x a. Remember that the only way to make a value of type K x a is using the constructor K. Therefore, this value kxa must have been made using that constructor, so we can break it apart as in: kxa ⩳ K x' where x' :: x. Let's go ahead and put that into our pattern:

  fmap f (Flip (K x')) = ...

Now we can make progress! We need to produce a value of type Flip K a y. Hmm. The only way to produce a value of type Flip is using the Flip constructor, so let's start with that:

  fmap f (Flip (K x')) = Flip ...

The Flip constructor at type Flip K a y takes a value of type K y a. The only way to produce one of those is with the K constructor, so let's add that:

  fmap f (Flip (K x')) = Flip (K ...)

The K constructor at type K y a takes a value of type y, so we need to provide a value of type y here. We have a value x' :: x and a function f :: x -> y. Plugging the first into the second gives us the value we need:

  fmap f (Flip (K x')) = Flip (K (f x'))

Just rename x' to b, and you have exactly the code your teacher provided.