Introducing Functional Programming

F# programming is effective and productive primarily because it is built on the tried and tested foundational constructs of functional programming, in particular the programming paradigm of the ML and Caml family of languages. In this chapter we look at some of the core building blocks of F# programming, particularly with regard to simple data types and function values. Imperative programming, type definitions, generics and object-oriented programming are covered in Chapters 4 to 7.

The ABC of F# Arithmetic

We first take a look at the most common base types of data manipulated in F# code. We begin with the basics of F# arithmetic.

Basic Arithmetic Literals

The table below shows the most common basic types used in F# code and their corresponding literal forms. Many additional types are defined in the .NET libraries.

Arithmetic types and literals

bool true/false values true, false System.Boolean

byte 8-bit unsigned integers 0uy, 19uy, 0xFFuy System.Byte

sbyte 8-bit signed integers 0y, 19y, 0xFFy System.SByte

int16 16-bit signed integers 0s, 19s, 0x0800s System.Int16

uint16 16-bit unsigned integers 0us, 19us, 0x0800us System.UInt16

int, int32 32-bit signed integers , 19l[DS1] , 0x0800, 0b0001 System.Int32

uint32 32-bit unsigned integers 0ul, 19ul, 0x0800ul[DS2]  System.UInt32

int64 64-bit signed integers 0L, 19L, 0x0800L System.Int64

uint64 64-bit unsigned integers 0UL, 19UL, 0x0800UL System.UInt64

single, float32 32-bit IEEE floating-point 0.0f, 19.7f, 1.3e4f System.Single

double, float 64-bit IEEE floating-point , , 1.3e4 System.Double

decimal High-precision decimal values 0M, 19M, 19.03M[DS3]  System.Decimal

bigint Arbitrarily large integers 0I, 19I Math.BigInt

bignum Arbitrary precision rationals 0N, 19N Math.BigNum

Arithmetic Operators

A number of operators are by default overloaded to work over multiple types, including user-defined types. Operators may also be redefined to only work over specific types, by replacing the definition that gives the operator the status of an overloaded operator. See Chapter 6 - Type Definitions, Classes and Objects for a description of how to define new instances of overloads for new type definitions. The most commonly used default arithmetic operators are shown below.

Arithmetic operators and examples

Unchecked Addition

Unchecked Subtraction

Unchecked Multiplication

Division 5.0 / 2.0

Modulus 5.4 % 2.0

Unary Negation -(5.4+2.4)

In F# addition, subtraction and multiplication over integers are unchecked, that is if overflow or underflow occurs beyond the representable range then wraparound occurs. For example, is the largest representable 32-bit integer of the int type:

Checked versions of these that raise System.Overflow exceptions can be accessed by opening the Microsoft.FSharp.Operators.Checked [DS4] module, and if detecting overflow is a priority then the use of the decimal, bigint or bignum types is recommended. Division by zero raises a System.DivideByZeroException, except in the case of floating point numbers where it returns a NaN value.

Operator overloading interacts with type inference - if any particular use of an overloaded operator is not otherwise constrained to work on any particular type then F# will assume it works on 32-bit integers. To constrain a particular use of an operator to a particular numeric type you must give a type annotation that has the effect of telling the compiler the left-hand type of the two arguments to the binary operator. For example, in the absence of additional type information the following function is assumed to work over integers:

A single type annotation on a is sufficient to indicate that a*a is an operation on float values, and thus returns a float value, and thus that a*a+b is also an operation on float values.

However asymmetric type constraints of this form are not always considered good style, and in some situations involving overloaded operators it will be simplest to give the full type annotations for the arguments and return type of a value:

Bitwise Operations

The integer types support bitwise manipulations on their underlying representations. The most commonly used default bitwise manipulation operators are shown in the table below.

Bitwise arithmetic operators and examples

&&& Bitwise And 0x65 &&& 0x0F 0x05

Bitwise Or 0x65 ||| 0x18 0x7D

Bitwise Exclusive Or 0x65 ^^^ 0x0F 0x6A

Bitwise Negation ~~~0x65 0xFFFFFF9a

<<< Left shift 0x01 <<< 3 0x08

>>> Right shift (arithmetic if signed) 0x65 >>> 3 0x0C

The following sample shows the use of these operators to encode 32-bit integers into 1, 2 or 5 bytes, represented by returning a list of integers. Input integers in the range 0 to 127 return a list of length one.

let encode (n: uint32) =

if (n >= 0 && n <= 0x7F) then [ n ]

elif (n >= 0x80 && n <= 0x3FFF) then [ (0x80 ||| (n >>> 8)) &&& 0xFF;

(n &&& 0xFF) ]

else [ 0xC0; ((n >>> 24) &&& 0xFF);

((n >>> 16) &&& 0xFF);

((n >>> 8) &&& 0xFF);

(n &&& 0xFF) ]

Here is an example of the function in action:

val it : int32 list = [32]

> encode 320;;

val it : int32 list = [129; 64]

> encode 32000;;

Arithmetic Conversions

Numeric types are not implicitly converted - all conversions between different numeric types must be made explicitly. Some conversion operators are shown in the table below. Often there are multiple equivalent ways of achieving the same conversion.

Basic arithmetic conversions and examples

Float.of_int int -> float Float.of_int 0x65 Int32.to_float, float

Int32.of_float float -> int Int32.of_float 128.4 Float.to_int, truncate

Byte.of_int int -> byte Byte.of_int 0x65 Int32.to_byte

Int32.of_byte byte -> int Int32.of_byte 0x65y Byte.to_int

These conversions are all unchecked, in the sense that they will not raise exceptions. An alternative is to use the .NET static methods contained in the type System.Convert, e.g. System.Convert.ToDouble( ). As with many .NET constructs, uses of System.Convert methods may require type annotations to resolve overloading, discussed in detail in Chapter 5. In addition, these operators are checked and will raise an exception if the source number can't be represented within the numeric range of the target type.

Arithmetic Comparisons

When used with numeric data the binary comparison operators , <>, <, <=, >, >=, min and max perform comparisons according to the natural ordering for each particular numeric type. These operators can also be used on structured data types, e.g. to compare lists of integers, and their behaviour can be customized for new types that you define. This topic is discussed in Chapter 8.

When used on floating point values these operators implement the IEEE semantics for NaN values, as with nearly all other modern high-level languages. For example, (NaN = NaN) returns false, as do (NaN <= NaN) and (NaN < NaN). For more details consult the F# language specification.

Simple Strings

The F# type string is an abbreviation for the.NET Framework type System.String and represents a sequence of Unicode UTF-16 characters. More details on Unicode can be found in the many excellent guides on the Web. In this section we briefly introduce strings and the most useful sets of functions for formatting them.

String Literals and Primitives

String literals are written using the forms shown in the table below.

String and character literals

'Humpty Dumpty' string string

'c:Program Files' string string

@'c:Program Files' verbatim string string

'xyZy3d2'B literal byte string byte[]

'c' character char

As shown in the table a literal form is also available for interpreting sequences of characters as arrays of bytes.

The escape codes that may be used in strings and characters are shown in the table below.

Escape characters in non-verbatim strings

n New Line 10 'n'

r Carriage Return 13 'r'

t TAB 9 't'

b Backspace 8

NNN Trigraph NNN (space)

uNNNN Unicode character NNNN 'u00a9' ()

UNNNNNNNN Long unicode character NNNN NNNN 'U00002260' (≠)

Verbatim strings are particularly useful for file and path names that contain the escape character " ". Multi-line string literals may also be used, e.g.

and all the kings men";;

Strings are immutable, i.e. the contents of a string value may not be modified once created. The operator is used to access the elements of a string, and the property .Length retrieves its length:

val s : string = 'Couldn't put Humpty'

> s.Length;;

val it : int = 19

> s.[13];;

Building Strings

The simplest way to build strings is via concatenation, using the + operator:

Strings can also be built using objects of the .NET type System.Text.StringBuilder. These objects are mutable buffers that can be used to accumulate and modify text. An example is shown below.

val buf : System.Text.StringBuilder

> buf.Append('Humpty Dumpty');;

> buf.Append(' sat on the wall');;

> let s = buf.ToString();;

Getting Started with Pattern Matching

One of the most important tools in F# programming is "pattern matching", a very general construct that combines decomposition and control. In the previous sections we had a taste for how pattern matching can be used with tuple values. However, pattern matching can also be used in many other situations. We'll see many other examples of pattern matching in this book, but we'll begin with some simple pattern matching over strings and integers. Pattern matches on explicit values are introduced using the match with construct:

let urlFilter url agent =

match (url,agent) with

| 'https://www.control.org', 99 -> true

| 'https://www.kaos.org' , _ -> false

| _, 86 -> true

| _ -> false

The inferred type of the function is:

The expression after match is evaluated to a tuple value, and the "rules" of the match are used to choose a result expression. Each rule of the match is introduced with a , though the first is optional. The first rule of the match will succeed if url and agent are 'https://www.control.org' and respectively. The last three rules all make use of "wildcard" patterns represented by the underscore character - these match all inputs.

The overall conditions under which urlFilter returns true can be read off simply by reading through the pattern match, e.g. agent 99 may access 'https://www.control.org', no one may access 'https://www.kaos.org', and, excluding the latter agent 86 may access anything.

Matching on Structured Values

Pattern matching can also decompose values. Here is an example where we match nested tuple values:

let highLow a b =

match (a,b) with

| ('lo', lo), ('hi', hi) -> (lo,hi)

| ('hi', hi), ('lo', lo) -> (lo,hi)

| _ -> failwith 'expected a both a high and low value';;

The match examines two pairs and looks at the strings in the first element of each, returning the associated values.

The first rule decomposes the list according to the case where the first parts of the pairs are the strings 'lo' and 'hi' respectively. It then returns a pair made from the respective second parts of the tuples. The second rule is the mirror of this in case the values appeared in reverse order.

The final cases of both of the above examples use wildcard patterns to cover remaining cases. This makes the patterns "exhaustive". Frequently no wildcard is needed to ensure this, as for many input types F# is able to determine if the given set of rules is sufficient to cover all possibilities for the given shape of data. However, if a match is not exhaustive a warning is given, e.g.

match url,agent with

| 'https://www.control.org', 86 -> true

| 'https://www.kaos.org', _ -> false;;

match url,agent with

In these cases it may be necessary to add an extra exception-throwing clause to indicate to the F# compiler that the given inputs are not expected, e.g.

match url,agent with

| 'https://www.control.org', 86 -> true

| 'https://www.kaos.org', _ -> false;;

| _ -> failwith 'unexpected input'

Non-exhaustive matches are automatically augmented by a default case is added where a MatchFailureException is thrown (exceptions are discussed in Section EXN).

F# is also frequently able to determine if pattern matching rules are redundant, i.e.if a rule may never be selected because previous rules subsume all such cases. In this case a warning is given. For example:

match url,agent with

| 'https://www.control.org', _ -> true

| 'https://www.control.org', 86 -> true

| _ -> false;;

| 'https://www.control.org', 86 -> true

Guarding Rules and Combining Patterns

Individual pattern clauses can be guarded by a condition that is executed if the pattern itself succeeds. Here is a very simple use of this mechanism to records the three clauses for computing the sign of an integer:

let sign x =

match x with

| _ when x < 0 -> -1

| _ when x > 0 -> 1

| _ -> 0

Two patterns may be combined to represent two possible paths for matching:

let getValue a =

match a with

| (('lo' | 'low') ,v) -> v

| ('hi',v) | ('high',v) -> v

| _ -> failwith 'expected a both a high and low value';;

Here the pattern ('lo' | 'low') matches either string. The pattern ('hi',v) | ('high',v) plays essentially the same role by matching pairs values where the left of the pair is 'hi' or 'high' and binding the value v on either side of the pattern.

Working with Lists and Options

Some of the foundational data structures of F# coding are tuples, lists and options. In this section we discuss these and some related topics by example.

Using F# Lists

F# lists are a common data structures used in foundational F# programming. We have seen some examples of concrete lists when using the String.split function in Code Sample CODE-WORD-COUNT. The following table shows the primitive constructs for building lists:

List related language constructs

The empty list

A list value

'Cons' an element with an existing list

Some basic list values are shown below:

let oddPrimes = [3;5;7;11]

let morePrimes = [13;17]

let primes = 2 :: (oddPrimes @ morePrimes)

F# Interactive shows the value of primes as follows:

It is important to note that lists are immutable: the "cons" and "append" operations do not modify the original lists, instead they create new lists. This can be seen in the following interactive session:

val people : string list = [ 'Adam'; 'Dominic'; 'James' ];;

> 'Chris' :: people;;

val it : string list = [ 'Chris'; 'Adam'; 'Dominic'; 'James' ];;

> people;;

Note that people has not been changed by the second line - lists and tuples are unchangeable, immutable values. Immutable values bring many advantages. At first it might seem strange to define values that you can't change. However, knowing that these don't change means that you rarely need to think about the "object identity" of these values - you can pass them to routines and know they won't be mutated, and you can pass them between multiple threads without worrying about unsafe concurrent access to the values.

As with tuples, you can decompose lists from the head downwards using pattern matching. Here is an example:

let printFirst primes =

match primes with

| h :: t -> printf 'The first prime in the list is %dn' h

| [] -> printf 'No primes found in the listn'

This code examines the head of the primes list, considering the case where primes is an empty list. Note that the and symbols can be used both to build up lists in expressions and to decompose them in pattern matching. This applies to many data structures in F# programming.

The F# library also includes a module List that contains some useful values related to programming with lists. We'll be seeing many of these functions in the next section and throughout this book. Some of these are shown in Fig. 3.1.

F# lists are represented in memory as linked lists, and each F# list value is either a 'cons' cell containing a value plus a pointer to the next chain in the list, or else it is a null pointer. When you create a new list using the tail of the new list will point to the old list, which ensures that the inner memory associated with lists is often reused as a part of multiple list values.

F# lists are not appropriate for all circumstances: e.g. very large data structures should probably be represented using arrays or other data structures, or even managed by an external tool such as a relational database. A number of list-like data structures are discussed in the panel below.

Figure 3.1: Some Sample Functions in the List Module

module List

val hd    : 'a list -> 'a

val tl    : 'a list -> 'a list

val map    : ('a -> 'b ) -> 'a list -> 'b list

val filter : ('a -> bool) -> 'a list -> 'a list

val iter    : ('a -> unit) -> 'a list -> unit

val to_array : 'a list -> 'a[]

val of_array : 'a[] -> 'a list

F# lists are simple, but are just one of a number of important data structures that are available with F#. Data structures are generally divided between mutable and immutable, a distinction covered in more detail in Chapter 4. Here are some of the immutable data structures commonly used with F#:

* 'a list, Immutable linked lists. Cheap to add and access data from one end. Inefficient for random access lookup. Full name Microsoft.FSharp.Collections.List <'a>.

* Microsoft.FSharp.Collections.Set<'a>, Immutable sets based on balanced trees. Cheap to add, access and union, with log(N) access time. Internal nodes can be shared between different sets.

* Microsoft.FSharp.Collections.Map<'key,'value >, Immutable maps based on balanced trees. Cheap to add and access, with log(N) access time. Internal nodes can be shared between different maps.

Chapter 4 includes several examples showing how to use mutable data structures. Some of the important mutable data structures are:

* 'a[]. Mutable, fixed size 1-dimensional arrays, intrinsic to .NET. Also written 'a array. Constant-time access

* 'a[,]. Mutable, fixed size 2-dimensional arrays, intrinsic to .NET. Constant-time access

* System.Collections.Generic.Dictionary<'key,'value>. Mutable hash tables. Near constant-time access. See Chapter 4 for more details.

* Microsoft.FSharp.Collections.HashSet<'a>. Mutable hash sets. Near constant-time access.

* ResizeArray<'a>. Mutable, auto-resizing arrays. Constant-time access. Full name System.Collections.Generic.List<'a>, but generally referred to by the type abbreviation ResizeArray<_> in F#. See Chapter 4 for examples.

There is one name clash between the commonly used mutable and immutable collections: the types Microsoft.FSharp.Collections.List<'a> and System.Collections.Generic.List<'a> both have short name "List<'a>" but are actually immutable linked lists and expanding arrays respectively. These types are very different and live in different namespaces. In general F# code uses lower-case abbreviation 'a list for the former and ResizeArray<'a> for the latter. Operations for these are in the modules Microsoft.FSharp.Collections.List and Microsoft.FSharp.Collections.ResizeArray respectively, accessed via simple paths such as List.map, List.iter, ResizeArray.map and ResizeArray.iter.

Using F# Option Values

Like lists and tuples, option values are simple constructs frequently used as a workhorse in F# coding. An option is simply either a value, Some(v), or the absence of a value, None. For example, options are extremely useful for returning the value of a search where you might or might not have a result. Here's a data structure that uses options to represent the (optional) parents of some well-known characters:

('Eve' , None);

('Cain', Some('Adam','Eve'));

('Abel', Some('Adam','Eve')) ];;

Pattern matching is very frequently used with option values:

match parents with

| Some(dad,mum) -> printf '%s has father is %s, mother %sn" nm dad mum

| None -> printf '%s has no parents!n' nm;;

val showParents : (string * (string * string) option) -> unit

> showParents ('Adam',None);;

The F# library also includes a module Option that contains some useful values related to programming with options. Some of these are shown in Fig. 3.2. While it is easy to code these by hand using pattern matching it can also be useful to learn and rely on the standard definitions.

Figure 3.2: Some Sample Functions in the Option Module

module Option

val get    : 'a option -> 'a

val is_some : 'a option -> bool

val map    : ('a -> 'b ) -> 'a option -> 'b option

val iter    : ('a -> unit) -> 'a option -> unit

Using Option Values for Control

Option values can be used for both data and control, and are often used to represent the success or failure of a computation. This can be useful when catching an exception, e.g.

let res =

try

Some(http('https://www.nature.com'))

with _ ->

None

Exceptions are described in more detail in Chapter 4 - what matters here is that if an unexpected problem occurs during the HTTP request then the exception will be caught and the result of the expression will be the value None. Successful web-page requests will return a Some value. Option values may then be discriminated and decomposed using pattern matching, as shown below:

let fetch url =

try Some(http(url))

with _ -> None

Here is an example where we use the function:

| Some(res) -> printf 'text = %sn' text

| None -> printf '**** no web page foundn';;

As it happens fetch is a somewhat dangerous function, as it catches all exceptions. Catching particular exceptions related to web requests has been discussed in Chapter 2.

Conditionals, && and ||

A basic control construct in F# programming is if/then/elif/else. Here's an example:

let round x =

if x >= 100 then 100

elif x < 0 then 0

else x

Conditionals are really shorthand for pattern matching, e.g. the above could have been written:

let round x =

match () with

| _ when x >= 100 -> 100

| _ when x < 0 -> 0

| _ -> x

Conditionals are always guarded by a boolean-valued expression. These can be built using the && and (the "and" and "or" operators) as well any library functions that return boolean values.

let round2 (x,y) =

if x >= 100 || y >= 100 then 100,100

elif x < 0 || y < 0 then 0,0

else x,y

&& and are special values that only evaluate the second argument if needed.

Defining Recursive Functions

One of the fundamental building blocks of computation in F# is recursion. The following code shows a simple well-known recursive function:

val factorial : int -> int

> factorial 5;;

This example shows that a recursive function is simply one that can call itself as part of its own definition. Recursive functions are introduced by let rec. Functions are not recursive by default, since it is wise to minimize the size of a recursive collection of functions to aid with maintainability. It may help to visualize the execution of factorial 5 in the following way (though note that in reality F# executes the function using efficient native code):

= 5 * factorial 4

= 5 * (4 * factorial 3)

= 5 * (4 * (3 * factorial 2))

= 5 * (4 * (3 * (2 * factorial 1 )))

= 5 * (4 * (3 * (2 * 1)))

= 5 * (4 * (3 * 2))

= 5 * (4 * 6)

= 5 * 24

As with all calls, the execution of the currently executing instance of the function is effectively suspended while the recursive call is made.

Many of the operators we have so far encountered can be coded as recursive functions. For example, the following is one possible implementation of List.map:

let rec map f l =

match l with

| [] -> []

| h :: t -> f h :: map f t

Likewise, many functions such as List.length are implemented using recursive functions.

Recursion is sometimes used as a means of programming particular patterns of control. This is usually used in contexts where functions have deliberate side effects. For example, the following code repeatedly fetches the HTML for a particular web page, printing each time it is fetched:

let rec repeatFetch url n =

if n > 0 then

let html = http url

printf 'fetched <<< %s >>> on iteration %dn' html n

repeatFetch (n-1)

Recursion is powerful, but not always the ideal way to encode either data manipulations or control constructs, at least if other techniques are readily available. For example, the above program could be implemented using a for loop, as explained in the next section, which would be clearer. A typical error with recursion is to forget to decrement a variable at the recursive call. For example, the author incorrectly entered the following non-terminating function when writing this chapter:

let rec badFactorial n = if n <= 0 then 1 else n * badFactorial n

Multiple inter-related recursive functions can be defined simultaneously by separating the definitions with and. For example:

let rec even n = (n = 0) or not(odd(n-1))

and odd n = not(even(n-1))

Care must sometimes be taken with recursive functions to ensure that they are "tail-recursive", or else the computation stack of your program may be exhausted. Indeed, the implementation of map above is not tail-recursive. This is discussed further in "Managing Resources", Chapter 8.

Introducing Function Values

In this section we take a look at the next foundational building block of F# programming: function values. We begin by a simple and well known example: using function values to transform one list into another.

One of the primary uses of F# lists is as a general-purpose concrete data structure for storing ordered sets of inputs and ordered results. Input sets are often transformed to output sets using "aggregate" operations that transform, select, filter and categorize elements of the list according to a range of criteria. These aggregate operations provide an excellent introduction to the use of function values. Let's take a closer look at this in the following code sample, which continues on from the definition of http in code sample HTTP-CODE.

'https://www.google.com' ];;

val sites : string list = ['https://www.live.com'; 'https://www.google.com' ]

> let fetch url = (url, http url);;

val fetch : string -> string * string

> let resultsOfFetch = List.map fetch sites;;

val resultsOfFetch: (string * string) list

= [ ('https://www.live.com', '<html></html>');

('https://www.google.com', '<html></html>'); ]

The first definition is a literal list of URLs. The second line calls the aggregate operation List.map. This accepts the "function value" fetch as the first argument and a list as the second argument, applying fetch to each element of the list and collecting up the results in a new list.

Types are one useful way to help learn what a function does. Here's the type of List.map:

This says that List.map accepts a function value as the first argument and a list as the second argument, and returns a list as the result. The function argument can have any type 'a -> 'b, and the list must have a corresponding type 'b. The symbols 'a and 'b are called "type parameters" or "type variables", and functions that involve type variables are called "generic" or "polymorphic". Type parameters are discussed in detail in the next section.

Using Anonymous Function Values

Function values are so common in F# programming that it is very convenient to define them without giving them names. Here is a very simple example:

val primes : int list = [2;3;5;7]

> let primeCubes = List.map (fun n -> n * n * n) primes;;

The definition of primeCubes uses the "anonymous function" (fun n -> n * n * n). These are similar to function definitions but are unnamed and appear as an expression rather than as a let declaration. fun is a keyword meaning "function", n represents the argument to the function, and n*n*n is the result of the function. The overall type of the anonymous function expression is int -> int. We could have this technique to avoid defining the intermediary function fetch in the sample above.

let resultsOfFetch = List.map (fun url -> (url, http url)) sites

We will see anonymous functions throughout this book. Here is another example:

Here we see two things:

* The argument of the anonymous function is a tuple pattern. The use of a tuple pattern automatically extracts the second element from each tuple and gives it the name p within the body of the anonymous function.

* Part of the tuple pattern is a "wildcard" pattern, indicated by an underscore. This indicates that we don't care what the first part of the tuple is, given we are only interested in extracting the length from the second part of the pair.

Computing with Aggregate Operators

Functions such as List.map are called "aggregate operators", and they are powerful constructs, especially when combined with the other features of F#. Here is a longer example where we use the aggregate operators List.filter and List.map to count the number of URL-links in each of three well-known web pages, and then collect stats on a group of pages:

let delimiters = [ ' '; 'n'; 't'; '<'; '>'; '=' ]

let getWords s = String.split delimiters s

let stats site =

let url = 'https://' + site

let html = http url

let hwords = html |> getWords

let hrefs = html |> getWords |> List.filter (fun s -> s = 'href')

(site,html.Length, hwords.Length, hrefs.Length)

> sites |> List.map stats;;

val it : (string * int * int * int) list

= [('www.live.com', 7728, 1156, 10);

('www.google.com', 2685, 496, 14);

The stats function generates the length of the html for the given website, the number of words in the text of that HTML, and the approximate number of links on that page.

The above code sample makes extensive use of the |> operator to "pipeline" operations. The F# library design ensures that a common, consistent set of aggregate operations is defined for each structured type. Figure 3.3 shows how the same design patterns occur for many different abstractions.

Figure 3.3: A Recurring Aggregate Operator Design Pattern from the F# Library

List.map ('a -> 'b) -> 'a list -> 'b list

Array.map ('a -> 'b) -> 'a[] -> 'b[]

Option.map ('a -> 'b) -> 'a option -> 'b option

Seq.map ('a -> 'b) -> #seq<'a> -> seq<'b>

The |> operator is perhaps the most important operator you use in your F# programming. Its definition is deceptively simple:

let (|>) x f = f x

Here is a use of the operator to compute the cubes of three numbers:

[1;2;3] |> List.map (fun x -> x * x * x)

This produces , just as if we'd written:

List.map (fun x -> x * x * x) [1;2;3]

In a sense |> is just "function application in reverse". However, the use of |> often has distinct advantages:

* Clarity. When used in conjunction with well-designed libraries, the |> operator allows us to perform the data transformations and iterations in a forward-chaining, pipelined style.

* Type inference. The use of the |> operator allows type information to be flowed from input objects through to the functions manipulating those objects. F# uses information collected from type inference to resolve some language constructs such as property accesses and method overloading. This relies on information being propagated left-to-right through the text of a program. In particular, typing information to the right of a position is not taken into account when resolving property access and overloads.

For completeness, here is the type of the operator:

val (|>) : 'a -> ('a -> 'b) -> 'b

Composing Functions with >>

Above we saw how the operator |> can be used to "pipe" values through a number of functions. This was a small example of the process of "computing with functions", and essential and powerful programming technique in F#. In this section we look at ways to compute new function values from existing ones using compositional techniques. First we look at function composition, which is one of the simplest ways of generating new values from old. For example, consider the following code:

google |> getWords |> List.filter (fun s -> s = 'href') |> List.length;;

We can rewrite this code using function composition as follows:

let countLinks = getWords >> List.filter (fun s -> s = 'href') >> List.length;;

google |> countLinks;;

Let's take a look at this more closely. We have defined countLinks as the composition of three function values using the operator >>. This operator is defined in the F# library as follows:

let (>>) f g x = g(f(x))

We can see from the definition that f >> g gives a function value that first applies f to the x and then applies g. Here is the type of >>:

val (>>) : ('a -> 'b) -> ('b -> 'c) -> 'a -> 'c

Note that >> is typically applied to only two arguments - those on either side of the binary operator, here named f and g. The final argument x is typically supplied at a later point. F# is very good at optimizing basic constructions of pipelines and composition sequences from functions - for example, the function countLinks above will become a single function calling the three functions in the pipeline in sequence. This means sequences of compositions can be used with relatively low overhead.

Building Functions with Partial Application

Composing functions is just one way to compute interesting new functions. Another useful way is through the use of "partial application". Here's an example:

let shift (dx,dy) (px,py) = (px + dx, py + dy)

let shiftRight = shift (1,0)

let shiftUp = shift (0,1)

let shiftLeft = shift (-1,0)

let shiftDown = shift (0,-1)

The last four functions have been defined by calling shift with only one argument, in each case leaving a residue function that expects an additional argument. F# Interactive will report the types as:

val shiftRight : (int * int) -> (int * int)

val shiftLeft : (int * int) -> (int * int)

val shiftUp : (int * int) -> (int * int)

Here is an example of the use shiftRight, and also the use of an inline application of shift to new arguments :

val it : (int * int) = (11,10)

> List.map (shift (2,2)) [ (0,0); (1,0); (1,1); (0,1) ];;

Using Local Functions

Partial application is one way in which functions can be "computed", rather than simply being defined. This technique becomes very powerful when combined with additional local definitions. Here's a simple and practical example, representing an idiom common in graphics programming:

open System.Drawing;;

let remap (r1: Rectangle) (r2: Rectangle) =

let scalex = float r2.Width / float r1.Width

let scaley = float r2.Height / float r1.Height

let mapx x = r2.Left + truncate (float (x - r1.Left) * scalex)

let mapy y = r2.Top + truncate (float (y - r1.Top) * scaley)

let mapp (p: Point) = new Point(mapx p.X, mapy p.Y)

mapp

The function remap computes a new function value mapp that maps points in one rectangle to points in another. F# Interactive will report the type as:

The type Rectangle is defined in the .NET library System.Drawing.dll and represents rectangles specified by integer coordinates. The computations on the interior of the transformation are performed in floating point to improve precision. We can use this as follows:

val mapp : Point -> Point

> mapp (new Point(100,100));;

val it : Point = X=50,Y=50

> mapp (new Point(150,150));;

val it : Point = X=150,Y=150

> mapp (new Point(200,200));;

The intermediate values scalex and scaley are only computed once. This is despite the fact that we've called the resulting function mapp three times. It may be helpful to think of mapp as a function object being generated by the remap function.

In the above sample: mapx, mapy and mapp are "local functions", i.e. functions defined locally as part of the implementation of remap. Local functions can be context-dependent, i.e. they can be defined in terms of any values and parameters that happen to be in scope. Here mapx is defined in terms of scalex, scaley, r1 and r2. Local functions are, if necessary, implemented by taking the "closure" of the variables they depend upon and storing them away until needed. In optimized F# code the F# compiler often avoids this implementation and intead passes extra arguments.

Using Functions as Abstract Values

Many useful "abstract" values can be modeled via function types and values. For example:

* The type unit -> unit is frequently used to model "actions", i.e. operations that run and perform some unspecified side effect. A sample implementation of this simple abstraction is the expression (fun () -> printf "Hello Worldn").

* Types of the form 'a -> 'a -> int are frequently used to model "comparison functions"over the type 'a. You will also see 'a * 'a -> int used for this purpose, where a tuple is accepted as the first argument. In both cases a negative results indicates "less than", zero "equals" and a positive "greater than". Many collection types will accept such a value as a configuration parameter. One frequently used implementation of this abstraction is provided by the F# compare function, which performs structural comparison on values (see Chapter 4).

* Types of the form 'a -> unit are frequently used to model "callbacks". Here 'a is a place-holder for the type of arguments passed to the callback, e.g. 'a may be System.Windows.Forms.MouseEventArgs.

* Types of the form unit -> 'a are frequently used to model "delayed computations", i.e. values that will, when required, produce a value of type 'a. For example, a threading library may accept such a function value and execute it on a different thread, eventually producing a value of type 'a. Delayed computations are related to lazy computations and comprehensions, discussed in Chapter 4.

* Types of the form 'a -> 'b are frequently used to model "transformers", e.g. functions that transform each element of a collection. You will see this pattern in the map operator for many common collection types.

* Types of the form 'a -> 'b -> 'b are frequently used to model "visitor accumulating functions", e.g. functions that visit each element of a collection (type 'a) and accumulate a result (type 'b). For example, a visitor function that accumulates integers into a set of integers would have type int -> Set<int> -> Set<int>.

Iterating with Aggregate Operators

It is very common to use data to drive control, and indeed in functional programming the distinction between data and control is often blurred: function values can be used as data, and data can influence control flow. One example is using a function such as List.iter to iterate over a list. Let's take a simple example:

let sites = [ 'https://www.live.com';

'https://www.google.com';

'https://search.yahoo.com' ]

sites |> List.iter (fun site -> printf '%s, length = %dn' site (http site).Length)

List.iter simply calls the given function (here an anonymous function) for each element in the input list. Here is its type:

Many additional aggregate iteration techniques are available, particularly by using values of type seq<_>. We cover this later in this chapter.

Abstracting Control with Functions

For example, let's abstract the common pattern of timing the execution of an operation (measured in wall-clock time). First we'll explore the use of System.DateTime.Now to get the wall clock time:

> let start = DateTime.Now;;

val start : DateTime = 30/04/20.. 23:00:11

> fetch 'https://www.newscientist.com';;

> let finish = DateTime.Now;;

val finish : DateTime = 30/04/20.. 23:00:13

> let elapsed = finish - start;;

Note the type TimeSpan has been inferred from the use of the overloaded operator in the expression finish - start. Overloaded operators are discussed in depth in ??. We can now wrap up this technique as a function time that acts as a new control operator:

open System

let time f =

let start = DateTime.Now

let res = f()

let finish = DateTime.Now

(res, finish - start)

This function runs the input function f, but takes the time on either side of the call. It then returns both the result of the function and the elapsed time. The inferred type is:

Here 'a is a "type variable" that stands for "any" type, and thus the function can be used to time functions that return any kind of result. Note that F# has automatically inferred a very general type for the function, a technique called "automatic generalization" that lies at the heart of F# programming. Automatic generalization is discussed in detail in the side panel on page PPP. We can now use this function as follows:

Getting Started with Sequences

Many program tasks require the iteration, aggregation and transformation of data streamed from various sources. One very important and very general way to code tasks is in terms of values of type System.Collections.Generic.IEnumerable<'a>, which is typically abbreviated to seq<'a> in F# code[DS7] . A seq<'a> is simply a value which generates "imperative iterators", which in turn yield results (of type 'a) on demand. They can wrap collections, computations and data streams, and are frequently used to represent the results of database queries. We will return to how this abstraction is defined in Chapter 6, but its role in applied F# programming is so central that a dedicated language construct is included to specify and transform seq<'a> values. In this section we look at some simple examples of working with seq<'a> values.

Range comprehensions

Simple seq values can be generated by using a range comprehension. In Chapter 2 we saw one simple example of a range comprehension over characters. For integer ranges these take the form for integer expressions n and m. The braces are not optional, and the spaces are required for constant ranges so the integers are not confused with floating point numbers:

Range expressions may also be specified using other numeric types such as double and single:

By default F# Interactive only shows the value of an seq to a limited depth. Indeed, seq values are "lazy", in the sense that they compute and return the successive elements on demand. This means you can create sequences representing very large ranges, and the elements of the sequence will only be computed if they are required by a subsequent computation. In the next example we don't actually create a concrete data structure containing 1 trillion elements, but rather an value which has the potential to yield up to this number of elements on demand. The default printing performed by F# Interactive forces this computation up to depth four.

The default increment for range comprehensions is always 1. A different increment may be used via range comprehensions of the form (n .. skip .. m)

val it : seq<int> = [ 1; 3; 5 ]

> ;;

If the skip causes the final element to be over-shot then the final element is not included in the result:

The and operators are overloaded operators in the same sense as and . This means they may be used with any type implementing a Range static method accepting two and/or three arguments of the given type (the F# compiler and library simulates the existence of these static methods for the basic .NET numeric types).

Iterating a sequence

seq<'a> values can be iterated using the for . in . do construct. We discuss related constructs for imperative looping and iteration in Chapter 4, Imperative Programming, but here give a simple example as this is a common way to examine the values of an seq:

val range : seq<int> = [ 0; 2; 4; 6 ]

> for i in range do

- printf 'i = %dn";;

i = 0

i = 2

i = 4

This operator forces the iteration of the entire seq, so must be used with care when working with sequences that may yield a large number of elements.

Transforming Sequences with Aggregate Operators

Any value of type seq<_> can be iterated and transformed using functions in the Microsoft.FSharp.Collections.Seq module. For example:

val range : seq<int> = [ 0; 1; 2; 3; ]

> range |> Seq.map (fun i -> (i,i*i));;

Some important values in this library module are shown in Figure 3.4. The following operators necessarily evaluate all the elements of the input seq immediately:

* Seq.iter. This iterates all elements, immediately applying a function to each one.

* Seq.to_list. This iterates all elements, building a new list. Lists are concrete, finite structure, so all elements are required immediately.

* Seq.to_array. This iterates all elements, building a new array. Arrays are concrete, finite structure, so all elements are required immediately.

All the other operators shown below return an seq<_>, and only force the computation of elements in the underlying seq<_> on demand.

Figure 3.4:Some Important Functions and Aggregate Operators from the Seq module

Seq.append : #seq<'a> -> #seq<'a> -> seq<'a>

Seq.concat : #seq< #seq<'a> > -> seq<'a>

Seq.choose : ('a -> 'b option) -> #seq<'a> -> seq<'b>

Seq.delay : (unit -> #seq<'a>) -> seq<'a>

Seq.empty : unit -> seq<'a>

Seq.iter : ('a -> unit) -> #seq<'a> -> unit

Seq.filter : ('a -> bool) -> #seq<'a> -> seq<'a>

Seq.map : ('a -> 'b) -> #seq<'a> -> seq<'b>

Seq.singleton : 'a -> seq<'a>

Seq.truncate : int -> #seq<'a> -> seq<'a>

Seq.to_list : #seq<'a> -> 'a list

Seq.of_list : 'a list -> seq<'a>

Seq.to_array : #seq<'a> -> 'a[]

Seq.of_array : 'a[] -> seq<'a>

Which types can be used as sequences?

The table in the previous section includes types prefixed with , e.g. #seq<'a>. This simply means that the function will accept any type that is compatible with (i.e. a subtype of) seq<'a>. The notions of subtyping and compatibility are explained in more detail in Chapter 5, Generics and Type Variables, but to OO programmers the concept will be very familiar, as it is the same as that used by C#, which itself is close to that used by Java. In practice it's very important to be aware of which types are compatible with which. This can easily be discovered by either using IntelliSense in tools such as Visual Studio, as when you hover over a type name the compatible types are shown as well. You can also refer to the online documentation for the F# libraries and .NET Framework, easily searched by typing a qualified type name into a major search engine.

Here are some of the types compatible with seq<'a>:

* Array types, e.g. int[] is compatibile with seq<int>

* Most F# and .NET collection types, e.g. System.Collections.Generic.SortedList<string> is compatible with seq<string>

The following types are not directly type-compatible with seq<'a>, but can readily be converted into sequences when needed. In particular, they can be used as sequences in comprehensions and for . in . do . loops, both of which are described below.

* Many .NET types are compatible with a somewhat deprecated non-generic .NET 1.0 construct called System.Collections.IEnumerable (note the absence of any generic parameter) but are not actually compatible with the newer construct System.Collections.Generic.IEnumerable<'a>, i.e. seq<'a> in F# code.

* Some .NET types such as System.Text.RegularExpressions.MatchCollection only support a GetEnumerator method, and can't always be used directly as values of type seq<'a>. However these can be converted into sequences by using them in conjunction with either the comprehension or loop syntax mentioned above, e.g. or for x in matchCollection do ..

* Somewhat surprisingly, F# list types such as int list are not directly compatible with seq<int> and so can't always be used directly where a seq<'a> is expected. This is for efficiency reasons: internally F# lists use the special value null to represent the empty list, and for various technical reasons null values can't be used as seq values. To convert an 'a list to an seq<'a> you can use List.to_IEnumerable[DS10] , or use the list value as part of a comprehension, as discussed below.

Lazy Sequences from External Sources

seq<'a> values are frequently used to represent the process of streaming data from an external source, e.g. from a database query or from a computer's file system. For example, the following recursive function constructs an seq<string> that represents the process of recursively reading the names of all the files under a given path. The return types of Directory.GetFiles and Directory.GetDirectories are string[], and as noted above this type is always compatible with seq<string>.

open System.IO

let rec allFiles dir =

let files = Directory.GetFiles(dir)

let subdirs = Directory.GetDirectories(dir)

Seq.append

files

(subdirs |> Seq.map allFiles |> Seq.concat)

This gives the type:

Here is an example of the function being used on one of the author's machines:

val it : seq<string> =

= ['c:WINDOWSsystem32$winnt$.inf';

'c:WINDOWSsystem3212520437.cpx';

'c:WINDOWSsystem3212520850.cpx';

The allFiles function is interesting partly because it shows many aspects of F# working seamlessly together:

* Functions are values. The function allFiles is recursive and is used as a first-class function value within its own definition

* Pipelining. The pipelining operator |> provides a natural way to present the transformations applied to each subdirectory name

* Type inference. Type inference computes all types in the obvious way, without any type annotations.

* NET interoperability. The System.IO.Directory operations provide intuitive primitives, which can then be incorporated in powerful ways using succinct F# programs.

* Laziness where needed. The function Seq.map applies the argument function lazily (on demand), which means that subdirectories will not be read until really required.

One subtlety with programming with sequences is that side effects such as reading and writing from an external store should not in general happen until the sequence value is actually iterated. In particular, the allFiles function as specified above reads the top-level directory C: as soon as allFiles is applied to its argument. This may not be appropriate if the contents of C: are changing. You should delay the implementation of the sequence until iteration is performed. That is, when data sources may change and you wish to see the changes in subsequent iterations then a sequence value should be a "specification" of a how to generate a sequence rather than a single read of the data source. You can achieve this by using Seq.delay, shown below, and see the F# library documentation for more details)

open System.IO

let rec allFiles dir =

Seq.delay (fun () ->

let files = Directory.GetFiles(dir)

let subdirs = Directory.GetDirectories(dir)

Seq.append

files

(subdirs |> Seq.map allFiles |> Seq.concat))

This also gives the type:

Comprehension Syntax

Aggregate operators are a very powerful way of working with Seq values. However, an even more convenient syntax is also provided for specifying the class of Seq values that can be built using operations such as choose, map, filter and concat. This syntax is called the enumeration comprehension syntax. It can also be used to specify the shapes of lists and arrays, as we will see below.

Comprehensions using "for"

The simplest form of a enumeration comprehension is . Here -> should be read as "yield". This is simply a shorthand way of writing Seq.map. As with range comprehensions the parentheses are not optional when using this syntax to generate seq values. For example, we can again generate an enumeration of numbers and their squares as follows:

The more complete form of this construct is (for pattern in seq -> expression). The pattern allows us to decompose the values yielded by the input enumerable. For example, we can consume the elements of squares using for (i,isquared) in squares:

The input seq may be a seq<'a>. Somewhat unusually, it may also be an F# list or indeed a value of any type supporting a GetEnumerator method. This is because some important types from the .NET libraries support this method without directly supporting the seq interface. Below is an example where the input is a list of options. If the pattern fails to match the element of the enumerable it is skipped and no result is yielded for that element:

Enriching Comprehensions with Additional Clauses

An enumerable comprehension always begins with for . in ., but additional clauses can also be given, each of which may be one of:

* A secondary iteration: for pattern in seq

* A filter: when expression

* A let-binding: let pattern = expression

* A final yield: -> expression

* A final yield of another sequence: ->> expression

* A final match& yield: match expression with pattern ->

* A final match& yield of another sequence: match expression with pattern ->>

Secondary iterations each yield an enumerable, all of which are collected and concatenated together. Filters allow us to skip elements that do not satisfy a given predicate. To see both of these in action, the following computes a checkerboard set of coordinates of a rectangular grid:

let checkerboardCoordinates n =

The let and match clauses in comprehensions allow us to compute intermediary results and filter results through failing matches. For example, the following code gets the creation time and last access time for each file in a directory.

let fileInfo dir =

The final yield of a comprehension may be another seq, signified through the use of the ->> symbol as the yield. The following sample shows how to redefine the allFiles function from the previous section using comprehension syntax.

let rec allFiles dir =

Seq.delay (fun () ->

Seq.append

)

Using Comprehension Syntax to Specify Lists and Arrays

The comprehension syntax for ranges and generated sequences can also be used to build list and array values. The syntax is identical except the surrounding parentheses are replaced by the usual for lists and for arrays. We discuss arrays in more detail in Chapter 3..

val squaresList : (int * int) list = [ (0,0); (1,1); (2,4); (3,9) ]

> let squaresArray = [| for i in (0 .. 3) -> i,i*i |];;