Difference between higher order and curried functions

Question

I'm reading a book, Functional Programming Using F#, which says (page 33), in the section Declaration of higher-order functions

We have seen higher-order built-in functions like (+) and (<<)

and at the end of the section

Higher-order functions may alternatively be defined by supplying the arguments as follows in the let-declaration:

let weight ro s = ro * s ** 3.0;;

However there were some helpful comments at the bottom of a question that I asked earlier today (which was originally titled "When should I write my functions as higher order functions") that seem to throw some doubt on whether these examples are in fact higher-order functions.

The wikipedia definition of higher-order function is:

a higher-order function (also functional form, functional or functor) is a function that does at least one of the following: (i) take one or more functions as an input; (ii) output a function.

On the one hand, I can see that functions like (+), and weight might be regarded as higher order functions because given a single argument they return a function. On the other hand I can see that they are properly regarded as curried functions. I'm learning F# as a self-study project and would like to get the concepts clear, so the answers and discussion on this site are particularly helpful.

My question is, what is the right term for these functions, and, perhaps more importantly, how do people normally use the terms "higher order functions" and "curried functions"?

Answer 1

I think you could say that curried function is a higher-order function that returns a function as the result.

A curried function is a function with a type that looks like a -> b -> c - and if you add parentheses (which does not change the type) a -> (b -> c), you can see that this is also higher-order.

However, you can write functions that are higher-order but not curried. For example, the following simple function takes some function f and calls it twice:

let runTwice f = f(); f();

This function has a type (unit -> unit) -> unit, so it is not curried (it just takes some input and returns unit value), but it is higher-order because the argument is a function.

Although functions like (+) are technically higher-order (the type is int -> (int -> int)), I do not think that they are good examples of higher-order, because you do not usually use them in the higher-order way (but it is occasionally useful). More typical examples of higher-order functions are functions like List.map that take functions as arguments.

Answer 2

Roughly speaking, the curried functions are a subset of the higher-order functions. Higher-order functions accept functions as arguments or return functions in their results. Curried functions are multivariate functions written in curried form as a function accepting the first argument and returning a function that accepts the second argument and so forth.

That is what Tomas says above. However, I think there is a subtlety here. I don't think all functions that return a function are curried and I think that Tomas' statement "if you add parentheses (which does not change the type)" is inaccurate in F#.

Specically, consider a function that takes an argument, has a side-effect and then returns another function that takes another argument and returns a result:

let f x =
  printfn "%d" x
  fun y -> x+y

F# infers the type:

val f : int -> (int -> int)

Note that it has put seemingly-redundant parentheses in there, I believe, precisely because there is a subtle difference between those types.

Furthermore, although this function returns a function as its result I do not think it qualifies as a curried function because of that side effect. This is not a multivariate function rewritten in curried form...