*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

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]