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);
//                 ^^^^^^^^^^^^^^^^^
});

Answer 2

I went through this tutorial myself and I think generally functions are assumed to be curried so f being b -> a -> b is perhaps counter-intuitive but not necessarily wrong AFAIK. (Take everything I say with a pinch of salt; I'm not an expert ;)

However the parentheses around f itself in the reduce signature gives an important clue to the reader (at least to the JavaScript reader) that f is a function:

reduce :: (b -> a -> b) -> b -> [a] -> b
          ^^^^^^^^^^^^^    ^    ^^^    ^
          1                2    3      4

1: f
2: reduction initial value
3: list to reduce
4: reduction result

Since f can be curried there is no guarantee that you'll receive all its arguments in one go. Of course in this particular case (a reducing function) most people would expect that f will be applied to both arguments (an accumulated value and a value) at the same time.

The function signature is merely a "declaration of intent" (at least in JavaScript):

• f takes two arguments.
• First argument must be a b type.
• Second argument must be a a type (which can be the same as b btw).
• The return value type is a b type.

What the function is supposed to do is not defined.

If b is a number then this definition of f is fine AFAIK: (although that'd be a very useless reducing function)

const f = b => a => 42