I am reading "Category Theory for Programmers" By Bartosz Milewski and on pg. 164 he introduces a natural transformation for the Reader Functor:

newtype Reader e a = Reader (e -> a)

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

I am having a difficult time understanding the type signature of this transformation.

My best guess is something like:

fmap :: (a -> b) -> (Reader e -> a) -> (Reader e -> b)

I am confused that the functor is declared with Reader partially applied Reader e and then on line two there f and g which are the two function arguments. Then, there is a lambda expression with x. Since there is no value for x, I assume the Reader(\x -> ....) lambda expression is partially applied. Does x refer to some outside value? Where does e come into play?

So, how does the fmap instance satisfy fmap => (a->b) -> f a -> f b?

CodePudding user response：

No, here f ~ Reader e, so f a means Reader e a, and thus:

fmap @ Reader e :: (a -> b) -> Reader e a -> Reader e b

It thus will with a function f :: (a -> b) transform a Reader e a to a Reader e b.

Now for the pattern (Reader g), we know that g has type g :: e -> a, we thus need to produce a function e -> b. We can do that by creating a function that maps a variable x to g x, and then applies f on that result, such that \x -> f (g x) or shorter f . g has type f . g :: e -> b, which thus satisfies the type constraint.

CodePudding user response：

First, there are two separate constructors named Reader:

1. The type constructor with kind Type -> Type -> Type
2. The data constructor with type (a -> b) -> Reader a b.

Reader e is a partial application of the type constructor to get something with kind Type -> Type, which is suitable for defining a Functor instance.

Reader g is a pattern that matches a value of type Reader e a, which means g is bound to a value of type e -> a.

In order to construct a value of type Reader e b, we need to construct a value of type e -> b. We don't have access to a value of type b for that function to return, but we can get one using f :: a -> b. So, our function of type e -> b will take its e argument, pass it to g :: e -> a, and we'll pass that result to f.

It's slightly easier to see when you expand Reader to the function types, and write them in prefix (rather than infix) order.

fmap :: (a -> b) -> Reader e a -> Reader e b
     -- by isomorphism of Reader e x and e -> x
     :: (a -> b) -> (e -> a) -> (e -> b)
     -- using prefix notation
     :: (a -> b) -> ((->) e) a -> ((->) e) b
     -- generalizing from a specific functor to an abstract functor
     :: (a -> b) -> f a  -> f b

where f is the functor (->) e or Reader e whose instance we are defining.