A Haskell function is higher order if and only if its type has more than one arrow?

Question

A professor teaching a class I am attending claimed the following.

A higher-order function could have only one arrow when checking its type.

I don't agree with this statement I tried to prove it is wrong. I tried to set up some function but then I found that my functions probably aren't higher-order functions. Here is what I have:

f x y z = x + y + z
f :: a -> a->  a -> a

g = f 3
g :: a -> a -> a

h = g 5
h :: a -> a

At the end of the day, I think my proof was wrong, but I am still not convinced that higher-order functions can only have more than one arrow when checking the type.

So, is there any resource or perhaps someone could prove that higher-order function may have only one arrow?

Answer 1

Strictly speaking, the statement is correct. This is because the usual definition of the term "higher-order function", taken here from Wikipedia, is a function that does one or both of the following:

• takes a function as an argument, or
• returns a function as its result

It is clear then that no function with a single arrow in its type signature can be a higher-order function, because in a signature a -> b, there is no "room" to create something of the form x -> y on either side of an arrow - there simply aren't enough arrows.

(This argument actually has a significant flaw, which you may have spotted, and which I'll address below. But it's probably true "in spirit" for what your professor meant.)

The converse is also, strictly speaking, true in Haskell - although not in most other languages. The distinguishing feature of Haskell here is that functions are curried. For example, a function like (+), whose signature is:

a -> a -> a

(with a Num a constraint that I'll ignore because it could just confuse the issue if we're supposed to be counting "arrows"), is usually thought of as being a function of two arguments: it takes 2 as and produces another a. In most languages, which all of course have an analagous function/operator, this would never be described as a higher-order function. But in Haskell, because functions are curried, the above signature is really just a shorthand for the parenthesised version:

a -> (a -> a)

which clearly is a higher-order function. It takes an a and produces a function of type a -> a. (Recall, from above, that returning a function is one of the things that characterises a HOF.) In Haskell, as I said, these two signatures are one and the same thing. (+) really is a higher-order function - we just often don't notice that because we intend to feed it two arguments, by which we really mean to feed it one argument, result in a function, then feed that function the second argument. Thanks to Haskell's convenient, parenthesis-free, syntax for applying functions to arguments, there isn't really any distinction. (This again contrasts from non-functional languages: the addition "function" there always takes exactly 2 arguments, and only giving it one will usually be an error. If the language has first-class functions, you can indeed define the curried form, for example this in Python:

def curried_add(x):
    return lambda y: x + y

but this is clearly a different function from the straightforward function of two arguments that you would normally use, and usually less convenient to apply because you need to call it as curried_add(x)(y) rather than just say add(x,y).

So, if we take currying into account, the statement of your professor is strictly true.

Well, with the following exception, which I alluded to above. I've been assuming that something with a signature of the form

a -> b

is not a HOF*. That of course doesn't apply if a or b is a function. Often, that function's type will include an arrow, and we're tacitly assuming here that neither a or b contains arrows. Well, Haskell has type synonyms, so we could easily define, say:

type MyFunctionType = Int -> Int

and then a function with signature MyFunctionType -> a or a -> MyFunctionType is most certainly a HOF, even though it doesn't "look like one" from just a glance at the signature.

*To be clear here,a and b refer to specific types which are as yet unspecified - I am not referring to an actual signature a -> b which would mean a polymorphic function that applies to any types a and b, which would not necessarily be functions.

Answer 2

Your functions are higher order. Indeed, take for example your function:

f :: a -> a -> a -> a
f x y z = x + y + z

This is a less verbose form of:

f :: a -> (a -> (a -> a))

So it is a function that takes an a and returns a function. A higher order function is a function that (a) takes a function as parameter, or (b) returns a function. Both can be true at the same time. Here your function f returns a function.

A function thus always has type a -> b with a the input type, and b the return type. In case a has an arrow (like (c -> d) -> b), then it is a higher order function, since it takes a function as parameter.

If b has an arrow, like a -> (c -> d), then this is a higher order function as well, since it returns a function.