F# Survival Guide

Lists and sequences are powerful collection types that are the workhorses of F# development. In this chapter, we will look at lists and sequences, study the breadth of their functionality, and see how they can be best applied.

Lists

Under the covers, F# implements a list via as a singly linked list that consists of data nodes allocated in a chain, where the first node (the head) contains some data and may refer to a “next” or downstream node. We make a distinction between the first node in the list (the head) and the “rest of the list”, collective referred to as “the tail.”

A linked list is a recursive data structure that terminates when the last node in the chain points to a sentinel value such as null or, in F#’s case, the empty list [] (see below). Before we can use a list, we need to create one, so let’s get to it.

Creating Lists

The very simplest list you can create or use is the empty list, represented by empty square brackets:

let emptyList = []
    // the empty list, head = tail = []
    // by itself, the empty list is of type 'T
    // once it contains an element, the list is of a fixed type

To create a list that initially contains some elements, you can enumerate the individual elements explicitly separated by semicolons, as shown here:

let fruit = ["apple"; "banana"; "orange"]
// list with 3 string elements (head = apple, tail = orange)

Note that the elements of a list appear between square braces and are separated by a semicolon (not a comma[1]), and they must all be of the same type, otherwise, F# will emit a compiler error, as in the following example:

The more common and pragmatic way to construct lists is to use list comprehensions.

List Comprehensions

List comprehensions are a succinct, powerful way to construct new lists. F# has two forms of list comprehension syntax: ranges and generators.

Ranges

Where the first_element is the first element in the list, step, which is optional, is the “count by” parameter, and the last_element is the final value. The first_element and last_element are inclusive, meaning they both appear in the list that F# constructs. Let’s take a look at a few examples:

To count down, e.g., from 10 to 0, you need to specify a negative step, as in the following example:

Generators

Generators are another form of list comprehension used extensively in functional programming. List comprehensions that use generators take the following form:

[for <identifier> in collection -> expr] or
[for <identifier> in collection do ... yield expr][2]

We will use both forms of list comprehensions in this text. Let break down each one in turn. The first form of list comprehension uses a lambda function to generate the list elements. In the following example, we create a list comprehension that generates the squares of the numbers from 1-10:

As you can see here, the square of every element from 1-10 is generated correctly. Suppose, however, we only want the squares of the even numbers from 1-10. The syntax provided in this form of the generator is insufficient to support selective element generation. This is where the second form of list comprehension comes into play.

Of course, if it suits you, you can always use the do…yield form of the list comprehension, sans the filtering expression:

It is also possible for a list comprehension to generate multiple dimensions, using two or more for loops:

yield and yield!

With list comprehensions, we first encounter the keyword yield. The keyword yield is used to generate a single element each time it is called. We saw examples of this above.

There is another form of yield, denoted yield! (pronounced yield bang) that is used to generate a collection of elements in the form of a list or sequence. Here is a simple example:

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

This list comprehension loops over the integers from 1-5, and for each integer the yield! expression will generate a collection of elements. When you’re working with arrays, lists, and sequences, you will sometimes use the yield! expression.

More on List Construction

We’ve looked at constructing an empty list, creating lists explicitly, and using list comprehensions to generate the lists’ elements. There are still several other ways we create lists: using the cons operator (::), concatenating two lists together using the list concatenation operator (@) and using recursion.

cons (::)
To add a new element to the head of a list, we use the right-associative cons operator (::). The list we start with may be empty or non-empty. Let’s take a look at an example:

It may be obvious to the careful reader that creating a list explicitly, e.g., ["apple"; "banana"; "orange"], is a shorthand for the cons operator equivalent “apple” :: “banana” :: “pears”::[]. The cons operator is often used in recursive algorithms to build up a resulting list based on some computation.

Note that the cons operator does not impact an existing list – lists are immutable. The cons operator returns a new list.

concat (@)

You can also build a new list from two or more existing lists via using the @ operator to concatenate them together. Given the definitions above, we can concatenate lists together like this:

let bigbasket = basket2 @ basket4 //["banana";"fruit";"apples";"peaches";"pears"]

Creating Lists using Recursion

In F#, we sometimes need to build a list programmatically. Let’s suppose, for example, we want to convert an array of integers to a list of integers. Although this is a contrived example, it demonstrates the idea:

Happily, the F# List and Array modules supply generic to_array and to_list functions repsectively, so we don’t need to write our own like we’ve done here. Note that we will see other ways to recursively build lists when we study pattern matching.

Using Lists

Now that we know how to create lists, we need to understand how best to use them. In this next section, we’ll cover some of the more interesting and useful List functions. Since we have covered many of the functional concepts, e.g. folding and filtering, when we discussed functions (Chapter 8), we won’t rehash them here. In addition, since we now know how to read generic type signatures, we’ll be able to understand the documentation for the List functions in all their majesty (OK, that’s a bit much).

Initialization

Yet another way to initialize a list is to use the List.init function. This function uses a lambda to initialize the list’s elements:

Checking for the Existence of Elements

Many times it’s necessary to check to see if a list contains elements or has a positive length. List.isEmpty and List.Length help us out here:

You may also want to test to see of the list contains at least one element that meets the criteria of a given predicate:

You can also write test to check if all elements of the given list satisfy the given predicate:

Accessing Elements

Because we generally process lists recursively, there are two functions that we use often. List.hd retrieves the first element in the list, while List.tl retrieves everything but the head:

val squares : int list = [0; 1; 4; 9; 16]
val head : int = 0
val tail : int list = [1; 4; 9; 16]

There is another function nth that retrieves the nth element from the list. The nth function makes the list look like an array from the perspective of element retrieval. The list‘s head is considered to be at index 0.

Finding and Filtering

You can find elements in a list by using predicates or by index. In the following example, we use List.find to find the first element for which the predicate is true. We then use the List.findIndex function to return the index of the first element that satisfies the given predicate.

let results = List.find(fun n -> n > 0 && n % 9 = 0) cubes
val results : int = 27

As we saw when we studied arrays, filtering is a common operation on collections. It should come as no surprise that List offers a filter function as well. This function returns a new collection containing all the elements that satisfy the given predicate.

let kids = ["jessica"; "kimberly"; "melissa"]
let youngest = List.filter(fun name -> name >= "k") kids

Sorting

Lists also give us the ability to sort them in various ways. The simplest but least powerful is the sort function. This function uses the natural order of the input arguments, e.g., strings are alphabetized, numbers are sorted lowest to highest, etc.:

If you need to take control over the sorting, you can use List.sortWith, which enables you to supply your own lamdba function. F# hands the lambda a pair of elements at a time (think of them as the left operand and the right operand) and the lambda returns either -1, 0 or 1 (-1 = left is smaller, 0 = both equal, 1 = right is smaller).

In the following example, we build a list of tuples. Each tuple contains the name of a planet, and it’s ordinal order from the sun (Mercury is the closest, followed by Venus, etc.) Our lambda function extracts the second element from each tuple (using F#’s snd function) and uses them as the basis of the sort.

let distanceFromSun =
List.sortWith(fun x y -> if (snd x) < (snd y) then -1 else 1) planets

Note that quite often, we’ll use the pipeline operator to feed input into List’s functions. We could have written the previous example as follows:

Using Aggregate Operators

The List module also provides a family of aggregate functions. These functions are quite powerful, and enable you to implement sophisticated processing engines. Note that we saw many of these functions when we discussed arrays. Let’s take a look at them again from the perspective of the List module.

Iteration

The List.iter family of functions iterates through each element in the list, calling a function for each element visited. Note that the List.iter functions do not return a value - they simply enable you to visit each element. The function that’s executed per element must return unit.

The other functions in the family include List.iter2, List.iteri, and List.iteri2. Let’s look at an example that uses 2 lists. The lists need to be the same size or F# will throw an exception.

let continents =
["n.america"; "s.america"; "europe"; "asia"; "africa"; "australia"; "antarctica"]

Mapping

Recall that mapping is the process of transforming one set of elements, the source, into another set of elements, the target. When F# executes List.map, it visits each element in the source and passes it to a (lambda) transformation function that we supply. In the following example, we convert a list of integers representing the ordinal order of planets into their corresponding names. Note that this is a very contrived example; however, I want to demonstrate that you can do much more than square numbers:

The first two lines are simple enough. They create the lists that we’ll use as the basis of our mapping. The next line (which extends over 3 physical lines) runs the List.map function over the planetOrds list. We can see that planetOrds is piped (|>) into List.map as a parameter. For each ordinal fed into List.map, F# executes the supplied lambda function. This lambda function interrogates the planets list, looking for a tuple whose second (snd) element equals that of the current ordinal. When it finds the correct tuple, it returns the first (fst) element of that tuple, which is the planet’s name. The target names array thus contains the list of planet names in ordinal order from the sun.

Folding

As discussed previously, functional languages use folding and unfolding to process collections. Folding (closely related to reducing) is the process of distilling a list to a single value, where unfolding is the process of generating a collection. The List module supports a family of fold methods, many of which we’ve seen already. The two primary methods in this family are fold (for folding left) and foldBack (for folding right). We present a few examples here for completeness.

let sum = List.fold accumulate 0 [1..10] // folding func, init accumulator, list

Note that in many examples of folding that you will see, the accumulator function, e.g., accumulate in the previous example, will be a mathematical operator listed in parentheses. For example, the add operator looks like this: ( + ) and the multiplication operator like this ( * ). We will cover operators and operator overloading later. For now, it’s sufficient for you to understand that these operators are (surprise, surprise) just more functions. They expect 2 parameters, e.g., a + b or x * y. To bring this idea home, the following example demonstrates computing a factorial using List.fold and the mathematical operator ( * ) as the accumulator function:

The foldBack function enables us to perform right folds (we process the input list from right to left vs. left to right). Note that folding a list left vs. folding it right can yield different results depending on the operator applied, i.e., folding is not commutative.

Recall that is you need access to the intermedia value of the folding operation, you can use List.scan and List.scanBack, as demonstated in Chapter 8.

Converting Lists

There are times when you’re working with a List, but need to turn it into a different data structure. This occurs often when you need to convert a list to an array or a sequence to take advantage of some functionality the other data structure offers, e.g., when you’re using a library that needs an array as input, or that you need the rich semantics of a sequence. The List module has two convenience functions for converting to arrays and sequences.

Sequences

Sequences, defined in the Microsoft.FSharp.Collections.Seq module, are conceptually similar to lists. Both data structures are used to represent an ordered collection of values all of homogenous type. However, unlike lists, elements in a sequence are computed lazily - as they are needed, rather than computed all at once. This gives sequences some interesting properties, such as the ability to represent infinite data structures.

A sequence is fundamentally an enumerable data structure that maps to System.Collections.Generic.IEnumerable<T> under the covers. The bottom line is that when you create a sequence, you are creating an IEnumerable.

Creating Sequences

When we talk about creating sequences, we generally talk about “generating sequences”, since the elements are produced on-demand, a.k.a., generated. Sequences are defined using the following syntax:

Similar to lists, sequences can be created using range expressions of various types, e.g., integers, floats, etc.

Because sequences are evaluated in a lazy manner, you can create very large sequences with almost zero penalty. When you create a large sequence (or any sequence for that matter), what you are really doing is setting up a collection that can be potentially generated. For example, to create a sequence with 10 million integers, we we can write the following:

This “big sequence” is no more expensive to create than the the first two in the previous example. The sequence elements are only generated when needed.

Sequence expressions may involve for, if and let expressions. These types of sequence expressions are akin to the list comprehensions discussed earlier. The general pattern for a sequence expression is:

seq { for value in expr .. expr -> expr } or
seq { for value in expr do .. yield expr } or
set { for pattern in seq -> expr }

Let’s look at some examples to illustrate the idea. You should already be familiar with the first two styles based on list comprehensions:

let s1 = seq { for i in 0..10 -> (i, i + i) }
let s2 = seq { for i in 0..10 do yield (i, i * i) }
let s3 = seq { for i in 0..10 do if i % 3 = 0 then yield i }

Using a let expression in a sequence expression enables you to compute intermediary results. A common example is shown below:

The examples above all used the yield keyword to return a single result. As with lists, you can use the yield! (yield bang)[4] keyword to return another sequence vs. a single element. The following examples demonstrates the use of yield! in sequence expressions:[5]

In addition to the use of yield! we see here another common sequence pattern – that of using a secondary iteration (another for loop). F# deals with multiple interations in sequences expressions by generating secondary sequences and concatenating the results to the previous ones.

The last form of sequence expression uses a pattern. A pattern, which we will cover in detail in Chapter 11, is an input with a known structure. Pattern matching is the act of checking to see if the structure of the given pattern matches a set of rules. F# understands patterns and can carry out pattern matching in a variety of contexts. For our immediate purposes, let’s take a look at a sequence expression that leverages patterns:

Here, tups is a list of tuples. Each tuple in this list has the structure (x, y). In the next line, we ask F# to match up the structure (a, b) with the structure (x,y), e.g., (1,2) would match and set a=1 and b=2, the values from the tups element. If the patterns match, as they do here, F# assigns the first element, a, to the first element of the tuple, and the second element, b, to the second element of the tuple. It then yields (->) a new tuple which contains the values in reverse order. The output from the F# Interactive Console is:

val tups : (int * int) list = [(1, 2); (3, 4); (5, 6); (7, 8)]
val revtups : seq<int * int>

Because revtups is a sequence, the values aren’t generated yet – they simply can be generated. Let’s force F# to generate the elements of the sequence and output them to the F# Interactive Console:

Note that sequences are compatible with List, Array or [], and the other .NET collection types such as System.Collections.Generic.SortedList<T>.

Using Sequences

Like arrays and lists, sequences support iteration, aggregate operations such as folding, mapping, etc. The functions , e.g., Seq.map, defined in the Seqe module are exact parallels to those defined in the List and Array modules; therefore, it doesn’t make a lot of sense to rehash them here. Instead, let’s examine some of the new and different functions specific to sequences themselves. Of course, the functions we discuss here are not exhaustive, but representative of the more commonly used ones. As with any module, please consult the documentation for full details.[6]

Seq.delay is a function that creates a sequence from a function that itself return a sequence. Why on earth would you need that, since standard sequences are already delay computed? The answer is rooted in the fact that the creation of certain sequences can cause side effects – and you may want to delay those side effects. Side effects are prevelant, for example, when you interact with the .NET libraries. Let’s take a common example of iterating over the directories and files in a given directory, which we discussed previously:

In this example, the creation of the sequence causes F# to generate the first set of files from the root directory dir passed into the function. From Don Syme’s Expert F#:

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.

So, the moral of the story is: when you are interacting with external data sources that can change out from under you, and you want to make sure that you get the latest-and-greatest data from these sources via sequences, consider using Seq.delay.

To provide a bit more insight into what the compiler generates, we can use Reflector to get a better sense of what’s happening (C# syntax as produced by Reflector). Here is what the non-delayed function looks like:

As you can see, the non-delayed version constructs the IEnumerable immediately, where the delayed version waits to construct the IEnumerable. If the construction of the IEnumerable produces unwanted side effects, you have Seq.delay at your disposal.

One of the functions that we did not cover when discussing Arrays or Lists is concat (used in Don Syme’s example above). While not the exclusive domain of the Seq module, you will see it used with sequences somewhat often. With a name like concat, it’s probably not too surprising that it concatenates its inputs together. It is often used in conjunction with recursive functions and data structures for building up a result. concat takes a list of enumerables and returns a single enumerable. Most of the examples on this topic are somewhat arcane, so to be clear we’ll create a simple, albeit contrived, example to demonstrate the idea. For this example, it’s easiest to build a data structure that explicitly contains a collection of enumerables. We will tap into the .NET libraries for help.[7]

Note that Seq.concat differs from a similarly named function Seq.append, the names of which can be confusing. Whereas concat “strings together” a set of enumerables into a single enumerable, append takes two sequences and adds one to the end of the other. The function signatures tell the story:

val concat_sig : (seq<#seq<'b>> -> seq<'b>)
val append_sig : (seq<'a> -> seq<'a> -> seq<'a>)

What these signatures tell us is that concat is a function that takes a sequence set and returns a sequence that is type compatible with the set. The #seq notation has to do with flexible types, which we’ll cover later. The signature for append, on the other hand, tells us that this function takes 2 different sequences and returns a new sequence.

Converting Sequences

When working with sequences, it’s often convenient to turn them into arrays and lists. To convert a sequence into an array, use the Seq.to_array function, as shown here:

You have the same option to turn the sequence into a list as well using Seq.to_list:

Well, you know now enough about lists and sequences to understand many of the samples that you will encounter in the wild. You also have enough background to make some sense of the F# documentation, and can probably write some non-trivial F# code. Let’s use this momentum and dive into pattern matching.

What You Need to Know

· Lists are immutable data structures that hold an ordered set of elements, all of the same type. Under the covers, Lists are implemented as singly linked lists.

· Lists, like most data structures in functional programming, are generally processed recursively.

· Lists have a wide range of built-in operations including folding, mapping, zipping, etc. You should already have enough F# knowledge now to understand the documentation for Lists.

· Lists can be constructed using the cons (::) operator, the concatenation (@) operator, using explicit delineation of elements, or via list comprehensions.

· During iteration/comprehension, yield returns a single element, while yield! (yield bang) return a collection of elements.

· Sequences are enumerable data structures whose elements are evaluated lazily (on demand). In other words, they are F#’s way to create and use IEnumerable<T>.

· You create sequences using the seq { } syntax and a sequence expression. The expression can list the elements explicitly, use a compatible collection such as a list, or use an arbitrary function to generate the elements.

· Like lists and arrays, sequences support a full complement of functions including mapping, unfolding, and (unique to sequences) infinite constructs.

[1] Using commas is a common mistake, and results in type-related error messages.

[2] You may see older F# examples that use a when guard in list comprehension. As of this writing (Sep 2009), the when guard is deprecated. Use do…yield instead.

[3] No, since the cons operator is outstanding. To convert this to a tail recursive function, we need an “accumulator.”

[4] In some texts and samples, you might see yield! replaced with the ->> operator. As of this writing, the ->> operator is deprecated. Use yield! instead.

[5] This sample taken from Expert F#, by Don Syme.

[6] One of my goals with this text is to enable you to read and understand the F# documentation at a fairly deep level.

[7] This sample was adapted from a similar example in Foundations of F# by Robert Pickering.

Introduction