Every so often I have a function of type a -> b and a function of type b -> b -> c and I would like a function of type a -> a -> c. For example if I wanted to check the second element of each two tuples were equal

snd :: (a , b) -> b
(==) :: Eq a => a -> a -> Bool

And I want something of type

Eq b => (a, b) -> (c, b) -> Bool

The best way I have found to do this so far is

f g z=(.g).z.g

Which is ok, but it feels unneccessarily complex for something that is this simple. The pointfree representation is even worse:


Additionally it feels like this idiom should be representable with some sort of abstraction (it feels a lot like (<*>)). I attempted to find a replacement by abstracting our functions to functors, the result is not very enlightening

flip=<<(fmap.).fmap.flip fmap ::
  Functor f => f a -> (a -> a -> b) -> f (f b)

Is there a shorter way to express this idea? Particularly the pointfree version?

  • 4
    \$\begingroup\$ There is on but you need to import Data.Function. \$\endgroup\$
    – flawr
    Dec 22 '19 at 18:02

Stumbled upon this question in the related questions list of How to golf a fork in Haskell?. Now that I have a better understanding of combinator golf, I gave it a try.

Primer: Haskell supports a few combinators including the standard S, B, C, K, I:

-- I
id = \x -> x
-- K
pure = \x y -> x  -- 1 byte shorter than `const`
-- S
(<*>) = \x y z -> x z (y z)
-- B
(.) = \x y z -> x (y z)
-- C
flip = \x y z -> x z y
-- Variations of S
(>>=) = \x y z -> y (x z) z
(=<<) = \x y z -> x (y z) z
liftA2 = \f g h x -> f (g x) (h x)  -- part of latest Prelude

Now, there are two possible forms to convert to pointfree:

v1 :: (b -> b -> c) -> (a -> b) -> (a -> a -> c)
v1 f g x y = f (g x) (g y)
v2 :: (a -> b) -> (b -> b -> c) -> (a -> a -> c)
v2 f g x y = g (f x) (f y)

The following are all the various reductions I tried (along with typechecking):

import Control.Applicative

type On a b c = (b -> b -> c) -> (a -> b) -> a -> a -> c
fref :: On a b c
fref g h x y=g(h x)(h y)
f1 :: On a b c
f1=(flip flip<*>).(.).((.).)
f2 :: On a b c
f2 z g=(.g).z.g
f3 :: On a b c
f4 :: On a b c
f5 :: On a b c

type On2 a b c = (a -> b) -> (b -> b -> c) -> a -> a -> c
fref' :: On2 a b c
fref' g h x y=h(g x)(g y)
f1' :: On2 a b c
f1' g=((.g).).(.g)
f2' :: On2 a b c
f3' :: On2 a b c
f3' g z=(.g).z.g
f4' :: On2 a b c
f5' :: On2 a b c
f6' :: On2 a b c
f6' g=(.g).((.g).)
f7' :: On2 a b c
f8' :: On2 a b c
f8'=s<*>s;s x=(.)(.x)

Try it online!

Unfortunately, the shortest unnamed lambda version is the same as OP's of

\z g->(.g).z.g

at 14 bytes, supporting both versions (just swap g and z in the argument list for the alternative version).

The shortest pointfree solution I could find was


at 20 bytes (which has the type of v1), which is 5 bytes shorter than OP's. For v2, I got two different 25 byters.

The reduction steps to reach this one:

\f g a b -> f (g a) (g b)
\f g a -> B (f (g a)) g
\f g -> C (\a -> B (f (g a))) g
\f g -> C (B (B B f) g) g
\f g -> (=<<) C (B (B B f)) g
\f -> (=<<) C (B (B B f))

I think eta-reduction is severely overrated. I see a lot more attempts at eta-reduction in the wild than I think is reasonable.

So it is in this case: eta-reducing this function is not helpful, I think. It's much more readable and elegant in its full form:

f :: (a -> a -> c) -> (a -> b) -> b -> b -> c
f g h a b = g (h a) (h b)

On a related note, such function exists in the standard libraries. It's called on, and the idea is to use it in infix form, so that it almost reads like English:

eqAmounts = (==) `on` amount
cmpNames = compare `on` name
  • 5
    \$\begingroup\$ Welcome to the site. I will say that "readability" and "elegance" are not worth a whole lot here. The reason eta reduction is popular for golfing is that point free functions don't require costly declarations. The on function that you and flawr pointed out is nice and short though. \$\endgroup\$
    – Wheat Wizard
    Dec 22 '19 at 18:44
  • 3
    \$\begingroup\$ I see. Thank you for pointing out. I will unsubscribe from this site. \$\endgroup\$ Dec 22 '19 at 20:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.