Can any function be reduced to a point-free form?

Question

Many functions can be reduced to point free form - but is this true for all of them?

E.g. I don't see how it could be done for:

apply2 f x = f x x 

Answer 1

Logical combinators (i.e. the S, K, I combinators) are essentially point-free forms of functions, and the lambda-calculus is equivalent to combinatory logic, so I think this suggests that the answer is yes.

The combinator for your apply2 function is (if I am reading things correctly):

((S((S(KS))K))(K((S((SK)K))((SK)K))))

also known as the "Lark", from Raymond Smullyan's Combinatory Birds page.

(edit-in:) Turns out¹ the above is equivalent to \f x -> f (x x). According to the comments by "@gereeter" here below it is indeed known as the "Lark", whereas the function \f x -> f x x requested in the question is the "Warbler" from the aforementioned book (a.k.a. the "W" combinator), W f x = S(S(K(S(KS)K))S)(KK)SI f x = S(S(KB)S)(KK)SI f x = CSI f x = SfIx = f x x.

---

¹ here:

((S((S(KS))K))(K((S((SK)K))((SK)K)))) f x =
  S( S(KS) K) (K( S( SK K) ( SK K)))  f x =   -- SKK    == I
  S (S(KS) K) (K( S  I       I    ))  f x =   -- S(KS)K == B
  S B         (K( S  I       I    ))  f x =
  Bf (K(SII)f) x = Bf (SII) x = f (SII x) = f (x x)

Answer 2

S-K basis

As already mentioned, with a proper fixed set of combinators, any lambda term can be converted into a form that uses only those combinators and function application - no lambda abstraction (hence no variables). The most well known set of combinators is S and K. Se Combinatory Logic/Completeness of the S-K basis for the description of the procedure. The combinators are defined as

K x y    = x
S x y z  = (x z) (y z)

Sometimes the identity combinator I is included, but it's redundant as I = S K K.

A single combinator basis

Interestingly you can do that even with a single combinator. The Iota language uses

U f = (f S) K

and it can be shown that

I = (UU)
K = (U(U(UU)))
S = (U(U(U(UU))))

So we can convert any lambda term into a binary tree with no other information than it's shape (all the leaves contain U and and the nodes represent function application).

A more efficient basis S, K, I, B, C

However, if we want to be a bit efficient and get a reasonably sized conversion, it's helpful to use I and to introduce two more redundant combinators, which are called B and C:

C f x y  = f y x
B f g x  = f (g x)

Here C reverses the order of arguments of f and B is function composition.

This addtion reduces the length of the output significantly.

These combinators in Haskell

Actually Haskell already contains all those standard combinators in some form. In particular:

I = id
K = const
  = pure :: a -> (r -> a)
S = (<*>) :: (r -> a -> b) -> (r -> a) -> (r -> b)
B = (.)
  = (<$>) :: (a -> b) -> (r -> a) -> (r -> b)
C = flip
  = \k x -> k <*> pure x

where pure, <*> and <$> are functions from the Applicative functors type class which we here specialize for the reader monad (->) r.

So in your case, we could write

apply2 = (<*>) `flip` id

Why the reader monad?

In the process of abstraction elimination we try to convert a term of the form λx -> M :: r -> a (where r is the type of x and a is the type of M) into a form without x. We do this by recursively processing M and we subsequently convert each its sub-term of type b (possibly containing x) into a function of type r -> b (not containing x), and then we combine these sub-terms together. And that's just what the reader monad is designed for: To combine functions of type r -> something together.

For more details see The Monad Reader, Issue 17: The Reader Monad and Abstraction Elimination.

How about data structures?

For constructing data structures we simply use their constructors, there is no problem here.

For deconstructing them, we need some way to get rid of pattern matching. This is something a compiler has to do when compiling a functional program. Such a procedure is described in The Implementation of Functional Programming Languages Chapter 5: Efficient compilation of pattern matching. The idea is that for each data type we have one case function that describes how to deconstruct (fold) the data type. For example, for lists it foldr, for Either its either, and let's say for 4-tuples it'd be

caseTuple4 :: (a -> b -> c -> d -> r) -> (a,b,c,d) -> r
caseTuple4 f (a,b,c,d) = f a b c d

etc. So for each data type we add its constructors, its deconstructing case function, and compile patterns into this function.

As an example, let's express

map :: (a -> b) -> [a] -> [b]
map f []        = []   
map f (x : xs)  = f x : map f xs

this can be expressed using foldr:

map f = foldr (\x xs -> f x : xs) []

and then converted using the combinators we discussed earlier:

map = (foldr . ((.) (:))) `flip` []

You can verify that it indeed does what we want.

See also System F data structures which describes how data structures can be encoded directly as functions if we enable higher rank types.

Conclusion

Yes, we can construct a fixed set of combinators and then convert any function into point-free style that uses only these combinators and function application.