Derive Haskell type and implementation of (<*>)(<*>)

Question

I am a rookie just start learning Haskell so please bear with me if I am asking stupid questions.

Recently I come across questions in SO demonstrating how to deriving type and implementation of functions & expression (questions such as

How can I understand "(.) . (.)"?

&

Haskell function composition, type of (.)(.) and how it's presented )

I find the answers very inspiring

I, then, try to come up some exercises for myself to make sure I know how to apply those techniques.

Then I come up with this expression myself: (<*>)(<*>) which I don't know how to solve.

In GHCi, it gives the type signature as:

(<*>)(<*>) :: Applicative f => (f (a -> b) -> f a) -> f (a -> b) -> f b

but my problem is how could I start from

(<*>) :: Applicative f => f (a -> b) -> f a -> f b

and derive the type signature as given by GHCi?

Furthermore, based on the type signature, how the implementation of (<*>)(<*>) = ?? would be?

I am stuck and cannot resolve this by techniques such as re-arranging terms, etc. I don't even have a clue on where to start with.

Would somebody give me a help?

Thanks a lot

note** : the expression (<*>)(<*>) really does not bear special meanings, it's just an exercise I come up for myself randomly

Answer 1

First of all, let's write out the type of (<*>) with two disjoint set of type variables:

(<*>) :: (Applicative f) => f (a -> b) -> f a -> f b
(<*>) :: (Applicative g) => g (c -> d) -> g c -> g d

If we want to use the second one with the first one as its argument, we need

g (c -> d) ~ f (a -> b) -> f a -> f b

yielding

g ~ (f (a -> b) ->)    or,   ((->) (f (a -> b)) )
c ~ f a
d ~ f b

and note that the choice of g is indeed an applicative functor: it's the un-newtyped Reader (f (a -> b)) applicative.

And so the application has type

g c -> g d

which we now know to be

(f (a -> b) -> f a) -> (f (a -> b) -> f b)

q.e.d.

Answer 2

As an exercise, narrowing it to functions, where <*> is just an S-combinator,

Prelude> let s f g x = f x (g x)

Prelude> :t s s
s s :: ((t -> t1 -> t2) -> t -> t1) -> (t -> t1 -> t2) -> t -> t2
--               g2          g4                 g2          g1
--         g3                             g3
--                      g5
--                                  g6

It is important to know that arrows in types associate to the right, so ((t -> t1 -> t2) -> t -> t1) is actually ((t -> t1 -> t2) -> (t -> t1)), and (t -> t1 -> t2) is (t -> (t1 -> t2)).

The implementation:

g6 g5 g3 t :: t2 
  g3 t t1 :: t2          -- need t1
  g5 g3 t :: t1
  g3 t (g5 g3 t) :: t2   -- so, 

h f g x = g x (f g x)    

So, when we have a type, it's just a matter of connecting the wires so to speak, or putting the Lego bricks together. We try and see which combinations of the given entities (arguments) have what type, and use them in further combinations if they are useful to get to the desired output type (t2, above).

Similarly,

Prelude Control.Applicative> :t (<*>) (<*>)
(<*>) (<*>) :: (Applicative f) =>
               (f (a -> b) -> f a) -> f (a -> b) -> f b
--                         f          fg
Prelude Control.Applicative> :t let axa f fg = fg <*> f fg in axa
let axa f fg = fg <*> (f fg) in axa :: (Applicative f) =>
                                       (f (a -> b) -> f a) -> f (a -> b) -> f b

Answer 3

Furthermore, based on the type signature, how the implementation of (<*>)(<*>) = ?? would be?

It's easier to reverse the order (find the implementation first, and then derive its type).

Applicative instance for functions is

instance Applicative ((->) a) where
    pure = const
    (<*>) f g x = f x (g x)

So simply by substituting <*> for f in the above definition, (<*>) (<*>) is \g x -> x <*> g x. Or after alpha-conversion \g h -> h <*> g h.

Since the first argument of (<*>) is h, is must be of type h :: f (a -> b) for some a and b, where f is in Applicative.

Since g receives h as an argument, it must be of type g :: f (a -> b) -> c, for some c.

Since the first argument of (<*>), h, has type f (a -> b) and the second argument of (<*>) is g h, its type must be g h :: f a, due to the fact, that

(<*>) :: f (a -> b) -> f a -> f b

Since g :: f (a -> b) -> c and g h :: f a,

h :: f (a -> b)
g :: f (a -> b) -> c
g h :: f a               ,  c ~ f a   (!)

Since h has type f (a -> b), h <*> (whatever :: f a) has type f b.

And altogether:

h         :: f (a -> b)
g         :: f (a -> b) -> f a
h <*> g h :: f b

So we have

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