# Theory

What exactly do we mean by order of functions?

The order of data:

Order 0 : Non function data

Order 1 : Functions with domain and range of order 0

Order 2 : Functions with domain and range of order 1

Order k : Functions with domain and range of order k-1

With the above understanding, we can now define higher-order functions to be - Functions of order i, i>=2.

A higher-order function :

takes one or more functions as input, and

outputs a function

A typical example of this would be composite functions - i.e. if f and g are two functions then fog is the composite function defined as fog(x) = f(g(x)).

Often, while using inductive datatypes, we end up building them in a recursive nature (yet not explicitly recursive, the constructor acts upon an instance of a certain type to return one of the same type). Many a times, our opperations on such instances require us to traverse the datatype. This traversal can have multiple uses in practice, yet the traversal is still of the same type. Hence, it makes sense to try and use a higher order function for the traversal which will take as an argument, the opperation that is required to be done. As is seen, higher order functions are an integral part of inductive datatypes.