Search code examples
haskelllambda-calculuspointfree

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

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
Solution

  • 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)