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 that does both.

Familiar Higher Order Functions

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:

$\lim _{x\to p}f(x)=L$

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:

$deriv(f(x))=\lim _{h\to 0}{f(x+h)-f(x) \over h}=f'(x)$

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 were a literal value, and call it just like 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

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 ints.

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)

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 << : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b.

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).

There's no reason why the compose function must be limited to numbers. Since it's generic, it can work with any datatype, such as int arrays, tuples, strings, 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 first applies f and then applies g on the result.

The |> Operator

The pipe forward operator, |>, is one of the most important operators in F#. The definition of the pipe forward 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 that 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 pipe forward 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

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 * x)         (* 2 * 2 = 4 *)
    |> ( fun x -> x + 5)         (* 4 + 5 = 9 *)
    |> ( fun x -> x.ToString() ) (* 9.ToString = "9" *)

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

A Timer Function

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 vary from machine to machine.

Currying and Partial Functions

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, let's 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

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 syntactic sugar for the explicit currying style shown above.

Two Pattern Matching Syntaxes

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.