# F Sharp Programming/Higher Order Functions

F# : Higher Order Functions |

A higher-order function is a function that takes another function as a parameter, or a function that returns another function as a value, or a function which does both.

## Contents

### Familiar Higher Order Functions[edit]

To put higher order functions in perspective, if you've ever taken a first-semester course on calculus, you're undoubtedly familiar with two functions: the limit function and the derivative function.

The limit function is defined as follows:

The limit function, `lim`

, takes another function `f(x)`

as a parameter, and it returns a value `L`

to represent the limit.

Similarly, the derivative function is defined as follows:

The derivative function, `deriv`

, takes a function `f(x)`

as a parameter, and it returns a completely different function `f'(x)`

as a result.

In this respect, we can correctly assume the limit and derivative functions are higher-order functions. If we have a good understanding of higher-order functions in mathematics, then we can apply the same principles in F# code.

In F#, we can pass a function to another function just as if it was a literal value, and we call it just like we call any other function. For example, here's a very trivial function:

```
let passFive f = (f 5)
```

In F# notation, `passFive`

has the following type:

`val passFive : (int -> 'a) -> 'a`

In other words, `passFive`

takes a function `f`

, where `f`

must take an `int`

and return any generic type `'a`

. Our function `passFive`

has the return type `'a`

because we don't know the return type of `f 5`

in advance.

```
open System
let square x = x * x
let cube x = x * x * x
let sign x =
if x > 0 then "positive"
else if x < 0 then "negative"
else "zero"
let passFive f = (f 5)
printfn "%A" (passFive square) // 25
printfn "%A" (passFive cube) // 125
printfn "%A" (passFive sign) // "positive"
```

These functions have the following types:

```
val square : int -> int
val cube : int -> int
val sign : int -> string
val passFive : (int -> 'a) -> 'a
```

Unlike many other languages, F# makes no distinction between functions and values. We pass functions to other functions in the exact same way that we pass ints, strings, and other values.

#### Creating a Map Function[edit]

A map function converts one type of data to another type of data. A simple map function in F# looks like this:

```
let map item converter = converter item
```

This has the type `val map : 'a -> ('a -> 'b) -> 'b`

. In other words, `map`

takes two parameters: an item 'a, and a function that takes an `'a`

and returns a `'b`

; map returns a `'b`

.

Let's examine the following code:

```
open System
let map x f = f x
let square x = x * x
let cubeAndConvertToString x =
let temp = x * x * x
temp.ToString()
let answer x =
if x = true then "yes"
else "no"
let first = map 5 square
let second = map 5 cubeAndConvertToString
let third = map true answer
```

These functions have the following signatures:

```
val map : 'a -> ('a -> 'b) -> 'b
val square : int -> int
val cubeAndConvertToString : int -> string
val answer : bool -> string
val first : int
val second : string
val third : string
```

The `first`

function passes a datatype `int`

and a function with the signature `(int -> int)`

; this means the placeholders `'a`

and `'b`

in the map function both become `int`

s.

The `second`

function passes a datatype `int`

and a function `(int -> string)`

, and `map`

predictably returns a `string`

.

The `third`

function passes a datatype `bool`

and a function `(bool -> string)`

, and `map`

returns a `string`

just as we expect.

Since our generic code is typesafe, we would get an error if we wrote:

```
let fourth = map true square
```

Because the `true`

constrains our function to a type `(bool -> 'b)`

, but the `square`

function has the type `(int -> int)`

, so it's obviously incorrect.

#### The Composition Function (`<<`

operator)[edit]

In algebra, the composition function is defined as `compose(f, g, x) = f(g(x))`

, denoted *f o g*. In F#, the composition function is defined as follows:

```
let inline (<<) f g x = f (g x)
```

Which has the somewhat cumbersome signature `val << : ('b -> 'c) -> ('a -> 'b) -> 'a -> 'c`

.

If I had two functions:

- f(x) = x^2
- g(x) = -x/2 + 5

And I wanted to model *f o g*, I could write:

```
open System
let f x = x*x
let g x = -x/2.0 + 5.0
let fog = f << g
Console.WriteLine(fog 0.0) // 25
Console.WriteLine(fog 1.0) // 20.25
Console.WriteLine(fog 2.0) // 16
Console.WriteLine(fog 3.0) // 12.25
Console.WriteLine(fog 4.0) // 9
Console.WriteLine(fog 5.0) // 6.25
```

Note that `fog`

doesn't return a value, it returns another function whose signature is `(float -> float)`

.

Of course, there's no reason why the compose function needs to be limited to numbers; since it's generic, it can work with any datatype, such as `int array`

s, `tuple`

s, `string`

s, and so on.

There also exists the `>>`

operator, which similarly performs function composition, but in reverse order. It is defined as follows:

```
let inline (>>) f g x = g (f x)
```

This operator's signature is as follows: `val >> : ('a -> 'b) -> ('b -> 'c) -> 'a -> 'c`

.

The advantage of doing composition using the `>>`

operator is that the functions in the composition are listed in the order in which they are called.

```
let gof = f >> g
```

This will first apply `f`

and then apply `g`

on the result.

### The `|>`

Operator[edit]

The pipeline operator, `|>`

, is one of the most important operators in F#. The definition of the pipeline operator is remarkably simple:

```
let inline (|>) x f = f x
```

Let's take 3 functions:

```
let square x = x * x
let add x y = x + y
let toString x = x.ToString()
```

Let's also say we had a complicated function which squared a number, added five to it, and converted it to a string? Normally, we'd write this:

```
let complexFunction x =
toString (add 5 (square x))
```

We can improve the readability of this function somewhat using the pipeline operator:

```
let complexFunction x =
x |> square |> add 5 |> toString
```

`x`

is piped to the `square`

function, which is piped to `add 5`

method, and finally to the `toString`

method.

### Anonymous Functions[edit]

Until now, all functions shown in this book have been named. For example, the function above is named `add`

. F# allows programmers to declare nameless, or anonymous functions using the `fun`

keyword.

```
let complexFunction =
2 (* 2 *)
|> ( fun x -> x + 5) (* 2 + 5 = 7 *)
|> ( fun x -> x * x) (* 7 * 7 = 49 *)
|> ( fun x -> x.ToString() ) (* 49.ToString = "49" *)
```

Anonymous functions are convenient and find a use in a surprising number of places.

#### A Timer Function[edit]

```
open System
let duration f =
let timer = new System.Diagnostics.Stopwatch()
timer.Start()
let returnValue = f()
printfn "Elapsed Time: %i" timer.ElapsedMilliseconds
returnValue
let rec fib = function
| 0 -> 0
| 1 -> 1
| n -> fib (n - 1) + fib (n - 2)
let main() =
printfn "fib 5: %i" (duration ( fun() -> fib 5 ))
printfn "fib 30: %i" (duration ( fun() -> fib 30 ))
main()
```

The `duration`

function has the type `val duration : (unit -> 'a) -> 'a`

. This program prints:

Elapsed Time: 1 fib 5: 5 Elapsed Time: 5 fib 30: 832040

*Note*: the actual duration to execute these functions will vary from machine to machine.

### Currying and Partial Functions[edit]

A fascinating feature in F# is called "currying", which means that F# does not require programmers to provide all of the arguments when calling a function. For example, lets say we have a function:

```
let add x y = x + y
```

`add`

takes two integers and returns another integer. In F# notation, this is written as `val add : int -> int -> int`

We can define another function as follows:

```
let addFive = add 5
```

The `addFive`

function calls the `add`

function with one of its parameters, so what is the return value of this function? That's easy: `addFive`

returns another function which is waiting for the rest of its arguments. In this case, addFive returns a function that takes an `int`

and returns another `int`

, denoted in F# notation as `val addFive : (int -> int)`

.

You call `addFive`

just in the same way that you call other functions:

```
open System
let add x y = x + y
let addFive = add 5
Console.WriteLine(addFive 12) // prints 17
```

#### How Currying Works[edit]

The function `let add x y = x + y`

has the type `val add : int -> int -> int`

. F# uses the slightly unconventional arrow notation to denote function signatures for a reason: arrows notation is intrinsically connected to currying and anonymous functions. Currying works because, behind the scenes, F# converts function parameters to a style that looks like this:

```
let add = (fun x -> (fun y -> x + y) )
```

The type `int -> int -> int`

is semantically equivalent to `(int -> (int -> int))`

.

When you call `add`

with no arguments, it returns `fun x -> fun y -> x + y`

(or equivalently `fun x y -> x + y`

), another function waiting for the rest of its arguments. Likewise, when you supply one argument to the function above, say 5, it returns `fun y -> 5 + y`

, another function waiting for the rest of its arguments, with all occurrences of x being replaced by the argument 5.

Currying is built on the principle that each argument actually returns a separate function, which is why calling a function with only part of its parameters returns another function. The familiar F# syntax that we've seen so far, `let add x y = x + y`

, is actually a kind of syntatic sugar for the explicit currying style shown above.

#### Two Pattern Matching Syntaxes[edit]

You may have wondered why there are two pattern matching syntaxes:

Traditional Syntax | Shortcut Syntax |
---|---|

```
let getPrice food =
match food with
| "banana" -> 0.79
| "watermelon" -> 3.49
| "tofu" -> 1.09
| _ -> nan
``` |
```
let getPrice2 = function
| "banana" -> 0.79
| "watermelon" -> 3.49
| "tofu" -> 1.09
| _ -> nan
``` |

Both snippets of code are identical, but why does the shortcut syntax allow programmers to omit the `food`

parameter in the function definition? The answer is related to currying: behind the scenes, the F# compiler converts the `function`

keyword into the following construct:

```
let getPrice2 =
(fun x ->
match x with
| "banana" -> 0.79
| "watermelon" -> 3.49
| "tofu" -> 1.09
| _ -> nan)
```

In other words, F# treats the `function`

keyword as an anonymous function that takes one parameter and returns one value. The `getPrice2`

function actually returns an anonymous function; arguments passed to `getPrice2`

are actually applied and evaluated by the anonymous function instead.