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.

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(a+h)-f(a) \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 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

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 << : ('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 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 will first apply f and then apply 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 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 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 + 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

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

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.