For example, the following function definition contains several duplicates of the subexpression x — 1:

By factoring out a subexpression a(x), this expression can be simplified:

where a(x) = x — 1.

The factoring of subexpressions, such as x-1, is the simplest form of factoring available to a programmer. The F# function equivalent to the original, unfactored expression is:

> let f x =
    (x - 1.0 - (x - 1.0) * (x - 1.0)) ** (x - 1.0);;
val f : float -> float
> f 5.0;;
val it : float = 20736.0

The F# function equivalent to the factored form is:

> let f x =
    let a = x - 1.0
    (a - a * a) ** a;;
val f : float -> float

> f 5.0;;
val it : float = 20736.0

By simplifying expressions, factoring is a means to manage the complexity of a program. The previous example only factors a subexpression but, in functional languages such as F#, it is possible to factor out higher-order functions.

As we have just seen, the ability to factor out common subexpressions can be useful. However, functions are first-class values in functional programming languages like F# and, consequently, it is also possible to factor out common sub-functions. In fact, this technique turns out to be an incredibly powerful approach to software engineering that is of particular importance in the context of scientific computing.

Consider the following functions that compute the sum and the product of a semi-inclusive range of integers [X₀, X₁), respectively:

> let rec sum_range xO xl =
    if xO = xl then 0 else xO + sum_range (xO + 1) xl;;
val sum_range : int -> int -> int

Figure 2.1. The fold_range function can be used to accumulate the result of applying a function f to a contiguous sequence of integers, in this case the sequence [1,9).

> let rec product_range xO xl =
    if xO = xl then 1 else
      xO * product_range (xO + 1) xl;;
val product_range : int -> int -> int

For example, the product_range function may be used to compute 5! as the product of the integers [1,6):

> product_range 1 6;;
val it : int = 120

The sum_range and product_range functions are very similar. Specifically, they both apply a function (integer add + and multiply *, respectively) to 1 before recursively applying themselves to the smaller range [xo + l, xi) until the range contains no integers, i.e. X₀ = x₁.

This commonality can be factored out as a higher-order function fold_range:

> let rec fold_range f xO xl accu =
    if xO = xl then accu else
      f xO (fold_range f (xO + 1) xl accu);;
val fold_range :
(int -> 'a -> 'a) -> int -> int -> 'a -> 'a

The fo1d_range function accepts a function f, a range specified by two integers x0 and xl and an initial value accu. Application of the fold_range function to mimic the sum_range or product_range functions begins with a base case in accu (0 or 1, respectively). If X₀ = x₁ then accu is returned as the result. Otherwise, the fold_range function applies f to both 1 and the result of a recursive call with the smaller range [l + l,u). This process, known as a right fold because f is applied to the rightmost integer and the accumulator first, is illustrated in figure 2.1.

The sum_range and product_range functions may then be expressed more simply in terms of the fold_range function by supplying a base case (0 or 1, respectively) and operator (addition or multiplication, respectively)^[9]:

> let sum_range xO xl = fold_range (+) xO xl 0;;
val sum_range : int -> int -> int

> let product_range xO xl = fold_range { *) xO xl 1;;
val product_range : int -> int -> int

These functions work in exactly the same way as the originals:

> product_range 1 6;;
val it : int = 120

but their commonality has been factored out into the fold_range function. Note how succinct the definitions of the sum_range and product_range functions have become thanks to this factoring.

In addition to simplifying the definitions of the sum_range and product_range functions, the fold_range function may also be used in new function definitions. For example, the following higher-order function, given a length n and a function f, creates the list containing the n elements (f (0), f (l),..., f(n- 1)):

> let list_init n f =
    fold_range (fun h t -> f h :: t) o n [];;
val list_init : int -> (int -> 'a) -> 'a list

This list_init function uses the fold_range function with a λ-function, an accumulator containing the empty list [] and a range [0,n). The λ-function prepends each f h onto the accumulator t to construct the result. For example, the list_init function can be used to create a list of squares:

> list_init 5 (fun i -> i*i);;
val it : int list = [0; 1; 4; 9; 16]

The functionality of this list_init function is already provided in the F# standard library in the form of the List. init function:

> List.init 5 (fun i -> i*i);;
val it : int list = [0; 1; 4; 9; 16]

In fact, this functionality of the List. init function can be obtained more clearly using sequence expressions and comprehensions (described in section 1.4.4):

> [ for i in 0 .. 4 ->
      i * i];;
val it : int list = [0; 1; 4; 9; 16]

As we have seen, the nesting and factoring of functions and variables can be used to simplify programs and, therefore, to help manage intrinsic complexity. In addition to these approaches to program structuring, the F# language also provides two different constructs designed to encapsulate program segments. We shall now examine the methodology and relative benefits of the forms of encapsulation offered by modules and objects.

Properties and members are written using the syntax:

member object. member args = ...

Record and variant types may be augmented with member functions using the type ... with ... syntax. For example, a record representing a 2D vector may be supplemented with a member to compute the vector's length:

> type vec2 = { x: float; y: float } with
    member r.Length = sqrt(r.x * r.x + r.y * r.y);;

Note that the method name r. Length binds the current object to r in the body of the method definition.

The length of a value of type vec2 may then be computed using the object oriented syntax:

> {x = 3.0; y = 4.0}.Length;;
val it : float =5.0

The member Length, which accepts no arguments, is called a property.

> type vec2 = {mutable x: float; mutable y: float} with

member r.Length
        with get () =
          sqrt(r.x * r.x + r.y * r.y)

        and set len =
          let s = len / r.Length
          r.x <- s * r.x;
          r.y <- s * r.y;;

> let r = {x = 3.0; y = 4.0};;
val r : vec2

> r.Length <- 1.0;;
val it : unit = ()

> r;;
val it : vec2 = {x=0.6; y=0.8}

> type vec2 = {mutable x: float; mutable y: float} with
    member r.Item
      with get(d) =
        match d with
        | 0 -> r.x
        | 1 -> r.y
        | _ -> invalid_arg "vec2.get"
      and set d v =
        match d with
        | 0 ->r.x<-v
        | 1 -> r.y <- v
        | _ -> invalid_arg "vec2.set";;

> let r = {x=4.0; y=4.0};;
val r : vec2

> r.[0] >- 3.0;;
val it : unit = ()

> r;;
val it : vec2 = {x=3.0; y=4.0}

> type vec2 = { X: float; y: float } with
    static member (+) (a, b) =
      {x = a.x + b.x; y = a.y + b . y};;

> {x = 2.0; y = 3.0} + {x = 3.0; y = 4.0};;
val it : vec2 = {x = 5.0; y = 7.0}

In conventional object-oriented programming languages, the vec2 type would have been defined as an ordinary class. There are two different ways to define ordinary classes in F#.

> type vec2 =

    val private x_ : float
    val private y_ : float

    new(x) =
      {x_ = x; y_ = 0.0}

    new(x, y) =
      {x_ = x; y_ = y}
    member r.x = r.x_
    member r.y = r.y_
    member r.Length =
      sqrt(r.x * r.x + r.y * r.y);;

> vec2(3.0, 4.0).Length;;
val it : float = 5.0

> type vec2(x : float, y : float) =

    member r.x = x

member r.y = y
       member r.Length =
         sqrt(r.x * r.x + r.y * r.y);;

> vec2(3.0, 4.0).Length;;
val it : float = 5.0

match object with
| : ? class -> ...

match object with
| : ? class as x -> f x

> box 12;;
val it : obj = 12

The ability to handle functions as values opens up a whole new way of programming. When making extensive use of functional values, the ability to compose these values in different ways can be very useful.

Higher-order functions and currying are often combined to maximize the utility of function composition. Higher-order functions that work by composing applications of other functions (including their argument functions) are sometimes referred to as combinators [13]. Such functions can be very useful when designed appropriately.

The practical benefits of combinators are most easily elucidated by example. In fact, we have already seen some combinators such as the derivative function d (from section 1.6.4).

The F# language provides three useful combinators that are written as operators:

These combinators will be used extensively in the remainder of this book, particularly the | > combinator.

A surprising amount can be accomplished using combinators. A simple combinator that applies a function to its argument twice may be written:

> let apply_2 f =
    f < < f;;
val apply_2 : ('a -> 'a) -> ('a -> 'a)

For example, doubling the number five twice is equivalent to multiplication by four:

> apply_2 ((*) 2) 5;;
val it : int = 20

A combinator that applies a function four times may be written elegantly in terms of the existing apply_2 combinator:

> let apply_4 f =
    apply_2 apply_2 f;;
val apply_4 : ('a -> 'a) -> ('a -> 'a)

As a generalization of this, a combinator can be used to nest many applications of the same function:

> let rec nest n f x =
    match n with
    | 0 -> x
    | n -> nest (n - 1) f (f x);;
val nest : int -> ('a -> 'a) -> 'a -> 'a

For example, nest 3 f xgivesf(f(f x)):

> nest 3 ((*) 2) 1;;
val it : int = 8

Recursion itself can be factored out into a combinator by rewriting the target function as a higher-order function that accepts the function that it is to call, rather than as a recursive function. The following y combinator can be used to reconstruct a one-argument recursive function:

> let rec y f x =
    f (y f) x;;
val y : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b

Note that the argument f to the y combinator is itself a combinator. For example, the factorial function may be written in a non-recursive form, accepting another factorial function to call recursively as its first argument:

> let factorial factorial = function
    | 0 -> 1
    | n -> n * factorial(n - 1);;
val factorial : (int -> int) -> int -> int

This process of rewriting a recursive function as a combinator to avoid explicit recursion is known as "untying the recursive knot" and makes it possible to stitch functions together, injecting new functionality between function calls. For example, this will be used to implement recursive memoization in section 6.1.4.2.

Applying the y combinator yields the usual factorial function:

> y factorial 5;;
val it : int = 120

Composing functions using combinators makes it easy to inject new code in between function calls. For example, a function to print the argument can be injected before each invocation of the factorial function:

> y (factorial >> fun f n -> printf "%d
" n; f n) 5;;
5
4
3
2
1
0
val it : int = 120

This style of programming is useful is many circumstances but is particularly importance in the context of asynchronous programming, where entire computations are formed by composing fragments of computation together using exactly this technique. This is so useful that the F# language recently introduced a customized syntax for asynchronous programming known as asynchronous workflows.

The task of measuring the time taken to apply a function to its argument can be productively factored into a time combinator. The .NET Stopwatch class can be used to measure elapsed real time with roughly millisecond (0.001s) accuracy. The following time combinator accepts a function f and its argument x and times how long it takes to apply f to x, printing the time taken and returning the result f x:

> let time f x =
    let timer = new System.Diagnostics.Stopwatch()
    timer.Start()
    try f x finally
    printf "Took %dms
" timer.ElapsedMilliseconds;;
val time : ('a -> 'b) -> 'a -> 'b

Note the use of try . . finally to ensure that the time taken is printed even if the function application f x raises an exception.

For example, the time taken to construct a 10⁶-element list:

> time (fun () -> [1 .. 1000000]) ();;
Took 44 6ms

Computations can also be timed from F# interactive sessions by executing the #time statement:

> #time;;
--> Timing now on

> [1 . . 1000000];;
Real: 00:00:00.619, CPU: 00:00:00.640, GC genO: 6,
genl: 2, gen2: 1

> #time;;

--> Timing now off

This has the advantage that it prints both elapsed real time and CPU time (which will be discussed in section 8) as well as the number of different generations of garbage collection that were invoked (quantifying how much the computation stressed the garbage collector). However, our time combinator has the advantage that it can be placed inside computations uninvasively in order to time certain parts of a computation.

Our time combinator will be used extensively throughout this book to compare the performance of different functions. In particular, chapter 8 elaborates on the time combinator in the context of performance measurement, profiling and optimization.

section 2.2 introduced the concept of a fold. This is a higher-order function that applies a given function argument to a set of elements, accumulating a result. In the previous example, the fold acted upon an implicit range of integers but folds are most often associated with container types (such as lists and arrays), a subject covered in detail in chapter 3.

Folds over data structures are often categorized into left and right folds, referring to starting with the left-most (first) or starting with the right-most (last) element, respectively.

The addition operator can be folded over a container in order to sum the int elements of a container xs. With a left fold this is written in the form:

fold_left ( + ) 0 xs

With a right fold this is written in the form:

fold_right ( + ) xs 0

Note the position of the initial accumulator 0, on the left for a left-fold and on the right for a right-fold.

For example, if xs is the sequence (1,2,3) then the left-fold computes ((0 + 1) + 2) + 3 whereas a right-fold computes 1 + (2 + (3 + 0)).

Maps are a similar concept. These higher-order functions apply a given function argument / to a set of elements x_i to create a new set of elements y_i = f(x_i). Container types (e.g. lists and arrays) typically provide a map function.

Maps and folds are generic algorithms used in a wide variety of applications. The data structures in the F# standard library provide maps and folds where appropriate, as we shall see in chapter 3.

Figure 2.2. Developing an application written entirely in F# using Microsoft Visual Studio 2005.

To create a new project in Visual Studio click File

To add an F# source code file to the new project, right-click on the project's name in the Solution Explorer pane and select Add

An important advantage of Visual Studio is the graphical throwback of inferred type information. For example, figure 2.3 shows the inferred type vec2 of the variable r in some F# source code. As type information is not explicit in F#, this functionality is extremely useful when developing F# programs.

Once written, F# source code can be executed in two different ways: a solution or project may be built to create an executable or the code may be entered into a running F# interactive mode.

A Visual Studio solution or project may be built to create an executable. To build an executable press CTRL+SHIFT+B. More often, solutions are built and executed immediately. This can be done in one step by pressing F5 to build and run a solution in debug mode or CTRL+F5 to build and run a solution in release mode. As the names imply, debug mode can provide more information when a program goes wrong as opposed to release mode which executes more quickly.

Figure 2.4. A project's properties page allows the compiler to be controlled.

Various options can be adjusted in the Project Properties window (see figure 2.4), to control the way an executable is built:

These options are set in the Project Properties window.

Although a detailed tutorial on Visual Studio is beyond the scope of this book it is worth mentioning the subject of debugging.

The static typing provided by the F# language goes a long way in eliminating errors in programs before they are run. However, there are still cases when a program will fail during its execution. In such cases, a detailed report of the problem can be essential in debugging the application.

Visual Studio provides a great deal of debugging support to help the programmer. In the case of F#, an application that fails (typically due to the raising of an exception that is never caught and handled) gives immediate throwback on where the exception came from and what it contained. Breakpoints can be set the in source code, to stop execution when a particular point is reached. The values of variables may then be inspected.

One of the most useful capabilities of the Visual Studio debugger is the ability to pause a program when an exception is thrown even if it is subsequently caught. This functionality is enabled through the Debug

In addition to building executable applications, F# provides a powerful interactive mode that allows code to be executed without being built beforehand.

In addition to conventional project building, F# provides an interactive way to execute code, called the F# interactive mode. This mode is useful for trying examples when first learning the F# programming language and for testing snippets of code from programs during development.

Scientists and engineers typically use two separate kinds of programming language:

F# is the first language to combine the best of both worlds with the F# interactive mode.

Before the F# interactive mode can be used within Visual Studio, it must be selected in the Add-in Manager (available from the menu Tools

The F# interactive mode can be started by pressing ALT+ENTER in the editor window. Lines of code from the editor can be evaluated in an interactive mode by pressing ALT+'. Selected blocks of code can be evaluated in an interactive mode by pressing ALT+ENTER. When typing directly into an F# interactive session, evaluation is forced by ending the last line with;;.

Double semicolons

The examples given so far in this book have been written in the style of the F# interactive mode and, in particular, have ended with;; to force evaluation. These double semicolons are not necessary in compiled code (i.e. in .fs and .fsx files).

Figure 2.5. The Add-in Manager is used to provide the F# interactive mode.

For example, the two function definitions can be interpreted simultaneously in an interactive session, with only a single;; at the end:

> let fl x =
    if x < 3 then print_endline "Less than three"
  let f2 x =
    if x < 3 then "Less" else "Greater";;
val fl : int -> unit
val f2 : int -> string

When compiled, programs can be written entirely without;;.

> #USe "foo.fS";;

> #load "foo.fs";;

> type length = Meters of float;;

> fsi.AddPrinter(fun (Meters x) -> sprintf "%fm" x);;

> Meters 5.4;;
val it : length = 5.400000m

One of the great benefits of the common language run-time that underpins .NET is the ability to interoperate with dynamically linked libraries (DLLs) written in other .NET languages. In particular, this opens up the wealth of tools available for mainstream languages like C# including the GUI Windows Forms designers integrated into Visual Studio and the automatic compilation of web services into C# functions. A specific example of this will be discussed in chapter 10 in the context of web services.

An F# program that requires a C# library is easily created using Visual Studio:

The name.dll DLL can be referenced from the source code of an F# program with:

#r "name.dll"

In this case, the directory of the DLL must be added to the search path before the DLL is referenced.

Figure 2.6. Creating a new C# class library project called ClassLibraryl inside a new solution called Interop.

Figure 2.7. Creating a new F# project called Projectl also inside the Interop solution.

Figure 2.8. Setting the startup project ofthe Interop solution to the F# project Project1 rather than the C# project ClassLibraryl as a DLL cannot be used to start an application .

For example, the following adds a member function foo () to the C# DLL:

using System;
using System.Collections.Generic;
using System.Text;

namespace ClassLibraryl
{
    public class Classl
    {
        public static void foo()
        {
            Console.WriteLine("foo");
        }
    }
}

The following F# source code adds the default location of the debug build of the C# DLL to the search path, references the DLL and then calls the foo () function:

#light
System.Environment.CurrentDirectory <-
  __SOURCE_DIRECTORY__
#1 @"..ClassLibrarylinDebug"

#r "ClassLibraryl.dll"
ClassLibraryl.Classl.foo()

The syntax @" ..." is used to quote a string without having to escape it manually. This can be compiled or run interactively. When evaluated in an interactive solution, this F# code produces the following output:

> #light;;

> System.Environment.CurrentDirectory <-
    __SOURCE_DIRECTORY__;;
val it : unit = ()

> #I @"..ClassLibrarylinDebug";;
--> Added 'C:Visual Studio 2005ProjectsInterop
Projectl..ClassLibrarylinDebug' to library include
path

> #r "ClassLibraryl.dll";;
--> Referenced 'C:Visual Studio 2005ProjectsInterop
Proj ectl..ClassLibrarylinDebugClassLibraryl.dll'

> ClassLibraryl.Classl.foo();;
Binding session to 'C:Visual Studio 2005Projects
InteropProjectl..ClassLibrarylinDebug
ClassLibraryl.dll'...
foo

val it : unit = ()

Note that the invocation of the C# function from F# prints "foo" as expected. The same procedure can be used to add C# projects containing autogenerated code from the Windows Forms designer or by adding Web References to the C# project.