How to represent functions with multiple arguments in Hindley-Milner?

Question

I'm reading a functional programming tutorial called Professor Frisby's Mostly Adequate Guide to Functional Programming, the author gives an introduction to Hindley-Milner and several examples about it, one of them being:

//  reduce :: (b -> a -> b) -> b -> [a] -> b
var reduce = curry(function(f, x, xs) {
  return xs.reduce(f, x);
});

The first argument of reduce is a function, whose type signature is b -> a -> b, and that's the exact part that I don't understand. The above code is written in js, which means f should take two arguments and return one, like this:

function f(b, a) {
  return b + a;
}

Thus the type signature of f should be (b, a) -> b instead of b -> a -> b, right? f shouldn't be a first order function(implied by b -> a -> b), at least not in js.

So my question is, is this an error of the tutorial? If so, what's the correct way to represent (b, a) -> b in Hindley-Milner?

Answer 1

Since xs is annotated as [a], we can expect it to be a regular javascript array.

Therefore, the .reduce call inside the reduce function can be assumed to be Array.prototype.reduce.

This array method does not take a curried reducer function. So I would say: yes, the type annotation is wrong.

To fix it, either

1. Change the type annotation to // reduce :: ((b, a) -> b) -> b -> [a] -> b, like you suggested, or
2. Change the implementation to handle passing a curried function to Array.prototype.reduce:

//  reduce :: (b -> a -> b) -> b -> [a] -> b
var reduce = curry(function(f, x, xs) {
  return xs.reduce((b, a) => f(b)(a), x);
//                 ^^^^^^^^^^^^^^^^^
});