Higher Order Functions

"Do not confine your children to your own learning for they were born in another time."
--Hebrew Proverb

A higher order function is a function which does at least one of the following two things:

1. it takes a function as an input
2. it returns a function as an output

A normal working programmer more likely than not will use a higher order function in his normal day to day work.

Case 1: Mapping

Simple case in point, if you have use simple SELECT statement in SQL, you have used a higher order function.  A SELECT applies a function you give it against the input it is given from the FROM clause.  Let's use the following statement to illustration this point:


SELECT
    x AS 'value'
   ,(x + x) AS 'add to self'
   ,(x + 1) AS 'increment by 1'
   ,(x * 5) AS 'multiply by 5'
  FROM (
    VALUES (1),(2),(3),(4),(5)
  ) AS value(x)
;

The input given to the SELECT is 1, 2, 3, 4, and 5 from the FROM statement (using the VALUES statement and the AS to create a "table" with the values and a column called x, this will only work in SQL Server, because of the VALUES if you want to use it on a different platform use the UNION ALL for the different values).  We have 4 functions being applied by SELECT to the input given to it.

1. identity function (do nothing)
2. add the value to it self
3. add 1 to the value
4. multiply the value by 5

As one would expect the output is the following (from SQL fiddle):

VALUE	ADD TO SELF	INCREMENT BY 1	MULTIPLY BY 5
1	2	2	5
2	4	3	10
3	6	4	15
4	8	5	20
5	10	6	25

This is type of higher order function is called a mapping.

We can do the same thing in F# using the following code:

let values = [1; 2; 3; 4; 5];;

values |> List.map id;;
values |> List.map (fun x -> x + x);;
values |> List.map (fun x -> x + 1);;
values |> List.map (fun x -> x * 5);;


Using List.map we are able to apply a function against each member of the list, this is exactly what we did in the SQL above!  This F# code gives use the exact same output:


>val values : int list = [1; 2; 3; 4; 5]

> val it : int list = [1; 2; 3; 4; 5]
> val it : int list = [2; 4; 6; 8; 10]
> val it : int list = [2; 3; 4; 5; 6]
> val it : int list = [5; 10; 15; 20; 25]

Case 2: Filtering

Another simple case of everyday use of higher order functions would be the simple WHERE clause again from SQL.  The WHERE clause applies Boolean functions you give it against the input it gets from the FROM clause.  If the output of the Boolean function with the given input is true then the value is passed on, if it is false then it is filtered out.  Let's use the following statement to show this:


SELECT
    x AS 'is even'
  FROM (
    VALUES (1),(2),(3),(4),(5)
  ) AS value(x)
  WHERE (x % 2) = 0
;

This statement filters out the odd numbers using the modulo operation and compares the result against the value 0, thus if the number is divisible by 2 (and hence even) then it is include in the output given to the SELECT statement (which is doing a simple mapping using the identity function).  The output is again as one would expect (from SQL fiddle):

IS EVEN
2
4

This is called filtering in higher order functional terms.

We can do the same thing in F# using the following code:


let values = [1; 2; 3; 4; 5];
 
values |> List.filter (fun x -> x % 2 = 0);;

Again we are simply taking a list of values and by using List.filter we are filtering out the output using a function which compares the input against the modulo operation with 2 to see if the number is even.  This would give the following output:


>val values : int list = [1; 2; 3; 4; 5]

>val it : int list = [2; 4]

Case 3: Folding

Last simple case for today, when you need to apply an operation against a set of values and this operation should give you a single result say a SUM or AVG windowing function.  This is folding in higher order functional land.

Let's use the following SQL to explore this:


SELECT DISTINCT
    SUM(x) OVER () AS 'sum'
   ,AVG(x) OVER () AS 'average'
  FROM (
    VALUES (1),(2),(3),(4),(5)
  ) AS value(x)
;


We are folding the sum of 1, 2, 3, 4, and 5 into one value, 15, and the average value is 3.

As we can see in the following output  (from SQL fiddle):

SUM	AVERAGE
15	3

We can do the same thing in F# using the following code:


let values = [1; 2; 3; 4; 5];

values |> List.sum;;
(values |> List.fold (fun acc x -> acc + x) 0) / values.Length;;


For the sum we use the built in function List.sum to obtain the value.  For the average we sum using List.fold just to show how List.sum might be implemented.  Then we take the sum and divide it by the number of values we summed giving use the average.  This gives use the following output:


>val values : int list = [1; 2; 3; 4; 5]

> val it : int = 15
> val it : int = 3


There you have it higher order functions with examples in F# and SQL!

Sample code is on SQL Fiddle here and Try F# here.  Enjoy.