First Class Functions
Often considered to be a core necessity in functional programming, having first class functions refers to the fact that functions are treated like "first-class citizens", which means that functions are treated exactly as you would a basic data type, like an int. That means we can pass functions as arguments to other functions, have functions return functions as return values, assign functions to variables, etc. This is not possible in languages like C, which do not treat functions the same as other types.
We've seen how to assign functions to variables. Now let's take a look at how we might utilize the fact that functions are first class functions in OCaml. The kind community at Stack Overflow has generated a list of examples in other languages.
We will, like the Wikipedia page for first class functions, be using C in our comparisons because it is familiar and because it doesn't support first class functions. As we go through the concepts that first class functions allow us to implement, we will discover that it gets progressively more and more complicated to achieve similar results.
We've seen how to assign functions to variables. Now let's take a look at how we might utilize the fact that functions are first class functions in OCaml. The kind community at Stack Overflow has generated a list of examples in other languages.
We will, like the Wikipedia page for first class functions, be using C in our comparisons because it is familiar and because it doesn't support first class functions. As we go through the concepts that first class functions allow us to implement, we will discover that it gets progressively more and more complicated to achieve similar results.
Partially Applied Functions
In a first class language like OCaml, partially applying functions is related to currying. Here is an explanation of the difference. A partially applied function is one where we fix one or more of the arguments (but not all as that would be using the function).
Let's take a look at partially applying the addition operator (+), a simple example.
In a first class language like OCaml, partially applying functions is related to currying. Here is an explanation of the difference. A partially applied function is one where we fix one or more of the arguments (but not all as that would be using the function).
Let's take a look at partially applying the addition operator (+), a simple example.
Recall that the addition operator (+) is an int -> int -> int function, which means that it takes two ints as arguments. Let's fix one of the arguments to be 4. We can do this by only passing in one argument to (+) instead of the usual 2.
|
(+) 4;; - : int -> int = <fun> |
Note that OCaml informs us that it is totally valid to pass only one argument to (+). The return value is a function that takes only 1 int and outputs an int. It would take its argument, add 4 (the argument we've fixed), and return the result.
Let's see this in action. |
let plus4 = (+) 4;; val plus4 : int -> int |
So we have defined a new function that is a more specific instance of an old function in a process called currying, or partial application. Let's see how we might achieve similar results in C.
|
int plus4(int x) |
This is similar, but more equivalent to the following OCaml
|
let plus4 (x : int) = x + 4;; |
Higher Order Functions
So while partial application is cool in that we have the return value of an operation be a function, we can do more cool things with functions. A higher order function is a function that both returns a function as well as takes a function as an argument. Let's at a look at the very simple, useless idea that follows.
So while partial application is cool in that we have the return value of an operation be a function, we can do more cool things with functions. A higher order function is a function that both returns a function as well as takes a function as an argument. Let's at a look at the very simple, useless idea that follows.
Consider the basic operations on integers, adding, subtracting, etc. Now we want a function that takes any of these operations and partially applies 4 to them. Meaning that when we pass in (+) as an argument, we now get the plus4 function from above. Let's do this in OCaml.
|
let apply4 (f : int -> int -> int) = f 4;; val apply4 : (int -> int -> int) -> int -> int = <fun> |
And let's partially apply apply4 to get plus4 from before.
|
let plus4 = apply4 (+);; val plus4 : int -> int = <fun> |
This seems trivial, because the example is trivial. However, having higher order functions allows us to do amazing things like map, which the code is written here. We'll cover matching and recursion next, but we'll see that map is used a ton.
|
let rec map : ('a -> 'b) -> 'a list -> 'b list = fun f lst -> val map : ('a -> 'b) -> 'a list -> 'b list = <fun> |
We can't pass in functions as arguments in C, but can achieve almost similar results by using function pointers.
int apply4 (int (*f)(int, int), int x)
{
return f(4, x);
}
Anonymous and Nested Functions
We've already seen anonymous functions in OCaml and thanks to treating all functions as first class citizens, we can pass these as arguments to other functions. How fun!
We've already seen anonymous functions in OCaml and thanks to treating all functions as first class citizens, we can pass these as arguments to other functions. How fun!
let plus4 = apply4 (fun x y -> x + y - 4 + 4 - 4 + 4);;
val plus4 : int -> int = <fun>
This is something we can't do in C. To achieve this, we actually need to name our random function to pass it around.
int helper(int x, int y)
{
return x + y - 4 + 4 - 4 + 4;
}
int plus4(int x)
{
return apply4(helper, x);
}
Non-local Variables and Closures
The last result of first class results is that we can refer to non-local, non-global variables and functions and, as a result, achieve simply implemented closures.
Closures are functions that reference things outside their immediate scope. This general definition conveys no actual meaning, so let's take a look at examples.
The last result of first class results is that we can refer to non-local, non-global variables and functions and, as a result, achieve simply implemented closures.
Closures are functions that reference things outside their immediate scope. This general definition conveys no actual meaning, so let's take a look at examples.
We can do the following in OCaml:
let example10 =
let x = 6 in
(+) 4 x
;;
val example10 : int = 10
The x =6 is out of the immediate scope of the (+) 4 x. What's difficult about doing this in C? Well... The first part of our OCaml code states that our variable x only has local scope. Which means that we can't do the following.
int x = 6;
int example10 = 4 + x;
In fact, in order to have the proper scoping of variables, we need to take an entirely different route. Instead, I'll link the Wikipedia section that deals with closures, which is well worth reading. The solution is a mess.
The power of first class functions extends far beyond these trivial examples that I've just simply for demonstration, but hopefully the concepts have come across. And first class languages extend far beyond OCaml--Javascript, Perl, Python, Smalltalk all allow you to harness the power of having concise(r) code thanks to the power of first class functions.