This chapter presents a wide variety of code snippets implementing useful functions in different ways. These examples should serve to ossify the readers understanding of the F# language in order to prepare them for the complete example programs in chapter 12. Whilst describing these functions we endeavour to explain the relationships between the styles chosen and the information disseminated in the previous chapters of this book.
Many useful mathematical and scientific constructs can be encoded very elegantly by exploiting the features of functional programming. In the introduction, we saw a remarkably simple and yet powerful numerical derivative function. In this section, we shall examine more functions that will be useful to scientists using F#.
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 = x3 — 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)
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 35th 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(2n). As the function is slow to execute, the results can be productively cached for reuse.
Fortunately, even the generic concept of caching the results of function calls can befactored out and expressed as a higher-order function. This technique is known as memoization. A higher-order function to memoize a given function may be written:
> 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
This memoize
combinator can be applied to the fib
function to produce a new function that has the same type as the fib function but transparently caches previously computed results:
> let mfib = memoize fib;; val mfib: (int -> int)
This function is slow when invoked for the first time on any given input but is fast the next time it is invoked with the same input:
> time mfib 35;; Took 24 0ms val it : int = 9227465 > time mfib 3 5;; Took 0ms val it : int = 9227465
Memoization can clearly be useful in a variety of circumstances. However, this implementation of the memoize
combinator can be generalized even further.
The previous example cached the return values of the original fib
function to improve performance when a calculation was repeated. However, when computing the 35th Fibonacci number, the function still recomputes the 33rd and 34th Fibonacci numbers. Caching would be more effective if it could memoize the results of the recursive calls made inside the fib
function as well as the calls made from the outside.
This can be done by first unravelling the fib
function such that it is no longer recursive, a technique known as "untying the recursive knot". To do this, the function is written as a higher-order function and is passed the function that it will recurse into. This is most simply written by removing the rec
from the definition and adding an initial argument with the same name as the function itself:
> let fib fib = function | 0 [1 as n -> n | n -> fib(n - 1) + fib(n - 2);; val fib : (int -> int) -> int -> int
By passing this fib
function a memoized version of itself as its first argument, the recursive calls inside the fib
function can also be memoized. Doing this required a slightly modified version of the memoize
combinator as well:
> 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
The nested f
' function is the memoized version of the f
function. Note that the f
' function is careful to pass itself as the first argument to f
, so that calls in f
that were recursive become calls to the memoized version f
' instead.
Applying memoize_rec
to the untied fib
function creates a recursively memoized version of the fib
function:
> let mfib = memoize_rec fib;; val mfib : (int -> int)
This function is not only quick to recompute Fibonacci numbers but is now asymptotically quicker to compute all Fibonacci numbers! Specifically, computing the nth number only requires the previous n numbers [0... n — 1] to be computed, i.e. the asymptotic complexity is now only O (n). Consequently, this function can be used to compute larger Fibonacci numbers very quickly.
For example, computing the 45th Fibonacci number takes only 2ms:
> time mfib 45;; Took 2ms val it : int = 1134903170
The ability to represent memoization as a combinator makes it much easier to use in functional languages. However, the F# programming language actually provides sophisticated support for recursive definitions and, in fact, can represent this recursive memoization using only the original memoize
function:
> let rec fib = memoize (function | 0 | 1 as n -> n | n -> fib(n - 1) + fib(n - 2));; val fib : (int -> int) -> int -> int
The compiler will emit a warning explaining that the soundness of this function definition cannot be checked at compile time and run-time checks will be inserted automatically but we can prove to ourselves that the definition is correct. This approach elegantly combines the brevity and clarity of the original implementation with the efficiency of a completely memoized function, including recursive calls:
> time mfib 45;; Took 2ms val it : int = 1134903170
However, the growth of the hash table used to memoize previously-computed results in this implementation can grow unbounded. This can sometimes be an effective memory leak when previous results are no longer needed and should be "forgotten". Consequently, it may be useful to replace the memoize combinator with an implementation that uses a more sophisticated data structure to remember only a certain number of the most commonly used answers, or even to measure the memory required by memoization and limit that.
Divide and conquer describes the strategy of algorithms that break large problems into separate smaller problems. This is a vitally important topic in algorithm design and underpins many high-performance algorithms that make practical problems tractable. A closely related subject that has received growing attention in recent years is called "dynamic programming". This refers to strategies similar to divide and conquer that manage to break large problems into overlapping smaller problems. Optimal asymptotic efficiency is then most easily obtained by memoizing the overlaps and reusing them rather than recomputing them.
The Fibonacci function described in the previous section is perhaps the simplest example of dynamic programming. At each step, the classic description of the Fibonacci function breaks the large computation of fib n
into two smaller computations of fib(n - 1)
and fib(n - 2)
but the smaller computations overlap because fib(n - 1)
can be expressed in terms of fib (n - 2
and fib(n - 3)
. Applying the memoize
combinator, as we did, allows the overlapping solutions to be reused and greatly improves performance as a consequence.
Dynamic programming will be revisited in section 12.3.
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.
Many useful functions simply perform computations on the built-in number types. In this section, we shall examine progressively more sophisticated numerical computations.
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.
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 };;
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)6 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) = x3 — 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 xi . 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) = x4 + y2 — x3y — 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 = 2pp ≥ 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#.
In recent times, the dominance of numerical methods in scientific computing has been significantly displaced by other forms of analysis. Particularly in the context of DNA and protein sequences, scientists are analysing a wider range of data structures than before. Strings are commonly used to represent such sequences and, consequently, are commonly using in bioinformatics as well as more directly-related sciences such as computational linguistics.
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.
In this section, we shall examine a variety of functions that act upon lists. Consequently, we shall assume that the namespace of the List
module hasbeen opened:
> open List;;
These functions are often polymorphic and typically make use of either recursion and pattern matching or higher-order functions. These concepts can all be very useful but are rarely seen in current scientific programs.
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 ith element of a list using a given function is sometimes useful. As the ith 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 6th 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 ith 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(n2). 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#.
Although arrays are currently overused in scientific computing, they are well suited to certain situations. Specifically, situations where memory is tight or where random access is a performance bottleneck.
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 ith and jth 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 jth 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.
As we have already hinted, aggressively factoring higher-order functions can greatly reduce code size and sometimes even lead to a better understanding of the problem. In this section, we shall consider various different forms of higher-order functions which can be productively used to aid brevity and, therefore, clarity.
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.