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.

CodePudding user response：

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.

CodePudding user response：

With

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

to get that (a->b) applied to that a in the context f, we need to operate in the context g.

And that's just fmap.

It's clearer with the flipped signature, focusing on its last part

flip nestedApply :: (Applicative f, Applicative g) 
            =>    f  a 
            -> g (f (a -> b))     --- from here
            -> g (f       b )     --- to here

So what we have here is

nestedApply gffun fx = fmap (bar fx) gffun

with bar fx being applied under the g wraps by fmap for us. Which is

bar fx ::         f (a -> b)
            ->    f       b   

i.e.

bar ::            f  a
            ->    f (a -> b)
            ->    f       b   

and this is just <*> isn't it, again flipped. Thus we get the answer,

nestedApply gffun fx  =  fmap (<*> fx) gffun

As we can see only fmap capabilities of g are used, so we only need

nestedApply :: (Applicative f, Functor g) => ...

in the type signature.

It's easy when writing it on a sheet of paper, in 2D. Which we imitate here with the wild indentation to get that vertical alignment.

_{Yes we the humans learned to write first, on paper, and to type on a typewriter, much later. The last generation or two were forced into linear typing by the contemporary devices since the young age but now the scribbling and talking (and gesturing and pointing) will hopefully be taking over yet again. Inventive input modes will eventually include 3D workflows and that will be a definite advancement. 1D bad, 2D good, 3D better. For instance many category theory diagrams are much easier to follow (and at least imagine) when drawn in 3D. The rule of thumb is, it should be easy, not hard. If it's too busy, it probably needs another dimension.}

Just playing connect the wires under the wraps. A few self-evident diagrams, and it's done.

Here's some type mandalas for you (again, flipped):

-- <$>               -- <*>               -- =<<
f     a              f     a              f     a       
     (a -> b)        f    (a -> b)             (a -> f b)
f          b         f          b         f    (     f b)   -- fmapped, and
                                          f            b    -- joined

and of course the mother of all applications,

--      $
      a
      a -> b
           b

a.k.a. Modus Ponens _{(yes, also flipped)}.