How can I make a combinator with this type signature?

Question

I've been trying to make a combinator with this type signature:

(a -> b -> c) -> (c -> d -> e) -> a -> b -> d -> e

I've been through Data.Aviary.Birds and all the tacit programming help sites that I can find, but to no avail. Also, if there's a general algorithm to make these, it would be greatly appreciated but not necessary.

Answer 1

Our definition will start like this:

foo :: (a -> b -> c) -> (c -> d -> e) -> a -> b -> d -> e
foo abc cde a b d = e

Now let's fill in the missing bits.

We need an e; the only way to get that is by applying the second function to a c and d.

e = cde c d

We are already given a d, but we need a c. How do we get a c? By applying the first function to an a and a b.

c = abc a b

We are given both of these, so we're done.

foo :: (a -> b -> c) -> (c -> d -> e) -> a -> b -> d -> e
foo abc cde a b d = e
  where
    e = cde c d
    c = abc a b

We might stop here. This is a perfectly good definition.

---

But if we want to try to make it more terse, let's start by substituting the definition of e

foo abc cde a b d = cde c d
  where
    c = abc a b

and then of c

foo abc cde a b d = cde (abc a b) d

We immediately see that we can eta reduce to remove the d.

foo abc cde a b = cde (abc a b)

The type is now slightly more general. d -> e has collapsed into one type variable, since it can actually be anything.

foo :: (a -> b -> c) -> (c -> de) -> a -> b -> de

We can now see in the aviary that our combinator is actually the blackbird, flipped.

blackbird :: (c -> d) -> (a -> b -> c) -> a -> b -> d

foo :: (a -> b -> c) -> (c -> de) -> a -> b -> de
foo = flip blackbird

And indeed if we look at the source for the blackbird, it looks much like what we have written.

-- | B1 combinator - blackbird - specs 'oo'.
blackbird :: (c -> d) -> (a -> b -> c) -> a -> b -> d
blackbird f g x y = f (g x y)

---

Can we go more point-free? We might consider uncurrying abc

foo abc cde a b = cde (uncurry abc (a, b))

rewriting this nesting with function composition

foo abc cde a b = (cde . uncurry abc) (a, b)

and currying back again

foo abc cde a b = curry (cde . uncurry abc) a b

And now we can chop off two more parameters.

foo abc cde = curry (cde . uncurry abc)

We should definitely stop here. But what if we now flip the arguments

foo = flip $ \cde abc -> curry (cde . uncurry abc)

rewrite the right half to make it point-free

foo = flip $ \cde abc -> (curry . ((cde .) . uncurry)) abc

and eta reduce once more

foo = flip $ \cde -> curry . ((cde .) . uncurry)

and take one final ridiculous step

foo = flip $ (curry .) . (. uncurry) . (.)

We are now point-free!

Answer 2

There's a really easy way: cheat. Let's start by finding out what function we want. For this, we go to Djinn. Type in

f :: (a -> b -> c) -> (c -> d -> e) -> a -> b -> d -> e

and it comes back with

f a b c d = b (a c d)

Nice. Now head over to pointfree.io. Paste in the definition from Djinn, and it says

f = flip ((.) . (.))

Done.