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

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"

• I'm not really sure what it is the above is doing (note that I'm not very familiar with functional programming). – Kyle Kanos May 29 '14 at 18:37
• I added a link. Why so many close votes? Is this not a good programming puzzle? – dspyz May 29 '14 at 18:40
• @dspyz the close-vote reason selected so far is "it's unclear what you're asking". so I guess that's the reason. – Martin Ender May 29 '14 at 18:43
• Even with the link, I'm still not sure what you want (possibly due to my lack of familiarity with functional languages). In general, language-specific tasks are looked down because not everyone can participate. – Kyle Kanos May 29 '14 at 18:43
• This is indeed very language specific. But the question is certainly clear, for someone with minimal knowledge of Haskell (very minimal in my case). – ugoren May 29 '14 at 19:01

# 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


## 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

## 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)


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


Online demo

## 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.

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 (.)