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:
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 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 a two parameters: an item 'a, and a function that takes an
'a and returns a
'b; map returns a
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
first function passes a datatype
int and a function with the signature
(int -> int); this means the placeholders
'b in the map function both become
second function passes a datatype
int and a function
(int -> string), and
map predictably returns a
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
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 (
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
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
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 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
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
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()
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, 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
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).
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
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) )
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
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.