How does <*> work with Function Applicative?

Question

I am trying to figure out with lambda calculus why the function result of the following code

(,) <$> (+1) <*> (+1)

has type Num a => a -> (a, a) instead of Num a => a -> a -> (a, a)

This is what I have got, am I doing something horribly wrong or is <*> just wired this way?

( \x, y -> (,) x y ) <$> ( \x -> x + 1 ) <*> ( \x -> x + 1 )

-- fmap applies first

(\x y -> (,) ((+1) x) y ) <*> ( \x -> x + 1 ) -- substituted the lambda with (+1) for better clarity

-- then goes apply

( \x y -> (,) ((+1) x) ((+1) y) )

how do the parameters of the lambda unify and at what point?

Answer 1

Let's see types in your example:

(,)            <$> (+1)            <*> (+1)
^                  ^                   ^
|                  |                   |
a -> b -> (a, b)   Num a => a -> a     Num a => a -> a

Rhs of (<$>) and Rhs/Lhs of (<*>) must be the Applicative Functor. Your functor is Num a => (->) a (the monad Reader).

So, what type will be after (<$>) application (Pseudo code):

a -> b -> (a, b) <$> Num a => (->) a a ==> Num a => (->) a (b -> (a, b))

After (<*>) (Pseudo code):

Num a => (->) a (b -> (a, b)) <*> Num a => (->) a a ==> Num a => (->) a (a, a)

But Num a => (->) a (a, a) is equivalent with Num a => a -> (a, a).

---

As @chi wrote at head, the implementation (<*>) for type (->) r is:

(<*>) :: (->) r (a -> b) -> (->) r a -> (->) r b
f <*> g = \r -> f r (g r)

And, if you apply, you'll get:

(\x y -> (,) x y) <$> (\r -> r + 1) <*> (\r -> r + 1) =
= (\r y -> (,) (r + 1) y) <*> (\r -> r + 1) =
= \r -> (,) (r + 1) (r + 1)