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.

### Familiar Higher Order FunctionsEdit

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 FunctionEdit

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 a 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 `|>`

OperatorEdit

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 FunctionsEdit

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 FunctionEdit

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 FunctionsEdit

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`

calls the `add`

function with one 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 WorksEdit

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

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

. F# use 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 SyntaxesEdit

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.