6
\$\begingroup\$

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"
\$\endgroup\$
  • \$\begingroup\$ I'm not really sure what it is the above is doing (note that I'm not very familiar with functional programming). \$\endgroup\$ – Kyle Kanos May 29 '14 at 18:37
  • \$\begingroup\$ I added a link. Why so many close votes? Is this not a good programming puzzle? \$\endgroup\$ – dspyz May 29 '14 at 18:40
  • \$\begingroup\$ @dspyz the close-vote reason selected so far is "it's unclear what you're asking". so I guess that's the reason. \$\endgroup\$ – Martin Ender May 29 '14 at 18:43
  • \$\begingroup\$ 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. \$\endgroup\$ – Kyle Kanos May 29 '14 at 18:43
  • 1
    \$\begingroup\$ This is indeed very language specific. But the question is certainly clear, for someone with minimal knowledge of Haskell (very minimal in my case). \$\endgroup\$ – ugoren May 29 '14 at 19:01
6
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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 (.)
\$\endgroup\$

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.