Functional Programming

---

You saw in Chapter 1 that pure functional programming treats everything as a value, including functions. Although F# is not a pure functional language, it does encourage you to program in the functional style; that is, it encourages you to use expressions and computations that return a result, rather than statements that result in some side effect. In this chapter, we’ll survey the major language constructs of F# that support the functional programming paradigm and learn how they make it easier to program in the functional style.

Literals

Literals represent constant values and are useful building blocks for computations. F# has a rich set of literals, which we will see in the next example.

In F#, string literals can contain newline characters, and regular string literals can contain standard escape codes. Verbatim string literals use a backslash (\) as a regular character, and two double quotes ("") are the escape code for a quote. You can define all integer types using hexadecimal and octal by using the appropriate prefix and postfix indicator. The following example shows some of these literals in action being bound to identifiers, which are described in the section Identifiers and let Bindings a little later in this chapter.

// Some strings.

let message = "Hello

World\r\n\t!"

let dir = @"c:\projects"

// A byte array.

let bytes = "bytesbytesbytes"B

// Some numeric types.

let xA = 0xFFy

let xB = 0o7777un

let xC = 0b10010UL

Functions

In F#, functions are defined using the keyword fun. The function’s arguments are separated by spaces, and the arguments are separated from the function body by an ASCII arrow (->).

Here is an example of a function that takes two values and adds them together:

fun x y -> x + y

Notice that this function does not have a name; this is a sort of function literal. Functions defined in this way are referred to as anonymous functions, lambda functions, or just lambdas.

The idea that a function does not need a name may seem a little strange. However, if a function is to be passed as an argument to another function, it may not need a name, especially if the task it’s performing is relatively simple.

If you need to give the function a name, you can bind it to an identifier, as described in the next section.

Identifiers and let Bindings

Identifiers are the way you give names to values in F# so you can refer to them later in a program. You define an identifier using the keyword let followed by the name of the identifier, an equal sign, and an expression that specifies the value to which the identifier refers. An expression is any piece of code that represents a computation that will return a value. The following expression shows a value being assigned to an identifier:

let x = 42

To most people coming from an imperative programming background, this will look like a variable assignment. There are many similarities, but a key difference is that in pure functional programming, once a value is assigned to an identifier, it does not change. This is why I will refer to them throughout this book as identifiers, rather than variables.

Under some circumstances you can redefine identifiers. This may look a little like an identifier changing value, but it is subtly different. Also, in imperative programming in F#, the value of an identifier can change in some circumstances. In this chapter, we focus on functional programming in which identifiers do not change their values.

An identifier can refer to either a value or a function, and since F# functions are really values in their own right, this is hardly surprising. This means F# has no real concept of a function name or parameter name; these are just identifiers. You can bind an anonymous function to an identifier the same way you can bind a string or integer literal to an identifier:

let myAdd = fun x y -> x + y

However, as it is very common to need to define a function with a name, F# provides a short syntax for this. You write a function definition the same way as a value identifier, except that a function has two or more identifiers between the let keyword and the equal sign, as follows:

let raisePowerTwo x = x ** 2.0

The first identifier is the name of the function, raisePowerTwo, and the identifier that follows it is the name of the function’s parameter, x. If a function has a name, it is strongly recommended that you use this shorter syntax for defining it.

The syntax for declaring values and functions in F# is indistinguishable because functions are values, and F# syntax treats them both similarly. For example, consider the following code:

let n = 10

let add a b = a + b

let result = add n 4

printfn "%i" (result)

On the first line, the value 10 is assigned to the identifier n. On the second line, an add function, which takes two arguments and adds them together, is defined. Notice how similar the syntax is, with the only difference being that a function has parameters that are listed after the function name. Since everything is a value in F#, the literal 10 on the first line is a value, and the result of the expression a + b on the next line is also a value that automatically becomes the result of the add function. Note that there is no need to explicitly return a value from a function as you would in an imperative language.

Identifier Names

There are some rules governing identifier names. Identifiers must start with an underscore (_) or a letter, and can then contain any alphanumeric character, underscore, or a single quotation mark ('). Keywords cannot be used as identifiers. As F# supports the use of a single quotation mark as part of an identifier name, you can use this to represent “prime” to create identifier names for different but similar values, as in this example:

let x = 42

let x' = 43

F# supports Unicode, so you can use accented characters and letters from non-Latin alphabets as identifier names:

let 标识符 = 42

If the rules governing identifier names are too restrictive, you can use double tick marks (``) to quote the identifier name. This allows you to use any sequence of characters—as long as it doesn’t include tabs, newlines, or double ticks—as an identifier name. This means you could create an identifier that ends with a question mark, for example (some programmers believe it is useful to put a question mark at the end of names that represent Boolean values):

let ``more? `` = true

This can also be useful if you need to use a keyword as an identifier or type name:

let ``class`` = "style"

For example, you might need to use a member from a library that was not written in F# and has one of F#’s keywords as its name. Generally, it’s best to avoid overuse of this feature, as it could lead to libraries that are difficult to use from other .NET languages.

Scope

The scope of an identifier defines where you can use an identifier (or a type, as discussed in the Defining Types section in the next chapter) within a program. It is important to have a good understanding of scope, because if you try to use an identifier that’s not in scope, you will receive a compile error.

All identifiers—whether they relate to functions or values—are scoped from the end of their definitions until the end of the sections in which they appear. So, for identifiers that are at the top level (that is, identifiers that are not local to another function or other value), the scope of the identifier is from the place where it’s defined to the end of the source file. Once an identifier at the top level has been assigned a value (or function), this value cannot be changed or redefined. An identifier is available only after its definition has ended, meaning that it is not usually possible to define an identifier in terms of itself.

You will have noticed that in F#, you never need to explicitly return a value; the result of the computation is automatically bound to its associated identifier. So, how do you compute intermediate values within a function? In F#, this is controlled by whitespace. An indentation creates a new scope, and the end of this scope is signaled by the end of the indentation. Indentation means that the let binding is an intermediate value in the computation that is not visible outside this scope. When a scope closes (by the indentation ending) and an identifier is no longer available, it is said to drop out of scope or to be out of scope.

To demonstrate scope, the following example shows a function that computes the point halfway between two integers. The third and fourth lines show intermediate values being calculated.

// Function to calculate a midpoint.

let halfWay a b =

    let dif = b - a

    let mid = dif / 2

    mid + a

printfn "%i" (halfWay 10 20)

First, the difference between the two numbers is calculated, and this is assigned to the identifier dif using the let keyword. To show that this is an intermediate value within the function, it is indented by four spaces. The choice of the number of spaces is left to the programmer, but the convention is four. After that, the example calculates the midpoint, assigning it to the identifier mid using the same indentation. Finally, the desired result of the function is the midpoint plus a, so the code can simply say mid + a, and this becomes the function’s result.

Note: You cannot use tabs instead of spaces for indenting, because these can look different in different text editors, which causes problems when whitespace is significant.

Capturing Identifiers

You have already seen that in F#, you can define functions within other functions. These functions can use any identifier in scope, including definitions that are also local to the function where they are defined. Because these inner functions are values, they could be returned as the result of the function or passed to another function as an argument. This means that although an identifier is defined within a function such that it is not visible to other functions, its actual lifetime may be much longer than the function in which it is defined. Let’s look at an example to illustrate this point. Consider the following function, defined as calculatePrefixFunction:

// Function that returns a function to

let calculatePrefixFunction prefix =

    // calculate prefix.

    let prefix' = Printf.sprintf "[%s]: " prefix

    // Define function to perform prefixing.

    let prefixFunction appendee =

        Printf.sprintf "%s%s" prefix' appendee

    // Return function.

    prefixFunction

   

// Create the prefix function.

let prefixer = calculatePrefixFunction "DEBUG"

// Use the prefix function.

printfn "%s" (prefixer "My message")

This function returns the inner function it defines, prefixFunction. The identifier prefix' is defined as local to the scope of the function calculatePrefixFunction; it cannot be seen by other functions outside calculatePrefixFunction. The inner function prefixFunction uses prefix', so when prefixFunction is returned, the value prefix' must still be available. calculatePrefixFunction creates the function prefixer. When prefixer is called, you see that its result uses a value that was calculated and associated with prefix':

 [DEBUG]: My message

Although you should have an understanding of this process, most of the time you don’t need to think about it because it doesn’t involve any additional work by the programmer. The compiler will automatically generate a closure to handle extending the lifetime of the local value beyond the function in which it is defined. The .NET garbage collection will automatically handle clearing the value from memory. Understanding this process of identifiers being captured in closures is probably more important when programming in imperative style where an identifier can represent a value that changes over time. When programming in the functional style, identifiers will always represent values that are constant, making it slightly easier to figure out what has been captured in a closure.

Recursion

Recursion means defining a function in terms of itself; in other words, the function calls itself within its definition. Recursion is often used in functional programming where you would use a loop in imperative programming. Many believe that algorithms are much easier to understand when expressed in terms of recursion rather than loops.

To use recursion in F#, use the rec keyword after the let keyword to make the identifier available within the function definition. The following example shows recursion in action. Notice how on the fifth line the function makes two calls to itself as part of its own definition.

// A function to generate the Fibonacci numbers.

let rec fib x =

    match x with

    | 1 -> 1

    | 2 -> 1

    | x -> fib (x - 1) + fib (x - 2)

// Call the function and print the results.

printfn "(fib 2) = %i" (fib 2)

printfn "(fib 6) = %i" (fib 6)

printfn "(fib 11) = %i" (fib 11)   

This function calculates the nth term in the Fibonacci sequence. The Fibonacci sequence is generated by adding the previous two numbers in the sequence, and it progresses as follows: 1, 1, 2, 3, 5, 8, 13…. Recursion is most appropriate for calculating the Fibonacci sequence, because the definition of any number in the sequence, other than the first two, depends on being able to calculate the previous two numbers, so the Fibonacci sequence is defined in terms of itself.

Although recursion is a powerful tool, you should be careful when using it. It is easy to inadvertently write a recursive function that never terminates. Although intentionally writing a program that does not terminate is sometimes useful, it is rarely the goal when trying to perform calculations. To ensure that recursive functions terminate, it is often useful to think of recursion in terms of a base case and a recursive case:

• The recursive case is the value for which the function is defined in terms of itself. For the function fib, this is any value other than 1 and 2.
• The base case is the non-recursive case; that is, there must be some value where the function is not defined in terms of itself. In the fib function, 1 and 2 are the base cases.

Having a base case is not enough in itself to ensure termination. The recursive case must tend toward the base case. In the fib example, if x is greater than or equal to 3, then the recursive case will tend toward the base case because x will always become smaller and at some point reach 2. However, if x is less than 1, then x will grow continually more negative, and the function will repeat until the limits of the machine are reached, resulting in a stack overflow error (System.StackOverflowException).

The previous code also uses F# pattern matching, which is discussed in the Pattern Matching section later in this chapter.

Operators

In F#, you can think of operators as a more aesthetically pleasing way to call functions.

F# has two different kinds of operators:

• A prefix operator is an operator where the operands come after the operator.
• An infix operator sits in between the first and second operands.

F# provides a rich and diverse set of operators that you can use with numeric, Boolean, string, and collection types. The operators defined in F# and its libraries are too numerous to be covered in this section, so rather than looking at individual operators, we’ll look at how to use and define operators in F#.

As in C#, F# operators are overloaded, meaning you can use more than one type with an operator. However, unlike in C#, both operands must be the same type, or the compiler will generate an error. F# also allows users to define and redefine operators.

Operators follow a set of rules similar to C#’s for operator overloading resolution; therefore, any class in the BCL or any .NET library that was written to support operator overloading in C# will support it in F#. For example, you can use the + operator to concatenate strings, as well as to add a System.TimeSpan to a System.DateTime, because these types support an overload of the + operator. The following example illustrates this:

let rhyme = "Jack " + "and " + "Jill"

printfn "%string" rhyme

open System

let oneYearLater =

    DateTime.Now + new TimeSpan(365, 0, 0, 0, 0)

printfn "%A" oneYearLater

Unlike functions, operators are not values, so they cannot be passed to other functions as parameters. However, if you need to use an operator as a value, you can do this by surrounding it with parentheses. The operator will then behave exactly like a function. Practically, this has two consequences:

• The operator is now a function, and its parameters will appear after the operator:

let result = (+) 1 1

• As it is a value, it could be returned as the result of a function, passed to another function, or bound to an identifier. This provides a very concise way to define the add function:

let add = (+)

You’ll see how using an operator as a value can be useful later in this chapter when we look at working with lists.

Function Application

Function application, also sometimes referred to as function composition or composing functions, simply means calling a function with some arguments. The following example shows the add function being defined and then applied to two arguments. Notice that the arguments are not separated with parentheses or commas; only whitespace is needed to separate them.

let add x y = x + y

let result = add 4 5

printfn "(add 4 5) = %i" result

The results of this example, when compiled and executed, are as follows:

(add 4 5) = 9

In F#, a function has a fixed number of arguments and is applied to the value that appears next in the source file. You do not necessarily need to use parentheses when calling functions, but F# programmers often use them to define which function should be applied to which arguments. Consider the simple case where you want to add four numbers using the add function. You could bind the result of each function call to a new identifier, but for such a simple calculation this would be very cumbersome:

let add x y = x + y

let result1 = add 4 5

let result2 = add 6 7

let finalResult = add result1 result2

Instead, it is often better to pass the result of one function directly to the next function. To do this, use parentheses to show which parameters are associated with which functions:

let add x y = x + y

let result =

    add (add 4 5) (add 6 7)

Here, the second and third occurrences of the add function are grouped with the parameters 4, 5 and 6, 7, respectively, and the first occurrence of the add function will act on the results of the other two functions.

F# also offers another way to compose functions using the pipe-forward operator (|>). This operator has the following definition:

let (|>) x f = f x

This simply means it takes a parameter, x, and applies it to the given function, f, so that the parameter is now given before the function. The following example shows a parameter, 0.5, being applied to the function System.Math.Cos using the pipe-forward operator:

let result = 0.5 |> System.Math.Cos

This reversal can be useful in some circumstances, especially when you want to chain many functions together. Here is the previous add function example rewritten using the pipe-forward operator:

let add x y = x + y

let result = add 6 7 |> add 4 |> add 5

Some programmers think this style is more readable, as it has the effect of making the code read in a more right-to-left manner. The code should now be read as “add 6 to 7, forward this result to the next function which will add 4, and then forward this result to a function that will add 5.”

This example also takes advantage of the capability to partially apply functions in F#, which is discussed in the next section.

Partial Application of Functions

F# supports the partial application of functions (these are sometimes called partial or curried functions). This means you don’t need to pass all the arguments to a function at once. Notice that the final example in the previous section passes a single argument to the add function, which takes two arguments. This is very much related to the idea that functions are values. So we can create an add function, pass one argument to it, and bind the resulting function to a new identifier:

let add x y = x + y

let addFour = add 4

Because a function is just a value, if it doesn’t receive all its arguments at once it returns a value that is a new function waiting for the rest of the arguments. So in the example, passing just the value 4 to the add function results in a new function. I named the function addFour because it takes one parameter and adds the value 4 to it. At first glance, this idea can look uninteresting and unhelpful, but it is a powerful part of functional programming that you’ll see used throughout the book.

Pattern Matching

Pattern matching allows you to look at the value of an identifier and then make different computations depending on its value. It might be compared to the switch statement in C++ and C#, but it is much more powerful and flexible. Programs that are written in the functional style tend to be written as series of transformations applied to the input data. Pattern matching allows you to analyze the input data and decide which transformation should be applied to it, so pattern matching fits in well with programming in the functional style.

The pattern matching construct in F# allows you to pattern match over a variety of types and values. It also has several different forms and crops up in several places in the language.

The simplest form of pattern matching is matching over a value. You have already seen this in the Recursion section of this chapter, where it was used to implement a function that generated numbers in the Fibonacci sequence. To illustrate the syntax, the next example shows an implementation of a function that will produce the Lucas numbers, a sequence of numbers as follows: 1, 3, 4, 7, 11, 18, 29, 47, 76…. The Lucas sequence has the same definition as the Fibonacci sequence; only the starting points are different.

// Definition of Lucas numbers using pattern matching.

let rec luc x =

    match x with

    | x when x <= 0 -> failwith "value must be greater than 0"

    | 1 -> 1

    | 2 -> 3

    | x -> luc (x - 1) + luc (x - 2)

The syntax for pattern matching uses the keyword match, followed by the identifier that will be matched, then the keyword with, then all the possible matching rules separated by pipes (|). In the simplest case, a rule consists of either a constant or an identifier, followed by an arrow (->), and then the expression to be used when the value matches the rule. In this definition of the function luc, the second and third cases are literals—the values 1 and 2—and these will be replaced with the values 1 and 3, respectively. The fourth case will match any value of x greater than 2, and this will cause two further calls to the luc function.

The rules are matched in the order in which they are defined, and the compiler will issue an error if pattern matching is incomplete; that is, if there is some possible input value that will not match any rule. This would be the case in the luc function if you had omitted the final rule, because any values of x greater than 2 would not match any rule. The compiler will also issue a warning if there are any rules that will never be matched, typically because there is another rule in front of them that is more general. This would be the case in the luc function if the fourth rule were moved ahead of the first rule. In this case, none of the other rules would ever be matched because the first rule would match any value of x.

You can add a when guard (as in the first rule in the example) to give precise control over when a rule fires. A when guard is composed of the keyword when followed by a Boolean expression. Once the rule is matched, the when clause is evaluated, and the rule will fire only if the expression evaluates to true. If the expression evaluates to false, the remaining rules will be searched for another match. The first rule is designed to be the function’s error handler. The first part of the rule is an identifier that will match any integer, but the when guard means the rule will match only those integers that are less than or equal to zero.

If you want, you can omit the first |. This can be useful when the pattern match is small and you want to fit it on one line. You can see this in the next example, which also demonstrates the use of the underscore (_) as a wildcard.

let booleanToString x =

    match x with false -> "False" | _ -> "True"

The _ will match any value and is a way of telling the compiler that you’re not interested in using this value. For example, in this booleanToString function, you do not need to use the constant true in the second rule, because if the first rule is matched you know that the value of x will be true. Moreover, you do not need to use x to derive the string "True", so you can ignore the value and just use _ as a wildcard.

Another useful feature of pattern matching is that you can combine two patterns into one rule through the use of the pipe (|). The next example, stringToBoolean, demonstrates this.

// Function for converting a Boolean to a string.

let booleanToString x =

    match x with false -> "False" | _ -> "True"

// Function for converting a string to a Boolean.

let stringToBoolean x =

    match x with

    | "True" | "true" -> true

    | "False" | "false" -> false

    | _ -> failwith "unexpected input"

The first two rules have two strings that should evaluate to the same value, so rather than having two separate rules, you can just use | between the two patterns.

It is also possible to pattern match over most of the types defined by F#. The next two examples demonstrate pattern matching over tuples, with two functions that implement a Boolean And and Or using pattern matching. Each takes a slightly different approach.

let myOr b1 b2 =

    match b1, b2 with

    | true, _ -> true

    | _, true -> true

    | _ -> false

let myAnd p =

    match p with

    | true, true -> true

    | _ -> false

The myOr function has two Boolean parameters that are placed between the match and with keywords and separated by commas to form a tuple. The myAnd function has one parameter, which is itself a tuple. Either way, the syntax for creating pattern matches for tuples is the same and similar to the syntax for creating tuples.

If it’s necessary to match values within the tuple, the constants or identifiers are separated by commas, and the position of the identifier or constant defines what it matches within the tuple. This is shown in the first and second rules of the myOr function and in the first rule of the myAnd function. These rules match parts of the tuples with constants, but you could use identifiers if you want to work with the separate parts of the tuple later in the rule definition. Just because you’re working with tuples doesn’t mean you always need to look at the various parts that make up the tuple.

The third rule of myOr and the second rule of myAnd show the whole tuple matched with a single _ wildcard character. This, too, could be replaced with an identifier if you want to work with the value in the second half of the rule definition.

Because pattern matching is such a common task in F#, the language provides alternative shorthand syntax. If the sole purpose of a function is to pattern match over something, then it may be worth using this syntax. In this version of the pattern-matching syntax, you use the keyword function, place the pattern where the function’s parameters would usually go, and then separate all the alternative rules with |. The next example shows this syntax in action in a simple function that recursively processes a list of strings and concatenates them into a single string.

// Concatenate a list of strings into a single string.

let rec conactStringList =

    function head :: tail -> head + conactStringList tail

           | [] -> ""

// Test data.

let jabber = ["'Twas "; "brillig, "; "and "; "the "; "slithy "; "toves "; "..."]

// Call the function.

let completJabber = conactStringList jabber

// Print the result.

printfn "%s" completJabber

The results of this example, when compiled and executed, are as follows:

'Twas brillig, and the slithy toves ...

Pattern matching is one of the fundamental building blocks of F#, and we’ll return to it several times in this book. We’ll look at pattern matching over lists with record types and union types in the next chapter.

Control Flow

F# has a strong notion of control flow. In this way, it differs from many pure functional languages, where the notion of control flow is very loose, because expressions can be evaluated in essentially any order. The strong notion of control flow is apparent in the if… then… else… expression.

In F#, the if… then… else… construct is an expression, meaning it returns a value. One of two different values will be returned, depending on the value of the Boolean expression between the if and then keywords. The next example illustrates this. The if… then… else… expression is evaluated to return either "heads" or "tails" depending on whether the program is run on an even second or an odd second.

let result =

    if System.DateTime.Now.Second % 2 = 0 then

        "heads"

    else

        "tails"

printfn "%A" result       

It’s interesting to note that the if… then… else… expression is just convenient shorthand for pattern matching over a Boolean value. The previous example could be rewritten as follows:

let result =

    match System.DateTime.Now.Second % 2 = 0 with

    | true -> "heads"

    | false ->  "tails"

printfn "%A" result

The if… then… else… expression has some implications that you might not expect if you are more familiar with imperative-style programming. F#’s type system requires that the values being returned by the if… then… else… expression must be the same type, or the compiler will generate an error. So, if in the previous example, you replaced the string "tails" with an integer or Boolean value, you would get a compile error. If you really require the values to be of different types, you can create an if… then… else… expression of type obj (F#’s version of System.Object) as shown in the next example, which prints either "heads" or false to the console.

let result =

    if System.DateTime.Now.Second % 2 = 0 then

        box "heads"

    else

        box false

       

printfn "%A" result

Imperative programmers may be surprised that an if… then… else… expression must have an else if the expression returns a value. This is logical when you consider the examples you’ve just seen. If the else were removed from the code, the identifier result could not be assigned a value when the if evaluated to false, and having uninitialized identifiers is something that F# (and functional programming in general) aims to avoid.

Lists

F# lists are simple collection types that are built into F#. An F# list can be an empty list, represented by square brackets ([]), or it can be another list with a value concatenated to it. You concatenate values to the front of an F# list using a built-in operator that consists of two colons (::), pronounced “cons.” The next example shows some lists being defined, starting with an empty list on the first line, followed by two lists where strings are placed at the front by concatenation:

let emptyList = []

let oneItem = "one " :: []

let twoItem = "one " :: "two " :: []

The syntax to add items to a list by concatenation is a little verbose, so if you just want to define a list, you can use shorthand. In this shorthand notation, you place the list items between square brackets and separate them with a semicolon (;), as follows:

let shortHand = ["apples "; "pears"]

Another F# operator that works on lists is the “at” symbol (@), which you can use to concatenate two lists together, as follows:

let twoLists = ["one, "; "two, "] @ ["buckle "; "my "; "shoe "]

All items in an F# list must be of the same type. If you try to place items of different types in a list—for example, you try to concatenate a string to a list of integers—you will get a compile error. If you need a list of mixed types, you can create a list of type obj (the F# equivalent of System.Object), as in the following code sample:

// The empty list.

let emptyList = []

// List of one item.

let oneItem = "one " :: []

// List of two items.

let twoItem = "one " :: "two " :: []

// List of two items.

let shortHand = ["apples "; "pairs "]

// Concatenation of two lists.

let twoLists = ["one, "; "two, "] @ ["buckle "; "my "; "shoe "]

// List of objects.

let objList = [box 1; box 2.0; box "three"]

I discuss types in F# in more detail in the next chapter, Types and Type Inference.

F# lists are immutable. In other words, once a list is created, it cannot be altered. The functions and operators that act on lists do not alter them, but they create a new, modified version of the list, leaving the old list available for later use if needed. The next example shows this.

// Create a list of one item.

let one = ["one "]

// Create a list of two items.

let two = "two " :: one

// Create a list of three items.

let three = "three " :: two

// Reverse the list of three items.

let rightWayRound = List.rev three

printfn "%A" one

printfn "%A" two

printfn "%A" three

printfn "%A" rightWayRound

An F# list containing a single string is created, and then two more lists are created, each using the previous one as a base. Finally, the List.rev function is applied to the last list to create a new reversed list.

Pattern Matching against Lists

The regular way to work with F# lists is to use pattern matching and recursion. The pattern-matching syntax for pulling the head item off a list is the same as the syntax for concatenating an item to a list. The pattern is formed by the identifier representing the head, followed by ::, and then the identifier for the rest of the list. You can see this in the first rule of concatList in the next example. You can also pattern match against list constants; you can see this in the second rule of concatList, where there is an empty list.

// List to be concatenated.

let listOfList = [[2; 3; 5]; [7; 11; 13]; [17; 19; 23; 29]]

// Definition of a concatenation function.

let rec concatList l =

    match l with

    | head :: tail -> head @ (concatList tail)

    | [] -> []

// Call the function.

let primes = concatList listOfList

// Print the results.

printfn "%A" primes

Taking the head from a list, processing it, and then recursively processing the tail of the list is the most common way of dealing with lists via pattern matching, but it certainly isn’t the only thing you can do with pattern matching and lists. The following example shows a few other uses of this combination of features.

// Function that attempts to find various sequences.

let rec findSequence l =

    match l with

    // Match a list containing exactly 3 numbers.

    | [x; y; z] ->

        printfn "Last 3 numbers in the list were %i %i %i"

            x y z

    // Match a list of 1, 2, 3 in a row.

    | 1 :: 2 :: 3 :: tail ->

        printfn "Found sequence 1, 2, 3 within the list"

        findSequence tail

    // If neither case matches and items remain,

    // recursively call the function.

    | head :: tail -> findSequence tail

    // If no items remain, terminate.

    | [] -> ()

// Some test data.

let testSequence = [1; 2; 3; 4; 5; 6; 7; 8; 9; 8; 7; 6; 5; 4; 3; 2; 1]

// Call the function.

findSequence testSequence

The first rule demonstrates how to match a list of a fixed length—in this case, a list of three items. Here, identifiers are used to grab the values of these items so they can be printed to the console. The second rule looks at the first three items in the list to see whether they are the sequence of integers 1, 2, 3; and if they are, it prints a message to the console. The final two rules are the standard head and tail treatment of a list, designed to work their way through the list, doing nothing if there is no match with the first two rules.

The results of this example, when compiled and executed, are as follows:

Found sequence 1, 2, 3 within the list

Last 3 numbers in the list were 3 2 1

Although pattern matching is a powerful tool for the analysis of data in lists, it’s often not necessary to use it directly. The F# libraries provide a number of higher-order functions for working with lists that implement the pattern matching for you, so you don’t need to repeat the code. To illustrate this, imagine you need to write a function that adds one to every item in a list. You can easily write this using pattern matching:

let rec addOneAll list =

    match list with

    | head :: rest ->

        head + 1 :: addOneAll rest

    | [] -> []

   

printfn "(addOneAll [1; 2; 3]) = %A" (addOneAll [1; 2; 3])

The results of this example, when compiled and executed, are as follows:

(addOneAll [1; 2; 3]) = [2; 3; 4]

However, the code is perhaps a little more verbose than you would like for such a simple problem. The clue to solving this comes from noticing that adding one to every item in the list is just an example of a more general problem: the need to apply some transformation to every item in a list. The F# core library contains a map function which is defined in the List module. It has the following definition:

let rec map func list =

    match list with

    | head :: rest ->

        func head :: map func rest

    | [] -> []

You can see that the map function has a very similar structure to the addOneAll function from the previous example. If the list is not empty, you take the head item of the list and apply the function, func, you are given as a parameter. This is then appended to the results of recursively calling map on the rest of the list. If the list is empty, you simply return the empty list. The map function can then be used to implement adding one to all items in a list in a much more concise manner:

let result = List.map ((+) 1) [1; 2; 3]

printfn "List.map ((+) 1) [1; 2; 3] = %A" result

Also note that this example uses the add operator as a function by surrounding it with parentheses, as described earlier in this chapter in the Operators section. This function is then partially applied by passing its first parameter but not its second. This creates a function that takes an integer and returns an integer, which is passed to the map function.

The List module contains many other interesting functions for working with lists, such as List.filter, which allows you to filter a list using a predicate, and List.fold, which is used to create a summary of a list.

Summary

This chapter has given you a short introduction to using F#’s functional features. These provide the programmer with a powerful but flexible way to create programs.