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?
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)
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.
