Understanding `ap` in a point-free function in Haskell

Question

I am able to understand the basics of point-free functions in Haskell:

addOne x = 1 + x

As we see x on both sides of the equation, we simplify it:

addOne = (+ 1)

---

Incredibly it turns out that functions where the same argument is used twice in different parts can be written point-free!

Let me take as a basic example the average function written as:

average xs = realToFrac (sum xs) / genericLength xs

It may seem impossible to simplify xs, but http://pointfree.io/ comes out with:

average = ap ((/) . realToFrac . sum) genericLength

That works.

As far as I understand this states that average is the same as calling ap on two functions, the composition of (/) . realToFrac . sum and genericLength

Unfortunately the ap function makes no sense whatsoever to me, the docs http://hackage.haskell.org/package/base-4.8.1.0/docs/Control-Monad.html#v:ap state:

ap :: Monad m => m (a -> b) -> m a -> m b

In many situations, the liftM operations can be replaced by uses of ap,
which promotes function application.

      return f `ap` x1 `ap` ... `ap` xn

is equivalent to

      liftMn f x1 x2 ... xn

But writing:

let average = liftM2 ((/) . realToFrac . sum) genericLength

does not work, (gives a very long type error message, ask and I'll include it), so I do not understand what the docs are trying to say.

---

How does the expression ap ((/) . realToFrac . sum) genericLength work? Could you explain ap in simpler terms than the docs?

Answer 1

Any lambda term can be rewritten to an equivalent term that uses just a set of suitable combinators and no lambda abstractions. This process is called abstraciton elimination. During the process you want to remove lambda abstractions from inside out. So at one step you have λx.M where M is already free of lambda abstractions, and you want to get rid of x.

• If M is x, you replace λx.x with id (id is usually denoted by I in combinatory logic).
• If M doesn't contain x, you replace the term with const M (const is usually denoted by K in combinatory logic).

• If M is PQ, that is the term is λx.PQ, you want to "push" x inside both parts of the function application so that you can recursively process both parts. This is accomplished by using the S combinator defined as λfgx.(fx)(gx), that is, it takes two functions and passes x to both of them, and applies the results together. You can easily verify that that λx.PQ is equivalent to S(λx.P)(λx.Q), and we can recursively process both subterms.

  As described in the other answers, the S combinator is available in Haskell as ap (or <*>) specialized to the reader monad.

The appearance of the reader monad isn't accidental: When solving the task of replacing λx.M with an equivalent function is basically lifting M :: a to the reader monad r -> a (actually the reader Applicative part is enough), where r is the type of x. If we revise the process above:

• The only case that is actually connected with the reader monad is when M is x. Then we "lift" x to id, to get rid of the variable. The other cases below are just mechanical applications of lifting an expression to an applicative functor:
• The other case λx.M where M doesn't contain x, it's just lifting M to the reader applicative, which is pure M. Indeed, for (->) r, pure is equivalent to const.
• In the last case, <*> :: f (a -> b) -> f a -> f b is function application lifted to a monad/applicative. And this is exactly what we do: We lift both parts P and Q to the reader applicative and then use <*> to bind them together.

The process can be further improved by adding more combinators, which allows the resulting term to be shorter. Most often, combinators B and C are used, which in Haskell correspond to functions (.) and flip. And again, (.) is just fmap/<$> for the reader applicative. (I'm not aware of such a built-in function for expressing flip, but it'd be viewed as a specialization of f (a -> b) -> a -> f b for the reader applicative.)

_{Some time ago I wrote a short article about this: The Monad Reader Issue 17, The Reader Monad and Abstraction Elimination.}

Answer 2

When the monad m is (->) a, as in your case, you can define ap as follows:

ap f g = \x -> f x (g x)

We can see that this indeed "works" in your pointfree example.

average = ap ((/) . realToFrac . sum) genericLength
average = \x -> ((/) . realToFrac . sum) x (genericLength x)
average = \x -> (/) (realToFrac (sum x)) (genericLength x)
average = \x -> realToFrac (sum x) / genericLength x

We can also derive ap from the general law

ap f g = do ff <- f ; gg <- g ; return (ff gg)

that is, desugaring the do-notation

ap f g = f >>= \ff -> g >>= \gg -> return (ff gg)

If we substitute the definitions of the monad methods

m >>= f = \x -> f (m x) x
return x = \_ -> x

we get the previous definition of ap back (for our specific monad (->) a). Indeed:

app f g 
= f >>= \ff -> g >>= \gg -> return (ff gg)
= f >>= \ff -> g >>= \gg -> \_ -> ff gg
= f >>= \ff -> g >>= \gg _ -> ff gg
= f >>= \ff -> \x -> (\gg _ -> ff gg) (g x) x
= f >>= \ff -> \x -> (\_ -> ff (g x)) x
= f >>= \ff -> \x -> ff (g x)
= f >>= \ff x -> ff (g x)
= \y -> (\ff x -> ff (g x)) (f y) y
= \y -> (\x -> f y (g x)) y
= \y -> f y (g y)

Answer 3

The Simple Bit: fixing liftM2

The problem in the original example is that ap works a bit differently from the liftM functions. ap takes a function wrapped up in a monad, and applies it to an argument wrapped up in a monad. But the liftMn functions take a "normal" function (one which is not wrapped up in a monad) and apply it to argument(s) that are wrapped up in monads.

I'll explain more about what that means below, but the upshot is that if you want to use liftM2, then you have to pull (/) out and make it a separate argument at the beginning. (So in this case (/) is the "normal" function.)

let average = liftM2 ((/) . realToFrac . sum) genericLength -- does not work
let average = liftM2 (/)   (realToFrac . sum) genericLength -- works

As posted in the original question, calling liftM2 should involve three agruments: liftM2 f x1 x2. Here the f is (/), x1 is (realToFrac . sum) and x2 is genericLength.

The version posted in the question (the one which doesn't work) was trying to call liftM2 with only two arguments.

The explanation

I'll build this up in a few stages. I'll start with some specific values, and build up to a function that can take any set of values. Jump to the last section for the TL:DR

In this example, lets assume the list of numbers is [1,2,3,4]. The sum of these numbers is 10, and the length of the list is 4. The average is 10/4 or 2.5.

To shoe-horn this into the right form for ap, we're going to break this into a function, an input, and a result.

ourFunction =  (10/)    -- "divide 10 by"
ourInput    =    4
ourResult   =    2.5 

Three kinds of Function Application

ap and listM both involve monads. At this point in the explanation, you can think of a monad as something that a value can be "wrapped up in". I'll give a better definition below.

Normal function application applies a normal function to a normal input. liftM applies a normal function to an input wrapped in a monad, and ap applies a function wrapped in a monad to an input wrapped in a monad.

        (10/) 4          -- returns 2.5
liftM   (10/) monad(4)   -- returns monad(2.5)
ap monad(10/) monad(4)   -- returns monad(2.5)

(Note that this is pseudocode. monad(4) is not actually valid Haskell).

(Note that liftM is a different function from liftM2, which was used earlier. liftM takes a function and only one argument, which is a better fit for the pattern i'm describing.)

In the average function defined above, the monads were functions, but "functions-as-monads" can be hard to talk about, so I'll start with simpler examples.

So what's a monad?

A better description of a monad is "something which contains a value, or produces a value, or which you can somehow extract a value from, but which also has something more complicated going on."

That's a really vague description, but it kind of has to be, because the "something more complicated" can be a lot of different things.

Monads can be confusing, but the point of them is that when you use monad operations (like ap and liftM) they will take care of the "something more complicated" for you, so you can just concentrate on the values.

That's probably still not very clear, so let's do some examples:

The Maybe monad

ap (Just (10/)) (Just 4)   -- result is (Just 2.5)

One of the simplest monads is 'Maybe'. The value is whatever is contained inside a Just. So if we call ap and give it (Just ourFunction) and (Just ourInput) then we get back (Just ourResult).

The "something more complicated" is the fact that there might not be a value there at all, and you have to allow for the Nothing case.

As mentioned, the point of using a function like ap is that it takes care of these extra complications for us. With the Maybe monad, ap handles this by returning Nothing if either the Maybe-function or the Maybe-input were Nothing.

ap (Just (10/)) Nothing    -- result is Nothing
ap Nothing (Just 4)        -- result is Nothing

The List Monad

ap [(10/)] [4]    -- result is [2.5]

With the list Monad, the value is whatever is inside the list. So ap [ourfunction] [ourInput] returns [ourResult].

The "something more complicated" is that there may be more than one thing inside the list (or exactly one thing, or nothing at all).

With lists, that means ap takes a list of zero or more functions, and a list of zero or more inputs. It handles that by returning a list of zero or more results: one result for every possible combination of function and input.

ap [(10/), (100/)] [5,4,2]  -- result is [2.0, 2.5, 5.0, 20.0, 25.0, 50.0]

Functions as Monads

A function like genericLength is considered a Monad because it has a value (the function's output), and it has a "something more complicated" (the fact that you have to supply an input before you can get the value).

This is where it gets a little confusing, because we're dealing with multiple functions, multiple inputs, and multiple results. It is all well defined, it's just hard to describe, so we have to be careful with our terminology.

Lets start with the list [1,2,3,4], and call that our "original input". That's the list we're trying to find the average of. It's the xs argument in the original average function.

If we give our original input ([1,2,3,4]) to genericLength then we get a value of '4'.

Our other function is ((/) . realToFrac . sum). It takes our list [1,2,3,4] and finds the sum (10), turns that into a fractional value, and then feeds it as the first argument to (/). The result is an incomplete division function that is waiting for another argument. ie it takes [1,2,3,4] as an input, and produces (10/) as its output.

This all fits with the way ap is defined for functions. With functions, ap takes two things. The first is a function that reads the original input and produces a new function. The second is a function that reads the original input and produces a new input. The final result is a function that takes the original input, and returns the same thing you would get if you applied the new function to the new input.

You might have to read that a few times to make sense of it. Alternatively, here it is in pseudocode:

average = 
  ap
    (functionThatTakes [1,2,3,4] and returns "(10/)" )
    (functionThatTakes [1,2,3,4] and returns "  4  " )

-- which means:

average = 
    (functionThatTakes [1,2,3,4] and returns "2.5"  )

If you compare this to the simpler examples above, you'll see that it still has our function (10/), our input 4 and our result 2.5. And each of them is once again wrapped up in the "something more complicated". In this case, the "something more complicated" is the "function that takes [1,2,3,4] and returns...".

Of course, since they're functions, they don't have to take [1,2,3,4] as their input. If they took a different list of integers (eg [1,2,3,4,5]) then we would get different results (e.g. new function: (15/), new input 5 and new value 3).

Other examples

minPlusMax = ap ((+) . minimum) maximum
-- a function that adds the minimum element of a list, to the maximum element


upperAndLower = ap ((,) . toUpper) toLower
-- a function that takes a Char and returns a tuple, with the upper case and lower case versions of a character

These could all also be defined using liftM2.

average       = liftM2 (/) sum genericLength
minPlusMax    = liftM2 (+) minimum maximum
upperAndLower = liftM2 (,) toUpper toLower