Any difference between First Class Function and High Order Function

Question

I'm wondering whether/what difference between First Class Function and High Order Function.

I read through those two wiki pages and they looks rather similar. If they talking about same, why need two terminologies?

Tried to google but have not found any useful thing.

Solution 1

There is a difference. When you say that a language has first-class functions, it means that the language treats functions as values – that you can assign a function into a variable, pass it around etc. Higher-order functions are functions that work on other functions, meaning that they take one or more functions as an argument and can also return a function.

The “higher-order” concept can be applied to functions in general, like functions in the mathematical sense. The “first-class” concept only has to do with functions in programming languages. It’s seldom used when referring to a function, such as “a first-class function”. It’s much more common to say that “a language has/hasn’t first-class function support”.

The two things are closely related, as it’s hard to imagine a language with first-class functions that would not also support higher-order functions, and conversely a language with higher-order functions but without first-class function support.

Solution 2

First class functions are functions that are treated like an object (or are assignable to a variable).

Higher order functions are functions that take at least one first class function as a parameter, or return at least one first class function.

Solution 3

They're different.

First class functions

Values in a language that are handled uniformly throughout are called "first class". They may be stored in data structures, passed as arguments, or used in control structures.

Languages which support values with function types, and treat them the same as non-function values, can be said to have "first class functions".

Higher order functions

One of the consequences of having first class functions is that you should be able to pass a function as an argument to another function. The latter function is now "higher order". It is a function that takes a function as an argument.

The canonical example is "map"

map :: (a -> b) -> [a] -> [b]
map f []     = []
map f (x:xs) = f x : map f xs

That is, it takes a function, and an array, and returns a new array with the function applied to each element.

Functional languages -- languages where functions are the primary means of building programs -- all have first class functions. Most also have higher order functions (very rare exceptions being languages like Excel, which can be said to be functional, but not higher order).

Solution 4

In addition to the previous answers, note that a language with first-class functions automatically enables the expression of higher-order functions (because you can pass functions as parameters like any other value).

On the other hand, you can imagine languages that support higher-order functions, but do not make functions first-class (and where parameters that are functions are treated specially, and different from "ordinary" value parameters).

So the presence of first-class functions (as a language feature) implies the presence of higher-order functions, but not the other way round.

Solution 5

First Class functions can:

• Be stored in variables
• Be returned from a function.
• Be passed as arguments into another function.

High Order Function is a function that returns another function.

For example:

function highOrderFunc() {
  return function () {
    alert('hello');
  };
}

View more solutions

Comments

[Simon]

I think one thing get me easily confused is that they are closely related.

[Ben]

@Simon I think the key to avoiding confusion is to remember that a language either has first-class functions (you can also talk about "first-class" other things, like first-class classes, etc), or it doesn't. So you never talk about a particular function being first-class or not. OTOH, when you say a function is higher-order or not, that just says whether or not it operates on functions, so "higher-order-ness" is a property of each individual function. So "has first-class functions" is a property of a language, and "is higher-order" is a property of a function.

[Simon]

Thanks Don. It's comprehensive. And I think phase "One of the consequences" indicate a kind of relationship between those two.

[Simon]

Exactly Ben. I was thinking those two are both a property for function hence I was confused. Thanks your comments.

[Tac-Tics]

Also, it's good to keep in mind that "first-class functions" are NOT the same as closure support. For example, in C supports "first-class functions" via function pointers. However, C does not support any notion of nested function, and so, does not support closures.

[ATHER]

Can you please give an example where an higher order function is not a first class function. ( I thought both are same. )

[Andreas Rossberg]

@ATHER, I don't have a concrete example of a language that would make such a design choice for functions as such. But something similar is the case e.g. with templates in C++: templates are higher-order (you can have "template template parameters"), but not first class values, i.e., templates cannot be parameters to ordinary functions. Similarly with e.g. modules/functors in ML.

[Honinbo Shusaku]

@AndreasRossberg Would Java 8 not be a valid answer to his question? Functions are not first-class citizens, but Java methods can receive functions (through functional interfaces), as described by you as "parameters that are functions are treated specially, and different from "ordinary" value parameters."

[wlnirvana]

@Tac-Tics the definitions are certainly subjective and open to debate, but I personally prefer to think that C only supports higher order functions (via function pointers). However, first-class functions are not supported because functions are inferior to other value types like int or char, in the sense that they cannot be explicitly defined (by a function body) wherever you want.

[Gokul N K]

The way you(@Ben) summed up 'So "has first-class functions" is a property of a language, and "is higher-order" is a property of a function is awesome.' Changing first-class functions to has first-class functions was a masterstroke.