## Sunday, May 5, 2013

### Maps, Filters, and Folding ... Oh My! OR Yet Another Blog on Higher Order Functions

"Ay me! I see the ruin of my house.
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{1, 2, 3};

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

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

Stephen Hawkings in a Brief History of Time gives us the following story:

A well-known scientist once gave a public lecture on astronomy. He described how the earth orbits around the sun and how the sun, in turn, orbits around the center of a vast collection of stars called our galaxy. At the end of the lecture, a little old lady at the back of the room got up and said: "What you have told us is rubbish. The world is really a flat plate supported on the back of a giant tortoise." The scientist gave a superior smile before replying, "What is the tortoise standing on?" "You're very clever, young man, very clever," said the old lady. "But it's 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{1, 2, 3};

var numbers =
x.Select(t => "turtle");

#### F#

[1; 2; 3] |> List.map (fun _ -> "turtle")

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)

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)

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)

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)

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

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

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

[1; 2; 3] |> List.min