Code Golf (sort of): a Functional Puzzle

Question

Here's a puzzle: define some higher-order function f such that, using only f and parentheses, you can define the three higher-order functions const, id and bothOn.

Those three functions could be defined in a straightforward way and in the Haskell programming language as follows:

-- takes two arguments, ignores the second and returning the first"
const a _ = a

-- takes one argument returns it:
id a = a

-- takes three arguments: the first is applied to the third and the result of applying 
-- the second to the third:
bothOn f g x = f x (g x)

You're limited to your choice of programming language here of course (lisp or haskell would be fine choices even if you don't know either).

And those of you who know what I'm up to (you know who you are) should only submit answers they thought up themselves ;-)

EDIT: Forgot to mention, the answer with the definition for f with fewest characters wins. Also show how you defined the three functions in terms of f.

---

EDIT: Well look at me with egg on my face. It was only after posting this question and trying to implement some known solutions to this problem in haskell that I realized that a statically-typed language isn't particularly well-suited to the untyped lambda calculus.

The infinite type errors... I could not make them stop. But I would be really interested if any haskell type system gurus out there can make a working implementation.

So for those who are still wondering, I was trying to trick you into defining a single-combinator base: essentially, in my understanding, a single function that is sufficient to be a turing complete system.

The three functions you were asked to define with your function were taken from the SKI Combinator calculus, which is a combinator base consisting of only three combinators. So by defining a single combinator (function) which is capable of defining S and K (I can be derived from S and K) you can easily prove that you have a 1-combinator base.

Here is a paper that goes over the derivation of one of the several known single-base combinators. And here is an interesting pair of esoteric languages Iota and Jot which is built on a single combinator and consists of only two symbols.

I'm thinking they should ask me to write the problem for the ICFP contest next year...

Answer 1

Does this qualify?

JavaScript, 74 84 characters

function f(){x=arguments,l=x.length;[a,b,c]=x;return l==3&&a(c)(b(c))||a}

Readable version:

function f() {
    var x = arguments, length = x.length;
    [first, second, third] = x;

    return (length == 3 && first(third)(second(third))) || first;
}

Uses destructuring assignment from JavaScript 1.7 to break apart arguments into a,b,c.

---

JavaScript, 102 characters

Here's another version that defines all the three functions first. Although code-golf is usually more concerned with output than the internal workings of the code, but here goes a little bit bigger but more technically correct version that relies on the arity to determine which function to call:

function f()[x=arguments,function(a)a,function(a,_)a,function(g,h,x)g(x)(h(x))][x.length].apply('',x)

Readable version:

function f() {
    var id_ = function(a) a;
    var const_ = function(a, _) a;
    var bothOn_ = function(g, h, x) g(x)(h(x));

    var functions = [id_, const_, bothOn_];
    var functionIndex = arguments.length - 1;

    return functions[functionIndex].apply(null, arguments);
}

Answer 2

A completely disappointing, but technically correct version ;)

{-# LANGUAGE FlexibleInstances, OverlappingInstances, UndecidableInstances #-}
class F a where
    f :: a
instance F (a -> a) where
    f a = a
instance F (a -> a -> a) where
    f a _ = a
instance F ((a -> b -> c) -> (a -> b) -> a -> c) where
    f f0 g x = f0 x (g x)

const :: a -> a -> a
const = f

id :: a -> a
id = f

bothOn :: (a -> b -> c) -> (a -> b) -> a -> c
bothOn = f

A more satisfying version would be to build one out of the iota combinator

import Control.Applicative
k x y = x
s x y z = x z (y z)
iota x = x s k
-- iota x = x (<*>) pure

but unfortunately I don't think you can get interesting programs built out of it or type restricted versions of it to typecheck.

If we flip it around a bit you can make some headway though:

f :: (((e -> a) -> (e -> a -> b) -> e -> b) -> (c -> f -> c) -> d) -> d
f x = flip (<*>) `x` pure

const :: a -> b -> a
const = f f

flippedBothOn :: (a -> b) -> (a -> b -> c) -> a -> c
flippedBothOn = f (f f)

Answer 3

Haskell: 36 chars

---

The spec does not require that these functions be as general as they can be, so here's my cheap take. (Use the -XNoImplicitPrelude command line option if you insist.)

f _ _ x=x
id=f()f
const=f()
bothOn=f

---

> id () == ()
True
> const () () == ()
True
> bothOn const id () == ()
True

Answer 4

... Iota?

Python (72 chars)

    i=lambda x:x(lambda a:lambda b:lambda c:a(c)(b(c)))(lambda a:lambda b:a)
#  |         |         |         |         |         |         |         |
#  |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
#  0    5   10   15   20   25   30   35   40   45   50   55   60   65   70

idFunc     = i(i)
constFunc  = i(i(i(i)))
bothOnFunc = i(i(i(i(i))))

assert idFunc('foo') == 'foo'
assert constFunc('foo')('bar') == 'foo'
assert bothOnFunc(lambda a:lambda b:a+b)(lambda p:p*p)(4) == 20

Answer 5

Python (43 chars)

(cheating) (based on the JS solution)

    f=lambda a,b=0,*c:c and a(c[0],b(c[0]))or a
#  |         |         |         |         |
#  |    |    |    |    |    |    |    |    |
#  0    5   10   15   20   25   30   35   40

idFunc = f
constFunc = f
bothOnFunc = f

assert idFunc('foo') == 'foo'
assert constFunc('foo', 'bar') == 'foo'
assert bothOnFunc(lambda a,b: a+b,  lambda p: p*p,  4) == 20