The purpose of this chapter is to illustrate the use of values of basic types: numbers, characters, truth values and strings by means of some examples. The concepts of operator overloading and type inference are explained. Furthermore, the chapter contains a gentle introduction to higher-order functions. It is explained how to declare operators, and the concepts of equality and ordering in F# are introduced. After reading the chapter the reader should be able to construct simple programs using numbers, characters, strings and truth values.

Numbers. Truth values. The unit type

From mathematics we know the set of natural numbers as a subset of the set of integers, which again is a subset of the rational numbers (i.e., fractions), and so on. In F#, however, the set of values with the type: int, for the integers, is considered to be disjoint from the set of values with the type: float, for floating-point numbers, that is, the part of the real numbers that are representable in the computer. The reason is that the encodings of integer and float values in the computer are different, and that the computer has different machine instructions for adding integer values and for adding float values, for example.

Tuples, records and tagged values are compound values obtained by combining values of other types. Tuples are used in expressing “functions of several variables” where the argument is a tuple, and in expressing functions where the result is a tuple. The components in a record are identified by special identifiers called labels. Tagged values are used when we group together values of different kinds to form a single set of values. Tuples, records and tagged values are treated as “first-class citizens” in F#: They can enter into expressions and the value of an expression can be a tuple, a record or a tagged value. Functions on tuples, records or tagged values can be defined by use of patterns.

Tuples

An ordered collection of n values (v1, v2,…,vn), where n > 1, is called an n-tuple. Examples of n-tuples are:

(10, true);;

val it : int * bool = (10, true)

((“abc”,1),–3);;

val it : (string * int) * int = ((“abc”, 1), –3)

A 2-tuple like (10,true) is also called a pair. The last example shows that a pair, for example, ((“abc”,1),–3), can have a component that is again a pair (“abc”,1). In general, tuples can have arbitrary values as components. A 3-tuple is called a triple and a 4-tupleis called a quadruple. An expression like (true) is not a tuple but just the expression true enclosed in brackets, so there is no concept of 1-tuple. The symbol () denotes the only value of type unit (cf. Page 23).

Functional languages make it easy to express standard recursion patterns in the form of higher-order functions. A collection of such higher-order functions on lists, for example, provides a powerful library where many recursive functions can be obtained directly by application of higher-order library functions. This has two important consequences:

1. 1. The functions in the library correspond to natural abstract concepts and conscious use of them supports high-level program design, and

2. 2. these functions support code reuse because you can make many functions simply by applying library functions.

In this chapter we shall study libraries for lists, sets and maps, which are parts of the collection library of F#. This part of the collection library is studied together since:

• It constitutes the immutable part of the collection library. The list, set and map collections are finite collections programmed in a functional style.

• There are many similarities in the corresponding library functions.

This chapter is a natural extension of Chapter 4 since many of the patterns introduced in that chapter correspond to higher-order functions for lists and since more natural program designs can be given for the two examples in Section 4.6 using sets and maps.

We will focus on the main concepts and applications in this book, and will deliberately not cover the complete collection library of F#. The functions of the collection library do also apply to (mutable) arrays. We address this part in Section 8.10.

This appendix provides complete programs of the keyword program from the Chapter 10. It consists of

• a section introducing the basic HTML concepts,

• a section containing the complete IndexGen program, and

• a section containing the complete NextLevelRefs program.

The remaining program for the keyword example: MakeWebCat, appears in Table 10.19. The source can also be found on the homepage of the book.

Web source files

The source of a web-page is a file encoded in the HTML (Hyper Text Mark-up Language) format. This section gives a brief introduction to HTML using the library documentation web-page as an example.

An HTML file is an ordinary text file using a special syntax. Certain characters like <, >, & and “ are delimiters defining the syntactical structure. The file consists of elements of the form <…> intermixed with text to be displayed. The following construction will for instance make a button with a link to a web-page:

<a href="http://msdn.microsoft.com/en-us/library/ee353439.aspx"> active pattern</a>

The text:

active pattern

is displayed in the button and a click will cause the browser to select the web-page given by the URI:

http://msdn.microsoft.com/en-us/library/ee353439.aspx

A sequence is a possibly infinite, ordered collection of elements seq [eo; e1;…]. The elements of a sequence are computed on demand only, as it would make no sense to actually compute an infinite sequence. Thus, at any stage in a computation, just a finite portion of the sequence has been computed.

The notion of a sequence provides a useful abstraction in a variety of applications where you are dealing with elements that should be processed one after the other. Sequences are supported by the collection library of F# and many of the library functions on lists presented in Chapter 5 have similar sequence variants. Furthermore, sequences can be defined in F# using sequence expressions, defining a process for generating the elements.

The type seq<′a> is a synonym for the .NET type IEnumerable<′a> and any .NET framework type that implements this interface can be used as a sequence. One consequence of this is, for the F# language, that lists and arrays (that are specializations of sequences) can be used as sequence arguments for the functions in the Seq library. Another consequence is that results from the Language-Integrated Query or LINQ component of the .NET framework can be viewed as F# sequences. LINQ gives query support for different kinds of sources like SQL databases and XML repositories.

Metrics, hemi-metrics, and open balls

A natural instance of topological space is given by metric spaces, as already studied in Chapter 3.

Note that metrics are symmetric: the distance between x and y is the same as the distance between y and x. There is no need to assume so in all generality, and Lawvere (2002) has already rejected the symmetry axiom as being artificial in various situations – although, as we shall see, symmetry certainly makes our lives easier in several important cases, notably in the study of completeness (see Section 7.1). We are led to the following definition.

Definition 6.1.1 (Hemi-metric, quasi-metric) Let X be a set. A hemi-metric d on X is a map from X × X to such that:

• d(x, x) = 0 for every x ∈ X;

• (Triangular inequality) d(x, y) ≤ d(x, z) + d(z, y) for all x, y, z ∈ X.

A set X with a hemi-metric is called a hemi-metric space.

A hemi-metric d, or a hemi-metric space, is said to be T0 if and only if d(x, y) = d(y, x) = 0 implies x = y. It is T1 if and only if the sole equality d(x, y) = 0 already implies x = y.

A quasi-metric is a T0 hemi-metric. A T0 hemi-metric space is called a quasi-metric space.

The most natural way one can introduce topology, and what topology is about, is to explain what a metric space is. A metric space is a set, X, equipped with a metric d, which serves to measure distances between points.

The purpose of this chapter is to introduce the basic notions that we shall explore throughout this book, in this more familiar setting.

However, we must face a conundrum. Imagine we explained what an open subset is in a metric space. In the more general settings we shall explore in later chapters, we would have to redefine opens. Redefinitions are bad mathematical practice, and for a good reason: we would never know which definition we would mean later on; i.e., are the opens we shall use meant to be those introduced in the metric case here, or the more general kind introduced in later chapters? So we shall only talk about sequential opens, not opens, here. Sequential opens will provide particular examples of opens, which we hope should be illuminating. We proceed similarly for sequentially closed subsets. The adjective “sequential” is itself justified by the fact that these notions will be defined through convergence of sequences – and convergence is arguably one of the central concepts in topology.

Metric spaces

Let us describe what a metric space, i.e., a set X with a metric d, is, in intuitive terms first.

The following is a prototypical example of a metric space; whenever one looks for intuitions about metric spaces, we should probably first imagine what is happening there. This example is the real plane. Think of it as a blank sheet of paper, extending indefinitely left, right, up, and down. On this sheet of paper, one can draw points.

Topology, topological spaces

Abstracting away from metrics, a topological space is a set, with a collection of so-called open subsets U, satisfying the following properties. We have already seen them, for sequentially open subsets of a metric space, in Proposition 3.2.7.

Definition 4.1.1 (Topology) Let X be a set. A topology on X is a collection of subsets of X, called the opens of the topology, such that:

• every union of opens is open (including the empty union, Ø);

• every finite intersection of opens is open (including the empty intersection, taken as X itself).

A topological space is a pair (X,O), where O is a topology on X.

We often abuse the notation, and write X itself as the topological space, leaving O implicit. It is also customary to talk about the elements of a topological space X as points.

Example 4.1.2 The sequentially open subsets of a metric space form a topology. This is what Proposition 3.2.7 states exactly.

Given a metric space X, d, we shall call metric topology the topology whose opens are the sequentially open subsets.

Example 4.1.3 We shall often consider ℝ with the metric topology of its L1 metric. We shall either call this space ℝ, or ℝ with its metric topology when there is a risk of confusion as to which topology is intended. There are indeed other natural candidates, as we shall see in Example 4.2.19, for instance.