Point free style with infix notation

问题:

Hello is there a way to write point free style when using infix notation?

f::Int->Int->Int->Int
f a b=(+) (a+b)

Why you cannot do something like this ?

 f::Int->Int->Int->Int
 f a b=(a+b) +

      or

 f a b= (a+b) `+`

Can you not combine operators in point free style like e.g?

ptfree::Int->Int->Int->Int
ptfree=(+) (+)

I mean you can chop arguments of functions like fold but why not for operator arguments?

回答1:

Well since you need to pass two parameters, we can use what is known as the "surprised owl operator". This is basically a composition of parameters. So we can use:

f = ((.).(.)) (+) (+)

Or we can more inline the operator like:

f = ((+) .) . (+)

The owl operator ((.).(.)) f g basically is short for \x y -> f (g x y)

How does this work?

The canonical form of the "surprised owl operator" is:

= ((.) . (.))
------------- (canonical form)
  (.) (.) (.)

So we can now replace the (.)s with corresponding lambda expressions:

(\f g x -> f (g x)) (.) (.)

So now we can perform some replacements:

   (\f g x -> f (g x)) (.) (.)
-> (\x -> (.) ((.) x))
-> (\x -> (\q r y -> q (r y)) ((.) x))
-> (\x -> (\r y -> ((.) x) (r y)))
-> (\x r y -> ((.) x) (r y))
-> (\x r y -> ((\s t u -> s (t u)) x) (r y))
-> (\x r y -> (\t u -> x (t u)) (r y))
-> (\x r y -> (\u -> x ((r y) u)))
-> \x r y u -> x ((r y) u))
-> \x r y u -> x (r y u)

So basically it means that our surprised owl operator, is equal to:

surprised_owl :: (y -> z) -> (a -> b -> y) -> a -> b -> z
surprised_owl f g x y = f (g x y)  -- renamed variables

And if we now specialize this with the fuctions provided (two times (+)), we get:

f = surprised_owl (+) (+)

so:

f x y = (+) ((+) x y)

回答2:

You must compose (+) with (+) twice, for it to be completely point-free: f = ((+) .) . (+)

Recall that composition is defined as

(f . g) x = f (g x)

or, equivalently:

(f . g) = \x -> f (g x)

So, if you look at the composition f = ((+) .) . (+) and work backwards using the definition of (.):

f       = ((+) .) . (+)
f       = \x -> ((+) .) ((+) x)          -- definition of (.)
f       = \y -> (\x -> (+) (((+) x) y))  -- definition of (.)
f x y   = (+) (((+) x) y)                -- a simpler way to write this
f x y z = (+) (((+) x) y) z              -- explicitly add in the final argument (eta expansion)
f x y z = ((+) x y) + z                  -- rewrite as infix
f x y z = (x + y) + z                    -- rewrite as infix

and you see we end up with what we started before we tried to make it point-free, so we know that this definition works. Going the other way through the steps above, roughly bottom-to-top, could give you an idea of how you might find such a point-free definition of a function like f.

When you "leave off" multiple arguments from the "end" like this, you usually must compose multiple times. Working through a few similar functions should help build intuition for this.

Note: I wouldn't generally recommend using this sort of point-free (when it complicates things) in production code.