f <*> g = \x -> f x (g x)

Trying to understand functions as Applicatives

Erk…this is hard, but I feel necessary to really get a grip with recursion and how Haskell defines types.

This is based on this stack overflow discussion.

So…I don’t really understand the formula in the title. It’s the instance definition of <*> for functions as Applicatives in Haskell, and it is used to chain together functions so that their results are applied in an equation, like so:

> f = (+) <$> (+3) <*> (*100)
> f 5 -- => 508

The (+) function takes two parameters. These are captured from (+3) and (*100) which are applied to the value 5 to give (+) 8 500 returning 508.

I have found this one baffling to decipher on my own, but with a little help from some learned people on StackOverflow I think I might be able to explain their explanations (and thereby get a little closer to understanding the function!).

The <*> function has the following signature:

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

So, at the most abstract level we provide a functor that contains an equation and another functor that contains a value and the equation in the first functor is applied to the value in the second functor. OK, makes sense.

The instance type definition is: Applicative ((->) r)

Specialising to (->) r we are saying that the functor is a function with one parameter. So from the signature above we now have

Applicative ((->) r) => ((->) r) (a -> b) -> ((->) r) a -> ((->) r) b

Which is dizzying, but reads as follows ( starting from the => ):
A function that takes one parameter, r and returns an equation from a to b, ->,a function that takes one parameter and returns a value of a, -> return an equation that takes one parameter and returns a value of type b. The type r and a are equivalent since both equations are constrained to take the type-variable r and both must accept a single parameter of type a.

So in the definition of <*> that reads:

f <*> g = \x -> f x (g x)

So:
* f is a function that returns a function, and takes a parameter of type r
* g is a function that returns a value and takes a parameter of type r
* x is a value of type r

Now, what confused me to no end was that I thought that f x (g x) meant that you supplied to 2 parameters to f, x and the value of g x. It doesn’t - this is the trick - f is a function that takes a parameter (x) and returns another function. Call this function f1. So once f has been called with x it is replaced with a function that accepts a value of type r. So the equation now looks like this:

f <*> g = \x -> f1 (g x)

Next, g is called with x. Remember g is a function that returns a value of type r, which is the same type as x and the same type that is accepted by f1. Call the value returned by g as v. The function now appears as follows:

f <*> g = \x -> f1 v

Finally f1 v is resolved to return the value of the function.

So how does this work from the perspective of a multi-function scenario such as the following?

(+) <$> (+3) <*> (*100) $ 5

Now, the <*> and <$> operators have left associativity meaning we can rewrite the above as follows:

((+) <$> (+3)) <*> (*100) $ 5

or even

(fmap (+) (+3)) <*> (*100) $ 5

Remember <$> is just an infix alias for fmap.

Which resolves to:

(\x -> (+) ((+) 3 x)) <*> (*100) $ 5

or

(\x -> (+) (3 + x)) <*> (*100) $ 5

So if we plug the above back into \x -> f x (g x) where f is (\x -> (+) ((+) 3 x)) we get the following (I’ve changed the x in the second equation into y for clarity):

\x -> ((\y -> (+) (3 + y)) x) (100 * x)

So that’s pretty boggling. Let’s make it easier by substituting x for 5 as per the example:

\5 -> ((\y -> (+) (3 + y)) 5) (100 * 5)

Which simplifies to:

\5 -> ((\y -> (+) (3 + y)) 5) (500)

and then by substituting y with 5 and simplifying resolves to:

(+) (3 + 5) 500

and finally resolves to:

(+) 8 500 -- => 8

Finished! It actually makes perfect sense, and is an excellent example of recursive problem solving in Haskell.

Whilst this was an interesting problem, the real lesson here was to follow the steps taken by Tikhon Jelvis in his answer to the discussion mentioned at the start. If you’re stuck, start with the class definition, then substitute in the specialised types, then take a simple example and work it through step by step until you understand how it works.

Written with StackEdit.