"
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:
- it takes a function as an input
- 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.
- identity function (do nothing)
- add the value to it self
- add 1 to the value
- 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):
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):
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.
