Write biSp in point-free form using as few terms as possible

Question

The Haskell function biSp has type signature

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

and (for those who prefer combinator calculus) can be defined as

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

Your task is to implement biSp in point-free form (equivalently: as a combinator without any lambdas) using only two primitives:

(.) :: (b -> c) -> (a -> b) -> a -> c
flip :: (a -> b -> c) -> b -> a -> c

or

(.) f g x = f (g x)
flip f x y = f y x

For those with a background in combinator calculus, these are respectively the B and C combinators.

You may define helper functions so long as they are point-free. Your score is the total number of terms in all right-hand-side expressions.

Testing

You can test a Haskell solution without installing any software using Ideone. By providing an explicit type alongside the definition you ensure a compile-time error if the function is incorrect. E.g. using the :pl reference implementation (online demo):

biSp :: (a -> c) -> (b -> d) -> (c -> d -> e) -> a -> b -> e
biSp = flip . ((flip . ((.) .)) .) . flip (.)
main = putStrLn "Compiled ok"

Answer 1

7 terms

We again define a helper combinator BBQ = B B (C B), which has reduction rule

BBQ w x y z = x y (w z)

Then biSp = BBQ BBQ BBQ

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

Online demo

By brute force, this is the only 7-term solution and there is no smaller solution.

8 terms

There are a handful of 8-term solutions. Firstly, the obvious

C BBQ BBQ BBQ

which reduces in one step to BBQ BBQ BBQ.

Then there are three solutions of the form X X X with a five-term X:

• X = B (B B) C B which reduces in one step to BBQ
• X = C B (C B) B which reduces in one step to BBQ and allows the further extraction, for no net gain or loss, of a helper combinator Q = C B
• X = C (B C (B B))

There is one solution of the form X X with a six-term X:

• X = C B (B B (C B)) (again, with an equivalent version which extracts Q = C B)

And there is one solution which can only be written in 8 terms with two helper combinators:

Q = C B
X = Q (Q Q B)
biSp = X X

Answer 2

9 terms

Define a helper combinator BBQ = B B (C B), which has reduction rule

BBQ w x y z = x y (w z)

Then we have three options:

1. C (B B BBQ) BBQ
2. B (C B BBQ) BBQ
3. C (B (C BBQ) BBQ)

To show the equivalence of the first two:

  C (B B BBQ) BBQ g h f x y
= B B BBQ g BBQ h f x y
= B (BBQ g) BBQ h f x y

  B (C B BBQ) BBQ g h f x y
= C B BBQ (BBQ g) h f x y
= B (BBQ g) BBQ h f x y

We can then continue:

= BBQ g (BBQ h) f x y

That then gives the equivalence with the third:

  C (B (C BBQ) BBQ) g h f x y
= B (C BBQ) BBQ h g f x y
= C BBQ (BBQ h) g f x y
= BBQ g (BBQ h) f x y

Finally

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

In Haskell this is (picking one of the options):

bbq = (.) (.) (flip (.))
biSp = flip ((.) (.) bbq) bbq

Online demo

Answer 3

9 terms

This uses an intermediate combinator which I shall call Par for parity, because of the way it groups its arguments. Par = B C (B B) has reduction rule

Par w x y z = (w y) (x z)

Then biSp = C (B Par (C Par)). To demonstrate:

  C (B Par (C Par)) g h f x y
= B Par (C Par) h g f x y
= Par (C Par h) g f x y
= C Par h f (g x) y
= Par f h (g x) y
= f (g x) (h y)

In Haskell this is

par = (.) flip ((.) (.))
biSp = flip ((.) par (flip par))

Online demo

Answer 4

10 terms

         1  2     3  4   5  6   7  8   9  10
biSp = flip . ((flip . ((.) .)) .) . flip (.)

Another reference solution, that from ghci-on-acid's :pl command.

Answer 5

10 terms

        1   2    3   4   5    6   7   8
biSp = cf ((.) (cf ((.) (.))) . flip (.))

      9   10
cf = (.) flip

Another 10 term solution

        1   2  3  4  5  6 7  8
biSp = fc ((.) . fc) . fc . fc

       9  10
fc = flip (.)