The tiger now hath seized the gentle hind;
Insulting tyranny begins to jut
Upon the innocent and aweless throne.
Welcome destruction, blood, and massacre!
I see, as in a map, the end of all."
-- Shakespeare, Richard III
Act II, Scene IV, Lines 49-54
This is taken from my presentation called, "Maps, Filters, and Folding. Oh my!" given at the Chicago Code Camp on April 27th, 2013.
f ◦ g
By higher order functions, we are talking about functions that take functions. In other words we are talking about f ◦ g.
Mapping
Our first higher order function is f : A → B, called the mapping function.
In a mapping function everything in A has a value that it maps to through the function f to B. Thus we can write f : A → B.
Mapping example - Identity
The identity function takes a value and maps it to the value given. In other words it does nothing.
C#
var x = new List
var numbers = from number in x
select number;
F#
let x = [1; 2; 3]
let numbers = List.map (fun n -> n) x
OR
let x = [1; 2; 3]
let numbers = x |> List.map id
Haskell
map (\x -> x) [1, 2, 3]
OR
[x | x <- 2="" 3="" font="">
OR
map id [1, 2, 3]
C
int* mapIdentity(int* list, int length) {
int result[length];
int i;
for (i = 0; i < length; i++) {
result[i] = list[i];
}
return result;
}
Mapping example - Turtles All the Way Down
If you want to create a function, which would describe a world in which everything is a Turtle you could use the following.
C#
var x = new List
var numbers =
x.Select(t => "turtle");
F#
[1; 2; 3] |> List.map (fun _ -> "turtle")Haskell
map (\_ -> "turtle") [1, 2, 3]
Mapping example - Shift Letters
Suetonius in The Twelve Caesars gives use the following about Julius Caesar:
If he had anything confidential to say, he wrote it in cipher, that is, by so changing the order of the letters of the alphabet, that not a word could be made out. If anyone wishes to decipher these, and get at their meaning, he must substitute the fourth letter of the alphabet, namely D, for A, and so with the others.
If we wanted to create a simple shifting function we could use the following.
C#
var caesar =
String.Concat(
"DOG".Select(
c => (char)(c + 13)));
F#
"DOG"
|> List.ofSeq
|> List.map (fun c -> char(int c + 13))
|> List.toArray
|> (fun s -> System.String s)
Haskell
map (\c -> chr (ord c + 13)) "DOG"
Filtering
Our second higher order function is f : A → if (f(A)) then B, called filtering.
In filtering, not everything in A which goes through the function f has a value in B. Thus we say that f filters A into B or f : A → if (f(A)) then B.
Filtering example - Odds only
Say we want a function which will only let Odd values into a club. We could use the following as a bouncer.
C#
var x = new List{1, 2, 3};
var odd = x.Where(
(a) => a % 2 == 1);
F#
[1; 2; 3] |> List.filter (fun x -> x % 2 = 1)
Haskell
filter (\x -> mod x 2 == 1) [1, 2, 3]
OR
filter odd [1, 2, 3]
Filtering example - Strings longer than 7
Say you want a function which will only let strings that are greater than 7 in length.
C#
var x = new List{
"Scarecrow",
"Tin Man",
"Cowardly Lion"};
var moreThanSeven =
x.Where((a) => a.Length > 7);
F#
["Scarecrow"; "Tin Man"; "Cowardly Lion"]
|> List.filter (fun x -> String.length x > 7)
Haskell
filter (\x -> length x > 7)
["Scarecrow", "Tin Man", "Cowardly Lion"]
Filtering example - Divisors of 6
In number theory it is common to want to know if some is a divisor of a number.
C#
var x =
new List{1, 2, 3, 4, 5};
var divisor =
x.Where((a) => 6 % a == 0);
F#
[1..5] |> List.filter (fun x -> 6 % x = 0)
Haskell
filter (\x -> mod 6 x == 0) [1..5]
Folding
Our third and finial higher order function is folding. Folding is when you have a set of values and you run them through a function f and get one value out of the function, f : A → a. Max, sum, average, ... are all examples of folding.
Folding example - Sum
A common problem with a set of number is finding the total, this is also called summing.
Since addition is associative, it does not matter if we fold from the left or from the right. If we were doing subtracts, it would matter. 5 - 2 = 3, but 2 - 5 = -3.
C#
var x = new List{1, 2, 3};
var s = x.Sum();
F#
[1; 2; 3] |> List.fold (fun acc x -> acc + x) 0
OR
[1; 2; 3] |> List.sum
Haskell
foldl (\acc x -> acc + x) 0 [1, 2, 3]
OR
sum [1, 2, 3]
Folding example - Counting
It is funny once you get into really high mathematics you find that a lot the same problems that you study earlier, come up again with fancier names and more abstract ideas. Combinatorics is a branch of mathematics which is concerned with grouping and counting items. We can use folding to create a counting function.
C#
var x = new List{1, 2, 3};
var c = x.Count();
F#
[1; 2; 3] |> List.fold (fun acc _ -> acc + 1) 0
OR
[1; 2; 3] |> List.length
Haskell
foldl (\acc _ -> acc + 1) 0 [1, 2, 3]
OR
length [1, 2, 3]
Folding example - Min
It is quite a common problem to want to find the minimum value of a given set. Again, we can use a folding function to solve this problem.
C#
var x = new List{1, 2, 3};
var m = x.Min();
F#
[1; 2; 3] |> List.fold (
fun m x -> if m > x then x else m)
System.Int32.MaxValue
OR
Haskell
foldr1 (\m x -> if m > x then x else m) [1, 2, 3]
OR
minimum [1, 2, 3]
