In Haskell how to "apply" functions in nested context to a value in context?

Question

nestedApply :: (Applicative f, Applicative g) => g (f (a -> b)) -> f a -> g (f b)

As the type indicates, how to get that (a->b) applied to that a in the context f?

Thanks for help.

Answer 1

This one of those cases where it's helpful to focus on types. I will try to keep it simple and explain the reasoning.

Let's start with describing the task. We have gfab :: g(f(a->b)) and fa :: f a, and we want to have g(f b).

gfab :: g (f (a -> b))
fa   :: f a
??1  :: g (f b)

Since g is a functor, to obtain type g T we can start with a value ??2 of type g U and apply fmap to ??3 :: U -> T. In our case, we have T = f b, so we are looking for:

gfab :: g (f (a -> b))
fa   :: f a
??2  :: g U
??3  :: U -> f b
??1 = fmap ??3 ??2  :: g (f b)

Now, it looks like we should pick ??2 = gfab. After all,that's the only value of type g Something we have. We obtain U = f (a -> b).

gfab :: g (f (a -> b))
fa   :: f a
??3  :: f (a -> b) -> f b
??1 = fmap ??3 gfab :: g (f b)

Let's make ??3 into a lambda, \ (x :: f (a->b)) -> ??4 with ??4 :: f b. (The type of x can be omitted, but I decided to add it to explain what's going on)

gfab :: g (f (a -> b))
fa   :: f a
??4  :: f b
??1 = fmap (\ (x :: f (a->b)) -> ??4) gfab :: g (f b)

How to craft ??4. Well, we have values of types f (a->b) and f a, so we can <*> those to get f b. We finally obtain:

gfab :: g (f (a -> b))
fa   :: f a
??1 = fmap (\ (x :: f (a->b)) -> x <*> fa) gfab :: g (f b)

We can simplyfy that into:

nestedApply gfab fa = fmap (<*> fa) gfab

Now, this is not the most elegant way to do it, but understanding the process is important.