How to rewrite in point-free style with a repeating variable?

Question

How to rewrite the following expression in point-free style?

p x y = x*x + y

Using the lambda-calculus I did the following:

p = \x -> \y -> (+) ((*) x x) y
  = \x -> (+) ((*) x x) -- here start my problem
  = \x -> ((+) . ((*) x )) x
  ... ?

Answer 1

Since you mentioned Lambda Calculus I will suggest how to solve this with SK combinators. η-reduction was a good try, but as you can tell you can't η-reduce when the variable is used twice.

S = λfgx.fx(gx)
K = λxy.x

The feature of duplication is encoded by S. You simplified your problem to:

λx.(+)((*)xx)

So let us start there. Any lambda term can be algorithmically transformed to a SK term.

T[λx.(+)((*)xx)]
= S(T[λx.(+)])(T[λx.(*)xx])        -- rule 6
= S(K(T[(+)]))(T[λx.(*)xx])        -- rule 3
= S(K(+))(T[λx.(*)xx])             -- rule 1
= S(K(+))(S(T[λx.(*)x])(T[λx.x]))  -- rule 6
= S(K(+))(S(*)(T[λx.x]))           -- η-reduce
= S(K(+))(S(*)I)                   -- rule 4

In Haskell, S = (<*>) and K = pure and I = id. Therefore:

= (<*>)(pure(+))((<*>)(*)id)

And rewriting:

= pure (+) <*> ((*) <*> id)

Then we can apply other definitions we know:

= fmap (+) ((*) <*> id)     -- pure f <*> x = fmap f x
= fmap (+) (join (*))       -- (<*> id) = join for Monad ((->)a)
= (+) . join (*)            -- fmap = (.) for Functor ((->)a)

Answer 2

If you go to http://pointfree.io/

For

p x y = x*x + y

It gives you

p = (+) . join (*)

Answer 3

I asked lambdabot

<Iceland_jack> @pl p x y = x*x + y
<lambdabot> p = (+) . join (*)

join is from Control.Monad and normally has this type

join :: Monad m => m (m a) -> m a

but using instance Monad ((->) x) (if we could left section types this could be written (x ->)) we get the following type / definition

join :: (x -> x -> a) -> (x -> a)
join f x = f x x

Let's ask GHCi to confirm the type:

>> import Control.Monad
>> :set -XTypeApplications 
>> :t join @((->) _)
join @((->) _) :: (x -> x -> a) -> x -> a

Answer 4

Just for fun, you can use the State monad to write

p = (+) . uncurry (*) . runState get

runState get simply produces a pair (x, x) from an initial x; get copies the state to the result, and runState returns both the state and that result.

uncurry (*) takes a pair of values rather than 2 separate values ((uncurry (*)) (3, 3) == (*) 3 3 == 9).