The nest function is found in many technical computing environments. This combi-nator nests applications of its function argument f to a given value x a given number of times n. The nest function may be written:

> 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

Note that we have phrased the recursive call to nest such that it is tail recursive. An equivalent but non-tail-recursive implementation would have been f(nest (n - 1) f x).

For example, in the context of the numerical derivative combinator d and the example function f = x³ — x — 1 from section 1.6.4, the third derivative of f may be written:

> let f''' = nest 3 d f;;
val f''' : (float -> float)

The nest combinator has many uses.

Iterative algorithms sometimes terminate when an iteration leaves the result unchanged. This is known as iterating to fixed point. A fixed_point combinator can implement this functionality using recursion:

> let rec fixed_point f x =
    match f x with
    | f_x when x = f_x -> x
    | x -> fixed_point f x;;
val fixed_point : ('a -> 'b) -> 'a -> 'b

For example, the golden ratio may be expressed as the fixed point of the iteration

> fixed_point (fun x -> sqrt (1.0 + x)) 1.0;;
val it : float = 1.618033989

Note that this iterative algorithm does not terminate in theory. The function only terminated because the next result was rounded to the same float value, i.e. the result was unchanged to within the error of a floating point value.

In scientific computing, many algorithms act only upon values that lie within a specific range. For example, to sum the elements of a list that lie within the range [3... 6] we might filter out those elements first:

> [1 .. 10]
  |> List.filter (fun x y -> 3 <= y && y <= 6)
  |> List.fold_left (+) 0;;
val it : int = 18

or filter as we fold by specifying a more complicated function argument:

> [1 .. 10]
  |> List.fold_left
      (fun x y ->
        if 3 <= y && y <= 6 then x + y else x) 0;;
val it : int = 18

The former approach is less efficient because it allocates and then deallocates a temporary list. The latter approach is more efficient but less comprehensible. Consequently, it is useful to have a combinator that "propagates" a fold only when the argument lies within a specified range:

> let within xO x1 f accu x = combinator
    if xO <= x && x <= xl then f accu x else accu;;
val within :
  'a -> 'a -> ('b -> 'a -> 'b) -> 'b -> 'a -> 'b

For example, the within combinator can be used to filter out elements lying within a range without creating an intermediate data structure or resorting to sequences (which are also slower):

> List.fold_left (within 3 6 (+)) 0 [1 . . 10];;
val it : int = 18

Note that we have been careful to order the arguments to the within function such that currying can be exploited to simplify uses of this function in a left fold.

Higher-order functions can clearly be used to aggressively factor code without sacrificing clarity or performance. Indeed, clarity has arguably been improved in this case and, as we shall see in chapter 8, this is an excellent way to write efficient code.

Caching the results of computations to avoid recomputation can be a very effective optimization. This applies not only to complicated numerical computations but also to functions that are slowed by external limitations, such as database connectivity, web access and so on.

The Fibonacci function is the pedagogical example of a function that can be accelerated using caching:

> let rec fib = function
    | 0 | 1 as n -> n
    | n -> fib(n - 1) + fib(n - 2);;
val fib : int -> int

This function is slow to compute even small Fibonacci numbers, taking 0.222s to compute the 35^th Fibonacci number:

> time fib 35;;
Took 222ms
val it : int = 9227465

The fib function is heavily recursive, making two recursive calls almost every time it is invoked (each of which make two more recursive calls and so on). Consequently, the asymptotic complexity of this function is O(2ⁿ). As the function is slow to execute, the results can be productively cached for reuse.

> let memoize f =
    let m = Hashtbl.create 1
    fun x ->
      try m.[x] with Not_found ->
      let f_x = f x
      m.[x] <- f_x
      f _X;;
val memoize : ('a -> 'b) -> 'a -> 'b

> let mfib = memoize fib;;
val mfib: (int -> int)

> time mfib 35;;
Took 24 0ms
val it : int = 9227465

> time mfib 3 5;;
Took 0ms
val it : int = 9227465

> let fib fib = function
    | 0 [1 as n -> n
    | n -> fib(n - 1) + fib(n - 2);;
val fib : (int -> int) -> int -> int

> let memoize_rec f =
    let m = Hashtbl.create 1
    let rec f x =
      try m.[x] with Not_found ->
      let f_x = f f x
      m.[x] <- f_x
      f_x in
    f';;
val memoize : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b

> let mfib = memoize_rec fib;;
val mfib : (int -> int)

> time mfib 45;;
Took 2ms
val it : int = 1134903170

> let rec fib =
    memoize
      (function
        | 0 | 1 as n -> n
        | n -> fib(n - 1) + fib(n - 2));;
val fib : (int -> int) -> int -> int

> time mfib 45;;
Took 2ms
val it : int = 1134903170

Many problems can be solved using recursive bisection and the generic algorithm is known as binary search.

The following function splits a range that is assumed to bracket a change in the comparison function cmp and returns the subrange that brackets the change:

> let binary_search split cmp (x, c_x, y, c_y) =
    let m = split x y
    let c_m = cmp m
    match c_x = c_m, c_m = c_y with
    | true, false -> m, c_m, y, c_y
    | false, true -> x, c_x, m, c_m
    | _ -> raise Not_found;;
val binary_search :
  ('a -> 'a -> 'a) -> ('a -> 'b) -> 'a * 'b * 'a * 'b ->
    'a * 'b * 'a * 'b

Note that this function is careful to avoid recomputation of cmp with the same argument, in case this is a slow function. This is achieved by bundling the values of cmp x and cmp y in the range and reusing them in the subrange that is returned.

The choice of currying the function arguments split and cmp but coalescing the range into a 4-tuple might seem odd but this is, in fact, a careful design decision. Thanks to this design, the binary_search function can be partially applied with its function arguments to yield a function that maps ranges onto ranges. Consequently, such a partial application can then be used with combinators such as nest and fixed_point to control the recursive subdivision of ranges.

This function will be used in the context of root finding, in section 6.2.5.

The heaviside step function:

is a simple numerical function which may be implemented trivially in F#:

> let heaviside x =
    if x < 0.0 then 0.0 else 1.0;;
val heaviside : float -> float

This function is particularly useful when composed with other functions.

The Kronecker δ-function:

may be written as:

> let kronecker i j =
    if i = j then 1 else 0;;
val kronecker : 'a -> 'a -> int

However, this implementation is polymorphic, which may be undesirable because static type checking will not enforce the application of this function to integer types only. Consequently, we may wish to restrict the type of this function by adding an explicit type annotation:

> let kronecker (i : int) j =
    if i = j then 1 else 0;;
val kronecker : int -> int -> int

Erroneous applications of this function to inappropriate types will now be caught at compile-time by the F# compiler.

Computations involving trigonometric functions may be performed using the sin, cos, tan, asin(arcsin), acos (arccos), atan(arctan), atan2 (as for atan but accepting signed numerator and denominator to determine which quadrant the result lies in), cosh, sinh and tanh functions.

The conventional mathematical functions

Thus, a function to calculate the Gaussian may be written:

> let gaussian mu sigma (x : float) =
       let sqr x = x * x
       exp(- sqr(x - mu) / (2.0 * sqr sigma)) /
         (sqrt(2.0 * System.Math.PI) * sigma)
val gaussian : float -> float -> float -> float

As this implementation of the Gaussian function is curried, a function representing a probability distribution with a given µ and a may be obtained by partially applying the first two arguments:

> seq { for x in −1.0 .. 0.5 .. 1.0 ->
          gaussian 1.0 0.5 x };;

Figure 6.1. The first seven rows of Pascal's triangle.

val it : seq<float> =
  seq [0.0002676604; 0.008863696; 0.107981933;
       0.483941449; ...]

Many of the special functions can be productively written in curried form to allow their arguments to be partially applied.

The binomial coefficient

Naturally, this may be written directly in terms of the factorial function:

> let binomial n r =
    factorial n / (factorial r * factorial (n - r));;
val binomial bigint -> bigint -> bigint

For example, the binomial coefficients in the expansion of (a + b)⁶ are given by:

> [ for r in 0I .. 6I ->
      binomial 6I r ];;
val it : bigint list = [1I; 6I; 15I; 20I; 15I; 6I; 1I]

However, computing relatively small binomial coefficients requires the computation of large intermediate values due to the use of factorials. For example, the computation of

> time (loop 1000 (binomial 1000I)) 2I;;
Took 12123ms
val it : bigint = 499500I

This implementation of the binomial function is clearly a suitable candidate for algorithmic optimization.

The performance of this binomial function is most easily improved upon by computing Pascal's triangle, where each number in the triangle is the sum of its two "parents" from the row before (illustrated in figure 6.1). This may be represented as the recurrence relation:

When using finite precision arithmetic (e.g. the int type), computing binomial coefficients using Pascal's triangle is more robust than computing via factorials because the numbers involved now increase monotonically, only overflowing if the result overflows. Our example can then be computed using only machine precision integers, even on 32-bit machines.

The recurrence relation may be expressed as a recursive function:

> let rec binomial n r =
    if r = 0 || r = n then 1 else
    binomial (n - 1) r + binomial (n - 1) (r - 1);;
val binomial : int -> int -> int

This implementation of the binomial function is slightly faster than the factorial-based implementation, taking around 9ms to compute

> time (loop 1000 (binomial 1000)) 2;;
Took 8904ms
val it : int = 499500

Moreover, this is a divide and conquer algorithm amenable to memoization. Consequently, this binomial function is most easily optimized using the memoize com-binator from section 6.1.4.1, replacing the two curried arguments n and r with a single 2-tuple argument:

> let rec binomial =
    memoize
      (fun (n, r) ->
         if r = 0 || r = n then 1 else
         binomial(n - 1, r) + binomial(n - 1, r - 1));;
val binomial : (int * int -> int) -> int * int -> int

The resulting function is 65× faster than the first implementation at the same computation:

> time (loop 1000 (binomial 1000)) 2;;
Took 18 8ms
val it : int = 499500

let us examine some more sophisticated numerical functions.

The fixed_point and binary_search combinators from sections 6.1.2 and 6.1.5, respectively, can be used to implement a simple root finder by recursively subdividing a range that brackets the zero-crossing of a function:

> let find_root f x y =
    let split x y= (x+y) / 2.0
    let cmp x = compare (f x) 0.0
    (x, cmp x, y, cmp y)
    |> fixed_point (binary_search mid cmp);;
val find_root :
  (float -> float) -> float ->
    float -> float * int * float * int

For example, this function can be used to find the root of the function f{x) = x³ — x — 1 that lies in the range x ϵ {1... 2}:

> find_root (fun x -> x**3.0 - x - 1.0) 1.0 2.0;;
val it : float * int * float * int =
  (1.324717957, −1, 1.324717957, 1)

This result contains two very similar values of a; that bracket the root.

When writing programs to perform scientific computations, programmers should constantly consider the possibility of factoring out higher-order functions. Although functional programming languages are becoming increasingly popular, the vast majority of the existing literature covers fundamental algorithms written in a relatively unfactored and typically very imperative style.

The ∇ operator in mathematics computes the vector derivative of a function of many variables:

In F#, a function of many variables may be represented by the type:

val f : vector -> float

The vector value of ∇ f may be computed as the numerical derivative of f with respect to each variable using the same procedure as the one-dimensional numerical derivative function d from section 1.6.4.

A numerical approximation to the partial derivative of f with respect to its i ^th variable may be calculated using the following function:

> let partial_d f_xs f xs i xi =
    xs. [i] <- xi + delta
    try (f xs - f_xs) / delta finally
    xs . [i] <- xi;;

val d :
  float -> (vector -> float) -> vector -> int ->
    float -> float

where f_xs is the value of f xs and xi is the original value of x_i . This definition of the partial_d function allows f_xs, f and xs to be partially applied such that the resulting closure can be applied to the conventional mapi function to obtain the grad.

Note the use of the try ... finally construct to ensure that the state change to the array xs is undone even if the application f xs causes an exception to be raised.

The vector value of ∇f can then be computed using a simple combinator:

> let grad f xs =
    Vector.mapi (partial_d (f xs) f xs) xs;;
val grad : (vector -> float) -> vector -> vector

The efficiency of this grad function is likely to be dominated by the cost of applying f. This implementation has factored out the computation of f xs for the original xs, so this grad function only applies the f function T(n + 1) times.

This grad function can be used in many important numerical algorithms, such as the minimization of multidimensional functions.

The task of altering the variables of a function in order to minimize or maximize the value of the function is common in scientific computing. By convention, this class of problems are generally referred to as minimization problems. There are many algorithms for function minimization and they are broadly classified into local and global minimization. Local function minimization refers to the task of tweaking the variables from an initial set in order to find a maximum that is close to the initial values by monotonically decreasing the value of the function. In contrast, global function minimization refers to grossly altering the variables in an attempt to find the highest possible value of the function, typically allowing the value of the function to increase in the interim period.

One of the simplest local function maximization algorithms is called gradient descent. This algorithm repeatedly steps in the direction of the downward gradient ∇f to monotonically decrease the value of the function f . In order to achieve good performance, the step size λ is increased when the function is successfully decreased and the step is accepted and λ is drastically decreased if the function increases:

for some « 1 and > 1.

> let descend alpha beta f f'
    (lambda, xs: vector, f_xs) =

let xs_2 = xs - lambda $* f xs
       let f_xs_2 = f xs_2
       if f_xs_2 >= f_xs then
         alpha * lambda, xs, f_xs
       else
         beta * lambda, xs_2, f_xs_2;;
   val descend :
     float -> float -> (vector -> 'a) ->
        (vector -> vector) -> float * vector * 'a ->
          float * vector * 'a

Note that this descend function is designed to work with the fixed_point combinator from section 6.1.2 after partial application of alpha, beta, f, and f'.

In the interests of numerical robustness, the algorithm is careful to decrease λ if the function stays the same to within numerical error. When numerical accuracy is exhausted, f (x) stops changing and λ is monotonically decreased until it underflows to 0 at which point the accumulator (λ, x, f (x)) stops changing and the fixed_point combinator terminates.

The gradient descent algorithm applies the fixed_point combinator to this auxiliary function descend with suitable arguments and extracting the vector of variables x from the result:

> let gradient_descent f f ' xs =
    let _, xs, _ =
      fixed_point (descend 0.5 1.1 f f) (1.0, xs, f xs)
    xs;;
val gradient_descent :
  (vector -> 'a) -> (vector -> vector) -> vector ->
    vector

For example, consider the function f(x, y) = x⁴ + y² — x³y — 3x:

> let f v =
       let x, y = v. [0] , v. [1]
       x**4.0 + y**2.0 - x**3.0 * y - 3.0 * X;;
val f : vector -> float

A local minimum of f(x,y) starting from (x,y) = (0,0) is most easily found using the numerical grad function from section 6.2.6:

> gradient_descent f (grad f) (vector [0.0; 0.0]);;
val it : vector = [1.1274523; 0.716579731]

Many important algorithms in scientific computing can be composed from simpler functions using higher-order functions, currying and combinators.

Numerical computing often requires the definition of various special functions. Several useful functions such as sin(x) and arctan(x) are built-in but many more functions must be defined in terms of these. The gamma function:

This function arises particularly in the context of factorial functions because it is a generalization of factorial:

Also, the gamma function satisfies the following recurrence relation:

A good numerical approximation to Γ(z) for

Using the first six terms gives the following implementation of ln(Γ(x)):

> let q =
    [| 75122.6331530; 80916.6278952; 36308.2951477;
       8687.24529705; 1168.92649479; 83.8676043424;
       2.50662827511 |]
    |> Array.map (fun x -> complex x 0.0);;
val q : Math.complex array

> let gamma z =
    let f x = complex x 0.0
    let z2 = z * z
    let z4 = z2 * z2
    let pow zl z2 = exp(z2 * log zl)
    (q.[0] + q. [1] * z + q. [2] * z2 + q. [3] * z * z2 +
     q.[4] * z4 + q. [5] * z * z4 + q. [6] * z2 * z4) /
      (z * (f 1.0 + z) * (f 2.0 + z) * (f 3.0 + z) *
       (f 4.0 + z) * (f 5.0 + z) * (f 6.0 + z)) *
      pow (z + f 5.5) (z + f 0.5) * exp(-(z + f 5.5));;
val gamma : Math.complex -> Math.complex

We can test this function on some well-known identities involving the gamma function. For example, Γ(6) = 5! = 120:

> gamma (complex 6.0 0.0);;
val it : Math.complex = 120.Or + O.Oi

The following identity also holds:

> gamma(complex (1.0 / 3.0) 0.0) *
    gamma(complex (2.0 / 3.0) 0.0);;
val it : Math.Complex = 3.627598728r+0.Oi

> 2.0 * System.Math.PI / sqrt 3.0;;
val it : float = 3.627598728

This and other similar functions have a wide variety of uses in scientific computing.

Wavelet transforms have many applications in science and engineering. These applications rely largely upon the on the unique time-frequency properties of this class of transforms. Wavelet transforms are most broadly classified into continuous and discrete wavelet transforms. Continuous wavelet transforms are widely used in the sciences and engineering for signal analysis, most notably time-frequency analysis. Discrete wavelet transforms are widely used in computer science and information theory for signal coding, particularly as a way of preconditioning signals to make them more amenable to compression.

All wavelet transforms consider their input (taken to be a function of time) in terms of oscillating functions (wavelets) that are localised in terms of both time and frequency. Specifically, wavelet transforms compute the inner product of the input with child wavelets which are translated dilates of a mother wavelet. As the mother wavelet is both temporally and spectrally localised, the child wavelets (as dilated translates) are distributed over the time-frequency plane. Thus, the wavelet transform of a signal conveys both temporal and spectral content simultaneously. This property underpins the utility of wavelets.

Discrete wavelet transforms of a length n input restrict the translation and dilation parameters to n discrete values. Typically, the mother wavelet is defined such that the resulting child wavelets form an orthogonal basis. In 1989, Ingrid Daubechies introduced a particularly elegant construction which allows progressively finer scale child wavelets to be derived via a recurrence relation [4]. This formulation restricts the wavelet to a finite width, a property known as compact support. In particular, the pyramidal algorithm [20, 21] implementing Daubechies' transform (used by the above functions) requires only 0(n) time complexity, even faster than the FFT. The Haar wavelet transform is the simplest such wavelet transform.

In this section, we shall examine a simple form of wavelet transform known as the Haar wavelet transform. Remarkably, the definition of this transform is more comprehensible when given as a program, rather than as a mathematical formulation or English description.

The Haar wavelet transform of a length n = 2^pp ≥ 0 ϵZ float list is given by the following function:

> let rec haar_aux (xs : float list) ss ds =
    match xs, ss, ds with
    | [ss] , [] , ds -> ss: :ds
    | [] , ss, ds -> haar_aux ss [] ds
    | xl::x2::xs, SS, ds ->
        haar_aux xs (xl + x2 :: ss) (xl - x2 :: ds)
    | _ -> invalid_arg "haar";;
val haar_aux :
  float list -> float list -> float list -> float list
> let haar xs =
    haar_aux xs [] [];;
val haar : float list -> float list

For example, the Haar wavelet transform converts the following sequence into a more redundant sequence that is more amenable to other data compression techniques:

> haar [1.0; 2.0; 3.0; 4.0; −4.0; −3.0; −2.0; −1.0];;
val it : float list =
  [0.0; 20.0; 4.0; 4.0; −1.0; −1.0; −1.0; −1.0]

The ihaar_aux function implements the transform by tail recursively taking pairs of elements off the input list and prepending the sum and difference of each pair onto two internal lists called ss and ds, respectively. When the input is exhausted, the process is repeated using the list of sums of pairs as the new input. Finally, when the input contains only a single element, the result is obtained by prepending this element (the total sum) onto the list of differences.

The inverse transform may be written:

> let rec ihaar_aux xs ss ds =
    match xs, ss, ds with
    | xs, [] , [] -> xs
    | ss, [] , ds -> ihaar_aux [] ss ds
    | xs, xl::SS, x2::ds ->
        ihaar_aux (0.5 * (hl+h2) :: 0.5 * (xl-x2) :: xs)
          ss ds
    | _ -> invalid_arg "ihaar"
val haar_aux :
  float list -> float list -> float list -> float list
> let ihaar = function
    | [] -> []
    | ss::ds -> ihaar_aux [] [ss] ds;;
val ihaar : float list -> float list

The previous example transform can be reversed to recover the original data from its representation in the wavelet basis:

> ihaar [0.0; 20.0; 4.0; 4.0; −1.0; −1.0; −1.0; −1.0];;
val it : float list =

[1.0; 2.0; 3.0; 4.0; −4.0; −3.0; −2.0; −1.0]

Wavelet transforms are often perceived as a complicated formof analysis but, as these example functions have shown, discrete wavelet transforms can be implemented quickly and easily in F#.

Transcription creates a single-strand RNA molecule from the double-strand DNA. The process replaces the nucleic acid thymine with uracil.

Consider the representation of a DNA sequence as a string containing the characters A, C, G and T:

> let dna = "ACGTTGCAACGTTGCAACGTTGCA";;
val dna : string

The String. map function is the simplest way to replace single characters in a string. For example, the transcription of dna is given by:

> String.map (function 'T' -> 'U' | c -> c) dna;;
val it : string = "ACGUUGCAACGUUGCAACGUUGCA"

Regular expressions are a more powerful alternative. Transcription can be represented as:

> open System.Text.RegularExpressions;;

> let transcribe dna =
       (new Regex("T")) .Replace (dna, "U");;
val transcribe : string -> string

For example:

> transcribe "ACGTTGCAACGTTGCAACGTTGCA";;
val it : string = "ACGUUGCAACGUUGCAACGUUGCA"

Although regular expressions are overkill for this trivial example, they can be very useful for more sophisticated analyses.

This section details a simple program that uses a regular expression to separate words in order to accumulate the distribution of word frequencies in a given file. The implementation includes a general purpose counter that uses a Map to accumulate the frequency of each word.

Regular expressions can be used to identify words in strings, as sequences of alphabet characters. The following regular expression matches any sequence of one or more non-alphabet characters, i.e. word separators:

> open System.Text.RegularExpressions;;

> let not_alpha = new Regex(@"[^a-zA-z]+");;
val not_alpha : Regex

The following function uses the |> operator to compose a sequence of operations that, ultimately, present the words and their frequencies from the given file in descending order by number of occurrences:

> let freqs file =
    let a =
      lines_of_file file
      |> Seq.map not_alpha.Split
      |> Seq.concat
      |> Seq.filter ((<>) "")
      |> Seq.map String.lowercase
      |> Seq.countBy (fun s -> s)
      |> Seq.to_array
    Array.sort (fun (_, n) (_, m) -> -compare n m) a
    a;;
val freqs : string -> (string * int) array

The lines in the given file are first obtained as a seq<string> using the lines_of_file function (defined in section 5.3). The Split member of the not_alpha regular expression is used to split each line into its constituent words. The sequence of sequences of words on each line are concatenated together to obtain the sequence of words in the file. Empty words are filtered out. The remaining words are converted into lowercase. Then the Seq. count By function is used to count the number of occurrences of the key obtained by applying the given function (in this case the identity function) to each element. This gives the frequencies of the words in the file in an unspecified order. All of these operations are performed at once on each element when the laziness is forced into action by the Seq. to_array function.

The resulting array is then sorted into reverse order by the second elements of each of the pairs in the array. This gives the word frequencies with the most frequent words listed first.

For example, this freqs function takes only 2.9s to compute the word frequencies in the King James bible:

> time freqs @"C: iblel3 . txt";;

Took 2 911ms
val it : (string * int) array
  = [|("the", 64034); ("and", 51744); ("of", 34688);
      ("to", 13638); ("that", 12922); ("in", 12693);
      ("he", 10420); ("shall", 9838); ("unto", 8997);
      ("for", 8994); ("i", 8854); ("his", 8473); ...|]

Regular expressions have a wide variety of uses in scientific computing, ranging from simple string dissection to performing sophisticated computations over DNA sequences.

The ability to count the number of elements in a list for which a predicate returns true is sometimes useful. A function to perform this task may be written most simply in terms of filter and length:

> let count f list =
    length (filter f list);;
val count : ('a -> bool) -> 'a list -> int

For example, the following counts the number of elements that are exactly divisible by three (0,3, 6 and 9):

> count (fun x -> x % 3 = 0) [0 . . 9];;
val it : int = 4

However, the subexpression filter f list in this definition of the count function is generating an intermediate list unnecessarily. Consequently, this implementation of the count function can be deforested as described in section 8.4.4.1.

A faster count function might exploit the laziness of the Seq. filter function:

> let count f list =
    Seq.length (Seq.filter f list);;
val count : ('a -> bool) -> seq<'a> -> int

Note that this function is generic over the container type: it can be applied to arrays, sets and so on as well as lists.

Using the more specific List. f old_left function will be faster still because it avoids the overhead of laziness:

> let count f xs =
    fold_left (fun n x -> if f x then n+1 else n) 0 xs;;
val count : ('a -> bool) -> 'a list -> int

The count function can also be written using pattern matching:

> let rec count_aux n f = function
    | [] -> n
    | h::t when f h -> count_aux (n+1) f t
    | _::t -> count_aux n f t;;
val count_aux : int -> ('a -> bool) -> 'a list -> int
> let count list = count_aux 0 list;;
val count : ('a -> bool) -> 'a list -> int

However, this is more verbose than the fold-based implementation.

The ability to prepend elements to lists indefinitely makes them the ideal data structure for many operations where the length of the output cannot be determined easily. Let us examine a function which composes an arbitrary length list as the result.

A function positions that returns the positions of elements satisying a predicate function f may be written in many different ways. For example:

> let positions f list =
    let cons_if (p, ps) h =
      p+1, if f h then p::ps else ps
    let _, ps = fold_left cons_if (0, []) list
    rev ps;;
val positions : ('a -> bool) -> 'a list -> int list

The nested auxiliary function cons_if accumulates the current index p and the list ps of positions satisfying the predicate function f. The positions function folds the cons_if function over the list, starting with an accumulator containing the index zero and the empty list. The final index is ignored and the positions function returns the reverse of the list of positions ps as it has been accumulated in reverse order (the first element to satisfy the predicate was prepended onto the empty list in the initial accumulator).

Like count, the positions function is useful for general purpose list dissection.

Consider a higher-order function f old_to that folds partway through a list, returning the accumulator and the remaining tail. This function may be written:

> let rec fold_to i f accu list =
    match i, list with
    | 0, t -> accu, t
    | i, h::t -> fold_to (i-1) f (f accu h) t
    | _, [] -> accu, [];;
val fold_to :
  int -> ('a -> 'b -> 'a) -> 'a -> 'b list ->
    'a * 'b list

Note that this function returns an empty tail list if the index was out of bounds.

Consider a function to insert an element at a given index in a list. This can be written elegantly in terms of the f old_to function, using the built-in List. rev_append function:

> let insert x i list =
    let rfront, back =
      fold_to i (fun t h -> h::t) [] list
    rev_append rfront (x::back);;
val insert : 'a -> int -> 'a list -> 'a list

For example, inserting 100 into the list [0 ... 9] such that it appears at index 5:

> insert 100 5 [0 . . 9];;
val it : int list = [0; 1; 2; 3; 4; 100; 5; 6; 7; 8; 9]

This function is useful when performance is not a problem but the T(i) complexity of this function renders it unsuitable for repeated insertions at random positions. If this functionality is required to be efficient then either the insertions should be amortized or the list should be replaced with a more suitable data structure.

Consider a function to chop a list into two lists at a given index i, returning the two halves of the input list which we shall refer to as the front and the back lists. As this function terminates in the middle of the list, it is most easily written using pattern matching rather than in terms of the higher-order functions provided in the List module.

The chop function may be written succinct in terms of the f old_to function, accumulating the front list in reverse:

> let chop i list =
    let rfront, back =
      fold_to i (fun t h -> h::t) [] list
    rev rfront, back;;
val chop : int -> 'a list -> 'a list * 'a list

For example, the chop function may be used to split the list [0... 10] into the lists [0... 4] and [5... 10]:

> Chop 5 [0 .. 10];;
val it : int list * int list =
  ([0; 1; 2; 3; 4] , [5; 6; 7; 8; 9; 10])

Writing the chop function in terms of the naturally tail recursive f old_to function encouraged us to write a tail recursive chop function. Factoring out tail recursive higher-order functions like f old_to is a good way to improve clarity in order to keep many functions tail recursive.

This chop function can be used as a basis for more sophisticated list processing functions.

Consider a function called dice that splits a list containing nm elements into n lists of m elements each. This function may be written in tail recursive form by accumulating the intermediate lists in reverse:

> let rec dice_aux accu m list =
    match fold_to m (fun t h -> h::t) [] list with
    | rfront, [] -> rev_map rev (rfront :: accu)
    | rfront, back -> dice_aux (rfront :: accu) m back;;
val dice_aux :
  'a list list -> int -> 'a list -> 'a list list

The dice function may then be written in terms of the dice_aux function by applying the empty list as the accumulator:

> let dice m list =
    dice_aux [] m list;;
val dice : int -> 'a list -> 'a list list

For example, the dice function may be used to dice the list [1... 9] into 3 lists containing 3 elements each:

> dice 3 [1 .. 9];;
val it : int list list =
  [[1; 2; 3]; [4; 5; 6]; [7; 8; 9]]

Note that the action performed by dice can be reversed using the flatten function in the List module:

> flatten [[1; 2; 3]; [4; 5; 6]; [7; 8; 9]];;
val it : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]

The dice function could be used, for example, to convert a stream of numbers into 3D vectors represented by lists containing three elements.

The ability to alter the i^th element of a list using a given function is sometimes useful. As the i^th element of a list may be reached by traversing the previous i elements, this task can be done in

> let apply_at f i list =
    match fold_to i (fun t h -> h::t) [] list with
    | rfront, h::back -> rev_append rfront (f h::back)
    | _, [] -> invalid_arg "apply_at";;
val apply_at : ('a -> 'a) -> int -> 'a list -> 'a list

For example, the following replaces the 6^th element (at the index 5) of the given list with its previous value plus twenty:

> apply_at ((+) 20) 5 [0 .. 9];;
val it : int list = [0; 1; 2; 3; 4; 25; 6; 7; 8; 9]

Provided performance is unimportant, functions like this apply_at function can be very useful when manipulating lists.

Another function found in the Array module but not in the List module is the sub function. This function extracts a subset of consecutive elements of length len starting at index i. A tail-recursive equivalent for lists may be written:

> let sub i len list =
    let (), after_i = fold_to i (fun () _ -> ()) () list
    fst (chop len after_i);;
val sub : int -> int -> 'a list -> 'a list

This implementation takes the back list after chopping at i and then chops this list at len, giving the result as the front list (extracted using the fst function). For example, the 4-element sublist from i = 3 of the list [0... 9] is the list [3... 6]:

> sub 3 4 [0 . . 9];;
val it : int list = [3; 4; 5; 6]

Just as Array. sub can be useful, so this sub function can come in handy in many different circumstances. However, the asymptotic complexity of this list sub function is worse than for arrays because this function must traverse the first i + len elements.

A function similar to the apply_at function (described in section 6.4.7) but which extracts the i^th element of a list, giving a 2-tuple containing the element and a list without that element, can also be useful. As for apply_at, the extract function may be written in terms of the fold_to function:

> let extract i list =
    match fold_to i (fun t h -> h::t) [] list with
    | rfront, h::back -> h, rev_append rfront back
    | _, [] -> invalid_arg "extract";;
val extract : int -> 'a list -> 'a * 'a list

For example, extracting the element with index five from the list [0... 9] gives the element 5 and the list [0... 4,6 ... 9]:

> extract 5 [0 .. 9];;
val it : int * int list =
  (5, [0; 1; 2; 3; 4; 6; 7; 8; 9])

This function has many uses, such as randomizing the order of elements in lists.

This function can be used to randomize the order of the elements in a list, by repeatedly extracting randomly chosen elements to build up a new list:

> let rand = new System.Random;;
val rand : System.Random

> let rec shuffle_aux n accu = function
    | [] -> accu
    | t ->
        let h, t = extract (Random.int n) t
        shuffle_aux (n-1) (h :: accu) t;;
val shuffle_aux : int -> 'a list -> 'a list -> 'a list

This auxiliary function shuf f le_aux counts down the length and accumulates the resulting list, so the shuffle function can be written by applying the precom-puted list length and the empty list:

> let shuffle list =
    shuffle_aux (length list) [] list;;
val shuffle : 'a list -> 'a list

For example, applying the shuffle function to the list {0... 9} gives a permutation containing the elements 0... 9 in a random order:

> randomize [0; 1; 2; 3; 4; 5; 6; 7; 8; 9];;
val it : int list = [6; 9; 8; 5; 1; 0; 3; 2; 7; 4]

This function is useful in many situations. For example, the programs used to measure the performance of various algorithms presented in this book used this shuffle function to evaluate the necessary tests in a random order, to reduce systematic effects of garbage collection. However, the slow random access to lists renders the asymptotic complexity of this function 0(n²). As we shall see in the next section, arrays can provide an 0(n) shuffle.

A function to transpose a rectangular list of lists is easily written in terms of pattern matching:

> let rec transpose = function
    | (_ :: _) :: _ as xss ->
        map hd xss :: transpose (map tl xss)
    | _ -> [];;
val transpose : 'a list list -> 'a list list

This function maps the hd function over the list of lists to obtain the first row of the transpose and prepends this onto the transpose of the remaining rows obtained by mapping the tl function over the list of lists. Unlike the Array2 module, the representation of a matrix as a list of lists does not restrict the number of columns in each row to a constant and, consequently, invalid data can be given to functions that expect rectangular input, such as this transpose function. In this case, improperly-shaped input will cause the hd function to raise an exception when it is applied to an empty list.

For example, the transpose of the matrix:

> transpose [[1; 2; 3]; [4; 5; 6]; [7; 8; 9]];;
val it : int list list =
  [[1; 4; 7]; [2; 5; 8]; [3; 6; 9]]

Many more sophisticated functions also act upon lists of lists, including combina-toric functions.

A function that computes the combinations that arise from composing lists with one element taken from each list in a given list of lists may be written:

> let rec combinations = function
    | [] -> [[]]
    | hs :: tSS ->
        [ for h in hs
            for ts in combinations tss ->
              h : : ts];;
val combinations : #seq<'a> list -> 'a list list

This combinations function prepends each head element onto each tail combination. Note that the use of comprehensions resulted in a generalization: the input to the combinations function is actually a list of sequences rather than a list of lists, i.e. the type #seq<'a> list.

For example, the following lists all combinations taken from the sets (1,2,3), (4,5,6) and (7,8,9):

> combinations [[1; 2; 3]; [4; 5; 6]; [7; 8; 9]];;
val it : int list list =
  [[1; 4; 7]; [1; 4; 8]; [1; 4; 9]; [1; 5; 7];
   [1; 5; 8]; [1; 5; 9]; [1; 6; 7]; [1; 6; 8];
   [1; 6; 9]; [2; 4; 7]; [2; 4; 8]; [2; 4; 9];
   [2; 5; 7]; [2; 5; 8]; [2; 5; 9]; [2; 6; 7];
   [2; 6; 8]; [2; 6; 9]; [3; 4; 7]; [3; 4; 8];
   [3; 4; 9]; [3; 5; 7]; [3; 5; 8]; [3; 5; 9];
   [3; 6; 7]; [3; 6; 8]; [3; 6; 9]]

Combinations are one of the two most important combinatoric functions. The other is permutations.

The ability to compute all permutations of a list is sometimes useful. Permutations may be computed using a simple recurrence relation, by inserting the head of a list into all positions of the permutations of the tail of the list. Thus, a function to permute a list is most easily written in terms of a function which inserts the given element into the given n-element list at all n + 1 possible positions. This function is called distribute:

> let rec distribute e = function
    | [] -> [[e]]
    | x :: xs' as xs ->
        (e :: xs) : :
          [ for xs in distribute e xs' ->
              X :: XS];;
val distribute : 'a -> 'a list -> 'a list list

This distribute function operates by prepending an answer, the element e prepended onto the given list 1, onto the head of the given list prepended onto each of the distributions of the element e over the tail t of the given list.

For example, the following inserts the element 3 at each of the three possible positions in the list [1; 2]:

> distribute 3 [1; 2];;
val it : int list list =
  [[3; 1; 2]; [1; 3; 2]; [1; 2; 3]]

Permutations may be computed using this distribute function.

A function to permute a given list may be written in terms of the distribute function:

> let rec permute = function
    | e :: t -> flatten (map (distribute e) (permute t))
    | [] -> [[]];;
val permute : 'a list -> 'a list list

This permute function then operates by distributing the head of the given list over the permutations of the tail.

For example, there are 3! = 6 permutations of three values:

> permute [1; 2; 3];;
val it : int list list =
  [[1; 2; 3]; [2; 1; 3]; [2; 3; 1]; [1; 3; 2];
   [3; 1; 2]; [3; 2; 1]]

The permute function has many uses, including the combinatorial optimization of small problems. However, the permute function has 0(n × n!) complexity. For n = 10, this function takes over 16s. Consequently, this function is not suitable for large combinatorial problems and, in fact, such problems can be very difficult or practically impossible to solve. Combinatorial optimization will be discussed in one of the complete examples in chapter 12.

The power set of a set A is the set of all subsets of A. This may be computed using a simple function:

> let rec powerset = function
    | [] -> [[]]
    | h::t ->
        [ for t in powerset t
            for t in [t; h::t] ->
              t ];;
val powerset : 'a list -> 'a list list

For example, the subsets of the set {1,2,3} are:

> powerset [1; 2; 3];;
val it : int list list =
  [[]; [1]; [2]; [1; 2]; [3]; [1; 3]; [2; 3]; [1; 2; 3]]

This is an elegant use of the list comprehension syntax offered by F#.

The ability to rotate the elements of an array can sometimes be of use. This can be achieved by creating a new array, the elements of which are given by looking up the elements with rotated indices in the given array:

> let rotate i a =
    let n = Array.length a
    [|for k in O .. n- 1 ->
        let k = (k + i) % n
        a.[if k < 0 then n + k else k]|];;
val rotate : int -> 'a array -> 'a array

This function creates an array with the elements of a rotated left by i. For example, rotating two places to the left:

> rotate 2 [| 0; 1; 2; 3; 4; 5; 6; 7; 8; 9 |];;
val it : int array = [| 2; 3; 4; 5; 6; 7; 8; 9; 0; 1|]

Rotating right can be achieved by specifying a negative value for i. For example, rotating right three places:

> rotate (-3) [|0; 1; 2; 3; 4; 5; 6; 7; 8; 9|];;
val it : int array = [|7; 8; 9; 0; 1; 2; 3; 4; 5; 6|]

Considering this function alone, the performance can be improved significantly by rotating the array elements in-place, by swapping pairs of elements. This can be regarded as a deforesting optimization (see section 8.4.4.1). However, the more elegant approach presented here can be refactored in the case of many subsequent rotations (and other, similar operations) such that no intermediate arrays need be created.

A function to swap the i^th and j^th elements of an array may be written:

> let swap (a : 'a array) i j =
    let t = a. [i]
    a. [i] <- a. [j]
    a. [j] <- t;;
val swap : 'a array -> int -> int -> unit

Note that this function swaps the elements in-place and, consequently, returns the value () of type unit.

This function can be used as the basis of many algorithms that permute the contents of an array, such as sorting algorithms.

A useful function in the context of array manipulation takes integers j ϵ {0... n — 1} and j ϵ {0... n — 2} and returns the j^th index that is not i:

> let except i j =
    if j < i then j else j + 1;;
val except : int -> int -> int

The except function can be used to shuffle array elements.

The order of the elements in an array can be randomised in-place by swapping each element with with a randomly-chosen element. A function to perform this operation as a side effect may be written in terms of the swap function and the Random module presented in section 9.4:

> let shuffle a =
    let n = Array.length a
    for i = 0 to n - 1 do
      swap a i (Random.int n);;
val shuffle : 'a array -> unit

Note that we are careful to choose any element at random such that an element may be swapped with itself. Although it is tempting to swap with other elements, this would lead to determinism, e.g. when shuffling a two-element array.

For example:

> let a = [|1 .. 9|];;
val a : int array

> shuffle a;;
val it : unit = ()

> a;;
   val it : int array = [|5; 4; 7; 3; 9; 1; 2; 6; 8|]

This function can be used in a wide variety of random algorithms and is particularly useful when performance is important.

Functions to perform operations such as map over tuples of a particular arity are also useful. For example, the following implements some useful functions over 2-tuples:

> let iter_2 f (a, b) =
    f a
    f b;;
val iter_2 : ('a -> unit) -> 'a * 'a -> unit

> let map_2 f (a, b) =
    f a, f b;;
val map_2 : ('a->'b) ->'a*'a->'b*'b

> let fold_left_2 f accu (a, b) =
    f (f accu a) b;;
val fold_left_2 :
  ('a -> 'b -> 'a) -> 'a -> 'b * 'b -> 'a

Such functions can be used to reduce code size in many cases.

The vector dot product is a specialized form of inner product. The inner and outer products may, therefore, be productively written as higher-order functions which can then be used as a basis for more specialized products, such as the dot product.

The inner product is most easily written in terms of a f old_lef t2 function. In the interests of generality, we shall begin by defining a fold_left2 function for the Seq type:

> let fold_left2 f accu xs ys =
    Seq.zip xs ys
    |> Seq.fold (fun accu (x, y) -> f accu x y) accu;;
val fold_left2 :
  ('a -> 'b -> 'c -> 'a) -> 'a ->
    #seq<'b> -> #seq<'c> -> 'a

An inner product that is generalized over types, functions and even container type may then be written in terms of this f old_lef t2 function:

> let inner base f xs ys g =
    fold_left2 (fun accu x y -> g accu (f x y))
      base xs ys;;
val inner :
  'a -> ('b -> 'c -> 'd) -> #seq<'b> -> #seq<'c> ->
     ('a -> 'd -> 'a) -> 'a

For example, the same inner function may be used to compute the dot product of a pair of int lists:

> inner 0 (*) [1; 2; 3] [2; 3; 4] (+);;

val it : int = 20

float lists:

> inner 0.0 (*) [1.0; 2.0; 3.0] [2.0; 3.0; 4.0]
    ( + );;
val it : float =20.0

and even float arrays:

> inner 0.0 (*) [|l.0; 2.0; 3.0|] [|2.0; 3.0; 4.0|]
    ( + );;
val it : float =20.0

Using the Seq type, even the outer product can be generalized over data structure:

> let outer f xs ys =
    seq { for x in xs ->
            seq { for y in ys ->
                    f X y } };;
val outer :
  ('a -> 'b -> 'c) -> #seq<'a> -> #seq<'b> ->
    seq<seq<'c> >

The outer product of two vectors is a matrix:

The generalized outer function can be used to compute this outer product on many container types including float lists:

> outer (*) [1.0; 2.0; 3.0] [2.0; 3.0; 4.0];;
   val it : seq<seq<float>>
     = seq [seq [2.0; 4.0; 6.0]; seq [3.0; 6.0; 9.0];
            seq [4.0; 8.0; 12.0]]

Aggressive factoring of higher-order functions can be very useful in the context of numerical computation.