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 ```

Accepted Answer

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 out1 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`.

1 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)
```

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

Solution

Problem

Related problems