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

7

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"

dspyz

Posted 2014-05-29T18:30:27.280

Reputation: 875

I'm not really sure what it is the above is doing (note that I'm not very familiar with functional programming). – Kyle Kanos – 2014-05-29T18:37:03.110

I added a link. Why so many close votes? Is this not a good programming puzzle? – dspyz – 2014-05-29T18:40:40.400

@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 – 2014-05-29T18:43:11.407

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 – 2014-05-29T18:43:37.653

Yeah, I guess this could be written in any functional language. But it lends itself more nicely to haskell. I'll remove the haskell tag. What's unclear about it? – dspyz – 2014-05-29T18:44:47.880

1This is indeed very language specific. But the question is certainly clear, for someone with minimal knowledge of Haskell (very minimal in my case). – ugoren – 2014-05-29T19:01:27.113

Actually, I'm starting to wonder if an optimal solution could be found with some sort of BFS. There's probably a lot of theory I don't know revolving around this sort of thing. – dspyz – 2014-05-29T19:07:33.587

Looks like an interesting problem, but perhaps out of reach for those unfamiliar with haskell. If possible, can you provide some examples of expected input and output? – Digital Trauma – 2014-05-29T19:15:33.303

I don't think the problem really lends itself to input and output. However, I think anything which matches the type signature and compiles (not including recursive functions and calls to "error") is correct. So, in that sense, you could say the input is the GHC compiler together with the type signature and the output is no compilation error – dspyz – 2014-05-29T19:20:01.073

Edited to clarify for people who are familiar with combinator calculus but not Haskell, or who know other FP languages but don't want to try finding proper definitions of flip and (.). I was tempted to delete the [tag:haskell] tag, but I wasn't sure why you had edited it back in after once editing it out. I don't think there's anything Haskell-specific about this other than the names of the functions: the type signature syntax is the same as SML, and the core question could be an exercise in To Mock a Mockingbird. – Peter Taylor – 2014-05-30T08:57:24.353

Answers

7

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

Peter Taylor

Posted 2014-05-29T18:30:27.280

Reputation: 41 901

3

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

Peter Taylor

Posted 2014-05-29T18:30:27.280

Reputation: 41 901

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

Peter Taylor

Posted 2014-05-29T18:30:27.280

Reputation: 41 901

1

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.

Kaya

Posted 2014-05-29T18:30:27.280

Reputation: 710

0

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

dspyz

Posted 2014-05-29T18:30:27.280

Reputation: 875