OCaml equivalent of javascript 'apply'

Question

It's been a while since I've coded OCaml, and I came across this problem which sounds simple but I'm having a mental block with solving:

Write a function that takes in a function f with a variable number of arguments that returns a boolean (i.e. f is of type 'a -> 'b -> 'c -> ... -> bool) and returns a function g that represents the negation of f (i.e. (f x1 x2 .. xn) == not (g x1 x2 .. xn) for all valid parameter sets).

It was inspired by the following code block which solves the problem in Javascript:

function negate(func) {
  return function() {
    return !func.apply(null, arguments);
  };
}

(from http://eloquentjavascript.net/1st_edition/chapter6.html)

However, I don't see a way to implement this in OCaml (the "arguments" keyword or equivalent is not available) because of the fact that the function f has no preset number of arguments. I have found links that talk about dealing with functions with variable numbers of arguments (such as https://blogs.janestreet.com/variable-argument-functions/) but I would like to know if there is a simpler / more 'natural' way to deal with this specific problem.

Answer 1

I am a JavaScript programmer and I have always maintained that variadic arguments are harmful. If we don't have variadic functions in JavaScript (just stay away from the arguments object), then every function in JavaScript typable in the Hindley Milner type system (minus API specific functions, like DOM functions) can be easily converted into an equivalent function in OCaml.

So what's the OCaml equivalent of the apply function? I believe that it's normal function application:

let apply f x = f x (* equivalent of apply in JavaScript *)

How is normal function application equivalent to the apply function in JavaScript? Consider:

let s f g x = f x (g x) (* the S combinator from the SKI combinator calculus *)

This function would be written in JavaScript as follows:

var s = function (f) {
    return function (g) {
        return function (x) {
            return f(x)(g(x));
        };
    };
};

Note that every function definition and function call is explicitly written in curried form.

This is the difference between JavaScript and OCaml:

1. In OCaml all the functions are curried by default and you have to be explicitly uncurry them.
2. In JavaScript all the functions are uncurried by default and you have to be explicitly curry them.

So, let's take a look at the uncurried variants of the S combinator. First, OCaml:

let s (f, g, x) = f (x, g (x)) (* sml convention is to use uncurried functions *)

The equivalent in JavaScript:

var s = function (f, g, x) {
    return f(x, g(x));
};

Note that normal function application is the same in both OCaml and JavaScript. For curried functions:

let result = s f g x (* equivalent to `((s f) g) x` *)

The equivalent in JavaScript:

var result = s(f)(g)(x);

For uncurried functions:

let result = s (f, g, x)

The equivalent in JavaScript:

var result = s(f, g, x);

So what about the apply function? How is that equivalent to normal function application?

In OCaml, you can do this:

let args   = (f, g, x) (* args is a tuple *)

let result = s args    (* normal function application *)

The equivalent in JavaScript is:

var args   = [f, g, x];           // args is an array

var result = s.apply(null, args); // normal function application

As you can see tuples in OCaml are equivalent to arrays in JavaScript. Arrays in JavaScript are versatile. They can be used as either lists or tuples, depending upon the context.

The args parameter given to apply can be any array-like object and it's treated as a single tuple argument. Every function in JavaScript can be thought of as a single argument function. Multi-parameter functions in JavaScript can be thought of as a single-parameter tuple argument function. The apply function of JavaScript is just a special form of normal function application.

So what does this imply? Consider:

var negate = function (f) {
    return function () {
        return !f.apply(null, arguments);
    };
};

If we consider arguments to be an implicit parameter of the inner function then the equivalent of the above function in OCaml is:

let negate f = fun arguments -> not (f arguments) (* arguments is explicit *)

This can be simplified to:

let negate f x = not (f x)

Now, you might say that this will only work for single argument functions. That's not the case. The type signature of negate is:

val negate : ('a -> bool) -> 'a -> bool

Hence, it can work for any type 'a including tuples. This is equivalent to JavaScript in which multi-parameter functions are just single-parameter tuple argument functions.

Finally, the only real problem is converting curried functions into uncurried functions so that you can negate them. Unfortunately, there's no generic way of uncurrying a function in OCaml. So you need a family of functions to uncurry curried functions of several arities:

let uncurry2 f (x, y) = f x y

let uncurry3 f (x, y, z) = f x y z

           .
           .
           .
           .

After negating the functions you can curry them back. However, just as with uncurry there's no way to generically curry a function. Hence, you again need a family of curry functions:

let curry2 f x y   = f (x, y)

let curry3 f x y z = f (x, y, z)

         .
         .
         .
         .

The only way to create generic curry or uncurry functions is to use dynamically typed languages (like Lisp or JavaScript) or dependently typed languages (like Idris or Agda). The type system of OCaml (the Hindley Milner type system) is too restrictive to allow such functions.

Answer 2

This isn't hard, but you have to write (and at call sites, select) an explicit definition for each arity by hand, as OCaml lacks the necessary machinery to abstract over similar definitions of different arities.

Note that this is a pattern that already exists in OCaml code: see List.map(2), List.iter(2), etc.

The definitions might look like:

let negate f = (fun a -> not (f a))
let negate2 f = (fun a b -> not (f a b))
let negate3 f = (fun a b c -> not (f a b c))
(* etc *)

Note that type systems that allow this kind of polymorphism are conceivable: in fact Typed Racket may be able to express this very definition.

Answer 3

A function that takes several arguments in ocaml is actually a function that takes one argument and return another function. It is curried.

What you want to do is possible with uncurried functions, ie functions that take only one argument (which might be a tuple):

For instance, you want f : (a * b * c) -> bool instead of f : a -> b -> c -> bool. But you have to "manually" transform your functions.

You can right functions like let uncurry f (x,y) = f x y but this is only transporting the problem because you have to do it for any number of arguments.

Maybe you could negate functions that take a list of arguments as argument. I mean I don't know the specifics of what you are trying to do.