Higher Order Functions

A higher order function (HOF) is a function that receives functions as an argument or returns functions.

Key point: Functions are first-class objects.

Example in C++:

bool compare(int x, int y) {
  return x > y;
}

int main() {
  vector<int> v = { ... };
  sort(v.begin(), v.end(), compare); // sort is a higher order function
}

Example: The predefined function map applies a function to each element of a list.

map :: (a -> b) -> [a] -> [b]

map f [] = []
map f (x:xs) = f x : map f xs

map odd [1..5]
[True, False, True, False, True]

Example: The predefined function (.) returns the composition of two functions:

(.) :: (b -> c) -> (a -> b) -> (a -> c)

(f . g) x = f (g x)

(reverse . sort) [5, 3, 5, 2]
[5, 5, 3, 2]

Example: The apli2 function applies a function to an element twice.

apli2 :: (a -> a) -> a -> a

apli2 f x = f (f x)
apli2 f = f . f

apli2 sqrt 16.0
2.0