Write f in pointfree-style?

Question

Say I have functions

g :: a -> b, h :: a -> c

and

f :: b -> c -> d.

Is it possible to write the function

 f' :: a -> a -> d

given by

f' x y = f (g x) (h y)

in point free style?.

One can write the function

f' a -> d, f' x = f (g x) (h x)

in point free style by setting

f' = (f <$> g) <*> h

but I couldn't figure out how to do the more general case.

score 24 · Accepted Answer · edited Aug 08 '16 at 11:24

We have:

k x y = (f (g x)) (h y)

and we wish to write k in point-free style.

The first argument passed to k is x. What do we need to do with x? Well, first we need to call g on it, and then f, and then do something fancy to apply this to (h y).

k = fancy . f . g

What is this fancy? Well:

k x y = (fancy . f . g) x y
      = fancy (f (g x)) y
      = f (g x) (h y)

So we desire fancy z y = z (h y). Eta-reducing, we get fancy z = z . h, or fancy = (. h).

k = (. h) . f . g

A more natural way to think about it might be

                             ┌───┐           ┌───┐
                        x ───│ g │─── g x ───│   │
                      /      └───┘           │   │
               (x, y)                        │ f │─── f (g x) (h y)
                      \      ┌───┐           │   │
                        y ───│ h │─── h y ───│   │
                             └───┘           └───┘

                      └──────────────────────────────┘
                                      k

Enter Control.Arrow:

k = curry ((g *** h) >>> uncurry f)

This is very different from the procedure I tend to follow myself. It's always refreshing to see a new way. — dfeuer, Aug 03 '16 at 16:05

score 5 · Answer 2 · answered Aug 03 '16 at 12:30

5

Take a look at online converter

It converted

f' x y = f (g x) (h y)

into

f' = (. h) . f . g

with the flow of transformations

f' = id (fix (const (flip ((.) . f . g) h))) 
f' = fix (const (flip ((.) . f . g) h)) 
f' = fix (const ((. h) . f . g)) 
f' = (. h) . f . g

answered Aug 03 '16 at 12:30

Nazarii Bardiuk

4,272
1
19
22

How did you/it go from `f' x y = f (g x) (h y)` to `f' = id (fix (const (flip ((.) . f . g) h)))`? – Gurkenglas Aug 03 '16 at 12:43
I am not expert in this. Looks like library has a set predefined transformations and performs search in the space of possible transformations. And by following simplifications looks like it has some redundant functions. For example first step could be `flip ((.) . f . g) h` without chain of `id(fix(const` – Nazarii Bardiuk Aug 03 '16 at 12:54

score 3 · Answer 3 · answered Aug 03 '16 at 13:41

This is slightly longer, but a little easier to follow, than (. h) . f. g.

First, rewrite f' slightly to take a tuple instead of two arguments. (In otherwords, we're uncurrying your original f'.)

f' (x, y) = f (g x) (h y)

You can pull a tuple apart with fst and snd instead of pattern matching on it:

f' t = f (g (fst t)) (h (snd t))

Using function composition, the above becomes

f' t = f ((g . fst) t) ((h . snd) t)

which, hey, looks a lot like the version you could make point-free using applicative style:

f' = let g' = g . fst
         h' = h . snd
     in (f <$> g') <*> h'

The only problem left is that f' :: (a, a) -> d. You can fix this by explicitly currying it:

f' :: a -> a -> d
f' = let g' = g . fst
         h' = h . snd
     in curry $ (f <$> g') <*> h'

(This is very similar, by the way, to the Control.Arrow solution added by Lynn.)

Easier to follow that `(. h) . f . g`? Er... I don't think so. Using the `Applicative (a->)` instance with tuples is giving you the _worst of both worlds_: cryptic dataflow semantics and awkward currying. — leftaroundabout, Aug 03 '16 at 15:41
I find partial application of `(.)` to be even less understandable than `Applicative (a ->)`. The user already indicated an understanding (or at least awareness) of `Applicative`, so I built off that. The question was how to write a point-free version of the function; myself, I wouldn't bother and stick with the perfectly understandable `f x y = f (g x) (h y)`. — chepner, Aug 03 '16 at 15:57

score 3 · Answer 4 · edited May 23 '17 at 12:06

Using the "three rules of operator sections" as applied to the (.) function composition operator,

(.) f g  =  (f . g)  =  (f .) g  =  (. g) f   -- the argument goes into the free slot
--       1           2           3

this is derivable by a few straightforward mechanical steps:

k x y =  (f (g x)) (h y)                      -- a (b c) === (a . b) c
      =  (f (g x) . h) y
      =  (. h)  (f (g x)) y
      =  (. h)  ((f . g)  x) y
      = ((. h) . (f . g)) x  y

Lastly, (.) is associative, so the inner parens may be dropped.

The general procedure is to strive to reach the situation where eta-reduction can be performed, i.e. we can get rid of the arguments if they are in same order and are outside any parentheses:

k x y = (......) y
=>
k x   = (......)

Lather, rinse, repeat.

Another trick is to turn two arguments into one, or vice versa, with the equation

curry f x y = f (x,y)

so, your

f (g x) (h y) = (f.g) x (h y)                      -- by B-combinator rule
              = (f.g.fst) (x,y) ((h.snd) (x,y))
              = (f.g.fst <*> h.snd) (x,y)          -- by S-combinator rule
              = curry (f.g.fst <*> h.snd) x y

This is the same as the answer by @chepner, but presented more concisely.

So, you see, your (f.g <*> h) x¹ just becomes (f.g.fst <*> h.snd) (x,y). Same difference.

¹(because, for functions, (<$>) = (.))

score 1 · Answer 5 · answered Aug 04 '16 at 15:33

Control.Compose

(g ~> h ~> id) f

Data.Function.Meld

f $* g $$ h *$ id

Data.Function.Tacit

lurryA @N2 (f <$> (g <$> _1) <*> (h <$> _2))
lurryA @N5 (_1 <*> (_2 <*> _4) <*> (_3 <*> _5)) f g h

Write f in pointfree-style?

5 Answers5

Related articles

Linked