CHAPTER 3
Functional Programming
You saw in Chapter 1 that pure functional programming treats functions as values, relies on recursion for looping, and does not allow changes to state. In this chapter, you'll survey the major language constructs of F# that support the functional programming paradigm.
Identifiers
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 equals 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 a lot of similarities, but there are key differences. In pure functional programming, once a value is assigned to an identifier, it never changes. This is why I will refer to them throughout this book as identifiers and not variables. You will see in the "Scope" section later in this chapter that, under some circumstances, you can redefine identifiers and that in imperative programming in F#, in some circumstances, the value of an identifier can change.
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. (I discuss this relationship in detail in the "Functions and Values" section later in this chapter.) This means F# has no real concept of a function name or parameter name; they are all just identifiers. You write a function definition the same way as a value identifier, except a function has two or more identifiers between the let keyword and the equals 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.
Keywords
Most, if not all, programming languages have the concept of keywords. A keyword is a language token that the compiler reserves for special use. In F# you cannot use a keyword as an identifier name or a type name (I discuss types later in this chapter in "Defining Types"). The following are the F# keywords:
abstract |
lsl |
and |
lsr |
as |
lxor |
assert |
match member |
asr |
mod |
begin |
module |
class |
mutable namespace |
default |
new |
delegate |
null |
do |
of |
done |
open |
downcast |
or |
downto |
override |
else |
rec |
end |
sig |
exception |
static |
false |
struct |
finally |
then |
for |
to |
fun |
true |
function |
try |
if |
type |
in |
val |
inherit |
when |
inline |
upcast |
interface |
while |
land |
with |
lor |
The words listed next are not currently F# keywords but have been reserved for possible future use. It is possible to use them as identifiers or type names now, but the compiler will issue a warning if you do. If you care that your code is compatible with future versions of the compiler, then it is best to avoid using them. I will not use them in the examples in this book.
async |
method |
atomic |
mixin |
break |
namespace |
checked |
object |
component |
process |
const |
property |
constraint |
protected |
constructor |
public |
continue |
pure |
decimal |
readonly |
eager |
return |
enum |
sealed |
event |
switch |
external |
virtual |
fixed |
void |
functor |
volatile |
include |
where |
If you really need to use a keyword as an identifier or type name, you can use the double back quote syntax:
let ``class`` = "style"
The usual reason for doing this is when you need to use a member from a library that was not written in F# and that uses one of F#'s keywords as a name (you'll learn more about using non-F# libraries in Chapter 4). The best practice is to avoid using keywords as identifiers if possible.
Literals
Literals represent constant values and are useful building blocks for computations. F# has a rich set of literals, summarized in Table 3-1.
| Example | F# Type | .NET Type | Description |
"Hello ", "World
" |
string |
System.String |
A string in which a backslash () is an escape character |
@"c:dirfs", @"""" |
string |
System.String |
A verbatim string where a backslash () is a regular character |
"bytesbytesbytes"B |
byte array |
System.Byte[] |
A string that will be stored as a byte array |
'c' |
char |
System.Char |
A character |
true, false |
bool |
System.Boolean |
A Boolean |
0x22 |
int/int32 |
System.Int32 |
An integer as a hexadecimal |
0o42 |
int/int32 |
System.Int32 |
An integer as an octal |
0b10010 |
int/int32 |
System.Int32 |
An integer as a binary |
34y |
sbyte |
System.SByte |
A signed byte |
34uy |
byte |
System.Byte |
An unsigned byte |
34s |
int16 |
System.Int16 |
A 16-bit integer |
34us |
uint16 |
System.UInt16 |
An unsigned 16-bit integer |
34l |
int/int32 |
System.Int32 |
A 32-bit integer |
34ul |
uint32 |
System.UInt32 |
An unsigned 32-bit integer |
34n |
nativeint |
System.IntPtr |
A native-sized integer |
34un |
unativeint |
System.UIntPtr |
An unsigned native-sized integer |
34L |
int64 |
System.Int64 |
A 32-bit integer |
34UL |
uint64 |
System.Int64 |
An unsigned 32-bit integer |
3.0F, 3.0f |
float32 |
System.Single |
A 32-bit IEEE floating-point number |
3.0 |
float |
System.Double |
A 64-bit IEEE floating-point number |
3474262622571I |
bigint |
Microsoft.FSharp. |
An arbitrary large integer |
474262612536171N |
bignum |
Microsoft.FSharp. |
An arbitrary large number |
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 for a quote. You can define all integer types using hexadecimal and octal by using the appropriate prefix and postfix. The following example shows some of these literals in action, along with how to use the F# printf function with a %A pattern to output them to the console. The printf function interprets the %A format pattern using a combination of F#'s reflection (covered in Chapter 7) and the .NET ToString method, which is available for every type, to output values in a readable way. You can also access this functionality by using the print_any and any_to_string functions from the F# library.
#light
let message = "Hello
World
!"
let dir = @"c:projects"
let bytes = "bytesbytesbytes"B
let xA = 0xFFy
let xB = 0o7777un
let xC = 0b10010UL
let print x = printfn "A%" x
let main() =
print message;
print dir;
print bytes;
print xA;
print xB;
print xC
main()
The results of this example, when compiled and executed, are as follows:
"Hello
World
!"
"c:\projects"
[|98uy; 121uy; 116uy; 101uy; 115uy; 98uy; 121uy; 116uy; 101uy; 115uy; 98uy;
121uy; 116uy; 101uy; 115uy|]
-1y
4095
18UL
Values and Functions
Values and functions in F# are indistinguishable because functions are values, and F# syntax treats them both similarly. For example, consider the following code. On the first line, the value 10 is assigned to the identifier n; then on the second line, a function, add, which takes two parameters 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.
#light
let n = 10
let add a b = a + b
let addFour = add 4
let result = addFour n
printfn "result = %i" result
The results of this code, when compiled and executed, are as follows:
result = 14
F# also supports the idea of the partial application of functions (these are sometimes called partial or curried functions). This means you don't have to pass all the arguments to a function at once. I did this in the third line in the previous code, where I passed a single argument to the add function, which takes two arguments. This is very much related to the idea that functions are values. 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 that I have named 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.
This behavior may not always be appropriate; for example, if the function takes two floating-point parameters that represent a point, it may not be desirable to have these numbers passed to the function separately because they both make up the point they represent. You may alternatively surround a function's parameters with parentheses and separate them with commas, turning them into a tuple (rhymes with "couple"). You can see this in the following code, which will not compile because the sub function requires both parameters to be given at once. This is because sub now has only one parameter, the tuple (a, b), instead of two, and although the call to sub in the second line provides only one argument, it's not a tuple. You'll examine tuples properly later in this chapter in "Defining Types."
#light
let sub (a, b) = a - b
let subFour = sub 4
When attempting to compile this example, you will receive the following error message; this is because the program does not type check as you are trying to pass an integer to a function that takes a tuple.
prog.fs(15,19): error: FS0001: This expression has type
int
but is here used with type
'a * 'b
In general, functions that can be partially applied are preferred over functions that use tuples. This is because functions that can be partially applied are more flexible than tuples, giving users of the function more choice about how to use them. This is especially true when creating a library to be used by other programmers. You may not be able to anticipate all the ways your users will want to use your functions, so it is best to give them the flexibility of functions that can be partially applied.
You never need to explicitly return a value, but how do you compute intermediate values within a function? In F#, this is controlled by whitespace. An indention means that the let binding is an intermediate value in the computation, and the end of the expression is signaled by the end of the indented section.
To demonstrate this, the next example shows a function that computes the point halfway between two integers. The third and fourth lines show intermediate values being calculated. 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. Note that you cannot use tabs because these can look different in different text editors, which causes problems when whitespace is significant. After that, the example calculates the midpoint, assigning it to the identifier mid using the same indentation. Finally, you want the result of the function to be the midpoint plus a, so you can simply say mid + a, and this becomes the function's result.
#light
let halfWay a b =
let dif = b - a
let mid = dif / 2
mid + a
printfn "(halfWay 5 11) = %i" (halfWay 5 11)
printfn "(halfWay 11 5) = %i" (halfWay 11 5)The results of this example are as follows:
(halfWay 5 11) = 8
(halfWay 11 5) = 8
Note It's the #light declaration, which should be placed at the top of each F# source file, that makes whitespace significant in F#, allowing you to omit certain keywords and symbols such as in, ;, begin, and end. I believe that significant whitespace is a much more intuitive way of programming, because it helps the programmer decide how the code should be laid out; therefore, in this book, I'll cover the F# syntax only when #light is declared.
Scope
The scope of an identifier defines where you can use an identifier (or a type; see "Defining Types" later in this chapter) within a program. Scope is a fairly simple concept, but it is important to have a good understanding because if you try to use an identifier that's not in scope, you will get 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 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.
Identifiers within functions are scoped to the end of the expression that they appear in; ordinarily, this means they're scoped until the end of the function definition in which they appear. So if an identifier is defined inside a function, then it cannot be used outside it. Consider the next example, which will not compile since it attempts to use the identifier message outside the function defineMessage:
#light
let defineMessage() =
let message = "Help me"
print_endline message
print_endline message
When trying to compile this code, you'll get the following error message:
Prog.fs(34,17): error: FS0039: The value or constructor 'message' is not defined.
Identifiers within functions behave a little differently from identifiers at the top level, because they can be redefined using the let keyword. This is useful; it means that the F# programmer does not have to keep inventing names to hold intermediate values. To demonstrate, the next example shows a mathematical puzzle implemented as an F# function. Here you need to calculate lots of intermediate values that you don't particularly care about; inventing names for each one these would be an unnecessary burden on the programmer.
#light
let mathsPuzzle() =
print_string "Enter day of the month on which you were born: "
let input = read_int ()
let x = input * 4 // Multiply it by 4
let x = x + 13 // Add 13
let x = x * 25 // Multiply the result by 25
let x = x - 200 // Subtract 200
print_string "Enter number of the month you were born: "
let input = read_int ()
let x = x + input
let x = x * 2 // Multiply by 2
let x = x - 40 // Subtract 40
let x = x * 50 // Multiply the result by 50
print_string "Enter last two digits of the year of your birth: "
let input = read_int ()
let x = x + input
let x = x - 10500 // Finally, subtract 10,500
printf "Date of birth (ddmmyy): %i" x
mathsPuzzle()
The results of this example, when compiled and executed, are as follows:
Enter day of the month on which you were born: 23
Enter number of the month you were born: 5
Enter last two digits of the year of your birth: 78
Date of birth (ddmmyy): 230578
I should note that this is different from changing the value of an identifier. Because you're redefining the identifier, you're able to change the identifier's type, but you still retain type safety.
Note Type safety, sometimes referred to as strong typing, basically means that F# will prevent you from performing an inappropriate operation on a value; for example, you can't treat an integer as if it were a floating-point number. I discuss types and how they lead to type safety later in this chapter in the section "Types and Type Inference."
The next example shows code that will not compile, because on the third line you change the value of x from an integer to the string "change me", and then on the fourth line you try to add a string and an integer, which is illegal in F#, so you get a compile error:
#light
let changeType () =
let x = 1 // bind x to an integer
let x = "change me" // rebind x to a string
let x = x + 1 // attempt to rebind to itself plus an integer
print_string x
This program will give the following error message because it does not type check:
prog.fs(55,13): error: FS0001: This expression has type
int
but is here used with type
string
stopped due to error
If an identifier is redefined, its old value is available while the definition of the identifier is in progress but after it is defined; that is, after the new line at the end of the expression, the old value is hidden. If the identifier is redefined inside a new scope, the identifier will revert to its old value when the new scope is finished.
The next example defines a message and prints it to the console. It then redefines this message inside an inner function called innerFun that also prints the message. Then, it calls the function innerFun and after that prints the message a third time.
#light
let printMessages() =
// define message and print it
let message = "Important"
printfn "%s" message;
// define an inner function that redefines value of message
let innerFun () =
let message = "Very Important"
printfn "%s" message
// define message and print it
innerFun ()
// finally print message again
printfn "%s" message
printMessages()
The results of this example, when compiled and executed, are as follows:
Important
Very Important
Important
A programmer from the imperative world might have expected that message when printed out for the final time would be bound to the value Very Important, rather than Important. It holds the value Important because the identifier message is rebound, rather than assigned, to the value Very Important inside the function innerFun, and this binding is valid only inside the scope of the function innerFun, so once this function has finished, the identifier message reverts to holding its original value.
Note Using inner functions is a common and excellent way of breaking up a lot of functionality into manageable portions, and you will see their usage throughout the book. They are sometimes referred to as closures or lambdas, although these two terms have more specific meanings. A closure means that the function uses a value that is not defined at the top level, and a lambda is an anonymous function. The section "Anonymous Functions" later in the chapter discusses these concepts in more detail.
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.
#light
let rec fib x =
match x with
| 1 -> 1
| 2 -> 1
| x -> fib (x - 1) + fib (x - 2)
printfn "(fib 2) = %i" (fib 2)
printfn "(fib 6) = %i" (fib 6)
printfn "(fib 11) = %i" (fib 11)
The results of this example, when compiled and executed, are as follows:
(fib 2) = 1
(fib 6) = 8
(fib 11) = 89
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 always 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 the 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 nonrecursive 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 recurse 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 I discuss in the "Pattern Matching" section later in this chapter.
Anonymous Functions
F# provides an alternative way to define functions using the keyword fun; you can see this in the following example. Ordinarily, you would use this notation when it is not necessary to give a name to a function, so these are referred to as anonymous functions and sometimes called lambda functions or even just lambdas. The idea that a function does not need a name may seem a little strange, but if a function is to be passed as an argument to another function, then often you don't need to give it a name of its own. I demonstrate this idea in the section "Lists" later in this chapter when you look at operations on lists. The arguments defined for this style of function can follow the same rules as when defining a function with a name, meaning that you can define the arguments so they can be partially applied or defined in the form of a tuple (see the section "Defining Types" later in this chapter for an explanation of tuples). The following example shows two functions that are created and then immediately applied to arguments so that the identifier x holds the result of the function rather than the function itself:
#light
let x = (fun x y -> x + y) 1 2
You can create an anonymous function with the keyword function. Creating functions this way differs from using the keyword fun since you can use pattern matching when using the keyword function (see the section "Pattern Matching" later in this chapter). Consequently, it can be passed only one argument, but you can do a couple of things if the function needs to have multiple parameters. The first line of the following example shows a function using the function keyword written so the function can be partially applied, meaning the arguments can be passed one at a time if needed. The second line shows a function defined using the function keyword that takes a tuple argument.
let x1 = (function x -> function y -> x + y) 1 2
let x2 = (function (x, y) -> x + y) (1, 2)
The keyword fun is generally preferred when defining anonymous functions because it is more compact; you can see this is the case when browsing the source for the libraries and examples distributed with F#.
Operators
In F#, you can think of operators as a more aesthetically pleasing way to call functions.
F# has two different kinds of operators, prefix and infix; a prefix operator is an operator that takes one operand, and an infix operator takes two or more. Prefix operators appear before their operand, whereas infix operators appear between the first two 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 instead you'll look at the way you use and define operators in F# rather than looking at individual operators.
Like 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; I discuss how to do that at the end of this section.
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 stings (you can also use ^ for this) as well as to add a System.TimeSpan to a System.DataTime because these types support an overload of the + operator. The following example illustrates this:
#light
let ryhm = "Jack " + "and " + "Jill"
let anotherRyhm = "Wee " ^ "Willy " ^ "Winky"
open System
let oneYearLater =
DateTime.Now + new TimeSpan(365, 0, 0, 0, 0)
Users can define their own operators or redefine any of the existing ones if they want (although this is not always advisable, because the operators then no longer support overloading). Consider the following perverse example that redefines + to perform subtraction:
#light
let (+) a b = a - b
print_int (1 + 1)
User-defined (custom) operators must be nonalphanumeric and can be a single character or a group of characters. You can use the following characters in custom operators:
!$%&*+-./<=>?@^|~
:
Custom operators can start with any of the characters on the first line and after that can use any of these characters and also the colon (:), listed on the second line. The syntax for defining an operator is the same as using the let keyword to define a function, except the operator replaces the function name and is surrounded by parentheses so the compiler knows that the symbols are used as a name of an operator rather than as the operator itself. The following example shows defining a custom operator, +:*, that adds its operands and then multiplies them:
#light
let ( +:* ) a b = (a + b) * a * b
printfn "(1 +:* 2) = %i" (1 +:* 2)
The results of this example, when compiled and executed, are as follows:
(1 +:* 2) = 6
Unary operators always come before the operand; binary operators are always infix.
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:
#light
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:
#light
let shortHand = ["apples "; "pairs "]
F# has a second operator that works on lists; this 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, and 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. I discuss types in F# in more detail in "Types and Type Inference" and "Defining Types" later in this chapter.
#light
let emptyList = []
let oneItem = "one " :: []
let twoItem = "one " :: "two " :: []
let shortHand = ["apples "; "pairs "]
let twoLists = ["one, "; "two, "] @ ["buckle "; "my "; "shoe "]
let objList = [box 1; box 2.0; box "three"]
let printList l =
List.iter print_string l
print_newline()
let main() =
printList emptyList
printList oneItem
printList twoItem
printList shortHand
printList twoLists
for x in objList do
print_any x
print_char ' '
print_newline()
main()
The results of these examples, when compiled and executed, are as follows:
one
one two
apples pairs
one, two, buckle my shoe
1 2.000000 "three"
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, altered version of the list, leaving the old list available for later use if needed. The next example shows this. 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. When you print these lists, it is easy to see that all the original lists remain unaltered.
#light
let one = ["one "]
let two = "two " :: one
let three = "three " :: two
let rightWayRound = List.rev three
let printList l =
List.iter print_string l
print_newline()
let main() =
printList one
printList two
printList three
printList rightWayRound
main()
The results of this example, when compiled and executed, are as follows:
one
two one
three two one
one two three
The regular way to work with F# lists is to use recursion. The empty list is the base case, and when a function working on a list receives the empty list, the function terminates; when the function receives a nonempty list, it processes the first item in the list (the head) and then recursively processes the remainder of the list (the tail). The next example demonstrates processing a list recursively:
#light
let listOfList = [[2; 3; 5]; [7; 11; 13]; [17; 19; 23; 29]]
let rec concatList l =
if List.nonempty l then
let head = List.hd l in
let tail = List.tl l in
head @ (concatList tail)
else
[]
let primes = concatList listOfList
print_any primes
First, you define an F# list composed of three other lists. Then, you define a recursive function, concatList, which is designed to merge a list of lists into one list. The function uses an F# library function, List.nonempty, to check whether the F# list is empty. If it is not empty, the function takes the head and tail of the list, passes the tail to a call to itself, and then concatenates the head of the list to the result. If the tail is empty, the function must still return something, so it simply returns the empty list, [], because concatenating the empty list with another list has no effect on the contents of the list.
The results of this example, when compiled and executed, are as follows:
[2; 3; 5; 7; 11; 13; 17; 19; 23; 29]
The concatList function is fairly verbose for what this example is trying to achieve. Fortunately, F# includes some pattern matching syntax for lists that can really help tidy this up. I cover this syntax later in this chapter in "Pattern Matching."
All the examples in this section demonstrate another nice feature of F# lists, the set of library functions provided for lists. The List.iter function is a library function that takes two arguments. The first argument is a function that will be applied to each item in the list, and the second is the list to which that function will be applied. You can think of the List.iter function as just a nice shorthand way to write a for loop over a list, and the library contains many other functions for transforming and manipulating lists, including a List.concat function that has a similar effect to the concatList function defined earlier. For more information about these functions, see Chapter 7, which covers the F# ML compatibility library.
List Comprehensions
List comprehensions make creating and converting collections easy. You can create F# lists, sequences, and arrays directly using comprehension syntax. (I cover arrays in more detail in the next chapter, and sequences are collections of type seq, which is F#'s name for the .NET BCL's IEnumerable type; I describe them in the section "Lazy Evaluation.")
The simplest comprehensions specify ranges, where you write the first item you want, either a number or a letter, followed by two periods (..) and then the last item you want, all within square brackets (to create a list) or braces (to create a sequence). The compiler then does the work of calculating all the items in the collection, taking the first number and incrementing it by 1, or similarly with characters, until it reaches the last item specified. The following example demonstrates how to create a list of numbers from 0 through 9 and a sequence of the characters from A through Z:
#light
let numericList = [ 0 .. 9 ]
let alpherSeq = { 'A' .. 'Z' }
printfn "%A" numericList
printfn "%A" alpherSeq
The results of this example are as follows:
[0; 1; 2; 3; 4; 5; 6; 7; 8; 9]
seq ['A'; 'B'; 'C'; 'D'; ...]
To create more interesting collections, you can also specify a step size for incrementing numbers—note that characters do not support this type of list comprehension. You place the step size between the first and last items separated by an extra pair of periods (..). The next example shows a list containing multiples of 3, followed by a list that counts backward from 9 to 0:
#light
let multiplesOfThree = [ 0 .. 3 .. 30 ]
let revNumericSeq = [ 9 .. −1 .. 0 ]
printfn "%A" multiplesOfThree
printfn "%A" revNumericSeq
The results of this example are as follows:
[0; 3; 6; 9; 12; 15; 18; 21; 24; 27; 30]
[9; 8; 7; 6; 5; 4; 3; 2; 1; 0]
List comprehensions also allow loops to create a collection from another collection. The idea is that you enumerate the old collection, transform each of its items, and place any generated items in the new collection. To specify such a loop, use the keyword for, followed by an identifier, followed by the keyword in, at the beginning of the list comprehension. In the next example, you create a sequence of the squares of the first ten positive integers. You use for to enumerate the collection 1 .. 10, assigning each item in turn to the identifier x. You then use the identifier x to calculate the new item, in this case multiplying x by itself to square it.
#light
let squares =
{ for x in 1 .. 10 -> x * x }
print_any squares
The results of this example are as follows:
seq [1; 4; 9; 16; ...]
You can also add a when guard to suppress items you don't want in the collection. A when guard is the keyword when followed by a Boolean expression. Only when the when guard evaluates to true will an item be placed in the collection. The next example demonstrates how to use a when guard, checking whether the modulus of x is zero. This is an easy way to check whether a number is even, and only if the number is even is it placed in the collection. The example also demonstrates how to create a function that returns a sequence based on a list comprehension. In the function evens, the parameter n specifies the size of the collection to be generated.
#light
let evens n =
{ for x in 1 .. n when x % 2 = 0 -> x }
print_any (evens 10)
The results of this example are as follows:
seq [2; 4; 6; 8; ...]
It's also possible to use list comprehensions to iterate in two or more dimensions by using a separate loop for each dimension. In the next example, you define a function, squarePoints, that creates a sequence of points forming a square grid, each point represented by a tuple of two integers.
#light
let squarePoints n =
{ for x in 1 .. n
for y in 1 .. n -> x,y }
print_any (squarePoints 3)
The results of this example are as follows:
[(1, 1); (1, 2); (1, 3); (2, 1); ...]
You'll look at using comprehensions with arrays and collections from the .NET Framework BCL in Chapter 4.
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. You can see the strong notion of control flow in the following 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.
#light
let result =
if System.DateTime.Now.Second % 2 = 0 then
"heads"
else
"tails"
print_string 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 were to replace 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); the next example shows how to do this. It prints either "heads" or false to the console.
#light
let result =
if System.DateTime.Now.Second % 2 = 0 then
box "heads"
else
box false
print_any result
Imperative programmers may be surprised that an if … then … else … expression must have an else if the expression returns a value. This is pretty logical when you think about it and if 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. There is a way for a program to contain an if … then expression without the else, but this is very much in the style of imperative programming, so I discuss it in Chapter 4.
Types and Type Inference
F# is a strongly typed language, which means you cannot use a function with a value that is inappropriate. You cannot call a function that has a string as a parameter with an integer argument; you must explicitly convert between the two. The way the language treats the type of its values is referred to as its type system. F# has a type system that does not get in the way of routine programming. In F#, all values have a type, and this includes values that are functions.
Ordinarily, you don't need to explicitly declare types; the compiler will work out the type of a value from the types of the literals in the function and the resulting types of other functions it calls. If everything is OK, the compiler will keep the types to itself; only if there is a type mismatch will the compiler inform you by reporting a compile error. This process is generally referred to as type inference. If you want to know more about the types in a program, you can make the compiler display all inferred types with the -i switch. Visual Studio users get tooltips that show types when they hover the mouse pointer over an identifier.
The way type inference works in F# is fairly easy to understand. The compiler works through the program assigning types to identifiers as they are defined, starting with the top leftmost identifier and working its way down to the bottom rightmost. It assigns types based on the types it already knows, that is, the types of literals and (more commonly) the types of functions defined in other source files or assemblies.
The next example defines two F# identifiers and then shows their inferred types displayed on the console with the F# compiler's -i switch. The types of these two identifiers are unsurprising, string and int, respectively, and the syntax used by the compiler to describe them is fairly straightforward: the keyword val (meaning "value") and then the identifier, a colon, and finally the type.
#light
let aString = "Spring time in Paris"
let anInt = 42
val aString : string
val anInt : int
The definition of the function makeMessage in the next example is a little more interesting. You should note two things about makeMessage. First, its definition is prefixed with the keyword val, just like the two values you saw before, since even though it is a function, the F# compiler still considers it to be a value. Second, the type itself uses the notation int -> string, meaning a function that takes an integer and returns a string. The -> between the type names (an ASCII arrow, or just arrow) represents the transformation of the function being applied. It is worth noting that the arrow represents a transformation of the value but not necessarily the type, because it can represent a function that transforms a value into a value of the same type, as shown in the half function on the second line.
#light
let makeMessage x = (string_of_int x) + " days to spring time"
let half x = x / 2val makeMessage : int -> string
val half : int -> int
The types of functions that can be partially applied and functions that take tuples differ. See the section "Values and Functions" earlier in the chapter for an explanation of the difference between these types of functions. The functions div1 and div2 are designed to illustrate this. The function div1 can be partially applied, and its type is int -> int -> int, representing that the arguments can be passed in separately. You can compare this to the function div2 that has the type int * int -> int, meaning a function that takes a pair of integers, a tuple of integers, and turns them into a single integer. You can see this in the function div_remainder, which performs integer division and also returns the remainder at the same time. Its type is int -> int -> int * int, meaning a curried function that returns an integer tuple.
let div1 x y = x / y
let div2 (x, y) = x / y
let divRemainder x y = x / y, x % yval div1 : int -> int -> int
val div2 : int * int -> int
val divRemainder : int -> int -> int * int
The next function, doNothing, looks inconspicuous enough, but it is quite interesting from a typing point of view. It has the type 'a -> 'a, meaning a function that takes a value of one type and returns a value of the same type. Any type that begins with a single quotation mark (') means a variable type. F# has a type, obj, that maps to System.Object and that represents a value of any type, a concept that you will probably be familiar with from other common language runtime (CLR)–based programming languages (and indeed many languages that do not target the CLR). However, a variable type is not the same. Notice how the type has an 'a on both sides of the arrow. This means the compiler knows that even though it does not yet know the type, it knows that the type of the return value will be the same as the type of the argument. This feature of the type system, sometimes referred to as type parameterization, allows the compiler to find more type errors at compile time and can help avoid casting.
let doNothing x = xval doNothing : 'a -> 'a
Note The concept of a variable type, or type parameterization, is closely related to the concept of generics that were introduced in the CLR version 2.0 and have now become part of the EMCA specification for the CLI version 2.0. When F# targets a CLI that has generics enabled, it takes full advantage of them by using them anywhere it finds an undetermined type. It is also worth noting that Don Syme, the creator of F#, designed and implemented generics in the .NET CLR before he started working on F#. One might be temped to infer that he did this so he could create F#!
The function doNothingToAnInt, shown next, is an example of a value being constrained, a type constraint; in this case, the function parameter x is constrained to be an int. The syntax for constraining a value to be of a certain type is straightforward. Within parentheses, the identifier name is followed by a colon (:) followed by the type name; this is also sometimes called a type annotation. Constraining values is not usually necessary when writing pure F#, though it can occasionally be useful. It's most useful when using .NET libraries written in languages other than F# and for interoperation with unmanaged libraries. In both these cases, the compiler has less type information, so it is often necessary to give it enough information to disambiguate things. It is possible to constrain any identifier, not just function parameters, to be of a certain type, though it is more typical to have to constrain parameters. The list stringList here shows how to constrain an identifier that's not a function parameter:
let doNothingToAnInt (x : int) = x
let intList = [1; 2; 3]
let (stringList : list<string>) = ["one"; "two"; "three"]val doNothingToAnInt _int : int -> int
val intList : int list
val stringList : string list
The intList value is a list of integers, and the identifier's type is int list. This indicates that the compiler has recognized that the list contains only integers and that in this case the type of its items is not undetermined but is int. Any attempt to add anything other than values of type int to the list will result in a compile error. The identifier stringList has a type annotation. Although this is unnecessary, since the compiler can resolve the type from the value, it is used to show an alternative syntax for working with undermined types. You can place the type between angle brackets after the type that it is associated with instead of just writing it before the type name. Note that even though the type of stringList is constrained to be list<string> (a list of strings), the compiler still reports its type as string list when displaying the type, and they mean exactly the same thing. This syntax is supported to make F# types with a type parameter look like generic types from other .NET libraries.
Pattern Matching
Pattern matching allows you to look at the value of an identifier and then make different computations depending on its value. It is a bit like a chain of if … then … else … expressions and also might be compared to the switch statement in C++ and C#, but it is much more powerful and flexible than either.
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 including its exception handling syntax, which I discuss in "Exceptions and Exception Handling" later in this chapter. The simplest form of pattern matching is matching over a value, and you have already seen this earlier in this chapter in the section "Values and Functions," where you used it 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.
#light
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)
printfn "(luc 2) = %i" (luc 2)
printfn "(luc 6) = %i" (luc 6)
printfn "(luc 11) = %i" (luc 11)
printfn "(luc 12) = %i" (luc 12)
The results of this example, when compiled and executed, are as follows:
(luc 2) = 3
(luc 6) = 18
(luc 11) = 199
(luc 12) = 322
This syntax for pattern matching is the keyword match followed by the identifier that will be matched and then the keyword with. This is followed by all the possible matching rules separated by vertical bars (|). In the simplest case, a rule consists of either a constant or an identifier, followed by an arrow (->) and then by the expression to be used when the value matches the rule. In this definition of the function luc, you can see that the second two cases are literals, the values 1 and 2, and these will just 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 of the example) to give exact control about 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. 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.
#light
let booleanToString x =
match x with false -> "False" | _ -> "True"
Another useful feature of pattern matching is that you can combine two patterns into one rule through the use of the vertical bar (|). The next example, stringToBoolean, demonstrates this. In the first two rules, you have two strings that you would like to have evaluate to the same value, so rather than having two separate rules, you can just use | between the two patterns.
#light
let stringToBoolean x =
match x with
| "True" | "true" -> false
| "False" | "false" -> true
| _ -> failwith "unexpected input"
printfn "(booleanToString true) = %s"
(booleanToString true)
printfn "(booleanToString false) = %s"
(booleanToString false)
printfn "(stringToBoolean "True") = %b"
(stringToBoolean "True")
printfn "(stringToBoolean "false") = %b"
(stringToBoolean "false")
printfn "(stringToBoolean "Hello") = %b"
(stringToBoolean "Hello")
The results of these examples, when compiled and executed, are as follows:
(booleanToString true) = True
(booleanToString false) = False
(stringToBoolean "True") = false
(stringToBoolean "false") = true
(stringToBoolean "Hello") = Microsoft.FSharp.FailureException: unexpected input
at Prog.stringToBoolean(String x)
at Prog._main()
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.
#light
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, and they 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. In these rules, you match parts of the tuples with constants, but you could have used identifiers if you wanted 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 have 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 have been replaced with an identifier if you wanted to work with the value in the second half of the rule definition.
printfn "(myOr true false) = %b" (myOr true false)
printfn "(myOr false false) = %b" (myOr false false)
printfn "(myAnd (true, false)) = %b" (myAnd (true, false))
printfn "(myAnd (true, true)) = %b" (myAnd (true, true))
The results of these examples, when compiled and executed, are as follows:
(myOr true false) = true
(myOr false false) = false
(myAnd (true, false)) = false
(myAnd (true, true)) = true
A common use of a pattern matching in F# is pattern matching over a list; in fact, this is the preferred way to deal with lists. The next example is a reworking of an example given in earlier in this chapter in the "Lists" section, but this one uses pattern matching instead of if … then … else …. For convenience, the original function definition is shown, renamed to concatListOrg. Comparing the two, it is easy to see that the version that uses pattern matching is about half the number of lines, a much preferable implementation. The pattern 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. You can also pattern match against list constants; you can see this in the second rule of concatList, where you have an empty list.
#light
let listOfList = [[2; 3; 5]; [7; 11; 13]; [17; 19; 23; 29]]
let rec concatList l =
match l with
| head :: tail -> head @ (concatList tail)
| [] -> []
let rec concatListOrg l =
if List.nonempty l then
let head = List.hd l in
let tail = List.tl l in
head @ (concatListOrg tail)
else
[]
let primes = concatList listOfList
print_any primes
The results of this example, when compiled and executed, are as follows:
[2; 3; 5; 7; 11; 13; 17; 19; 23; 29]
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. The first rule demonstrates how to match a list of a fixed length, in this case a list of three items, and here you use identifiers 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/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.
#light
let rec findSequence l =
match l with
| [x; y; z] ->
printfn "Last 3 numbers in the list were %i %i %i"
x y z
| 1 :: 2 :: 3 :: tail ->
printfn "Found sequence 1, 2, 3 within the list"
findSequence tail
| head :: tail -> findSequence tail
| [] -> ()
let testSequence = [1; 2; 3; 4; 5; 6; 7; 8; 9; 8; 7; 6; 5; 4; 3; 2; 1]
findSequence testSequence
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
Because pattern matching is such a common task in F#, the language provides an 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.
#light
let rec conactStringList =
function head :: tail -> head + conactStringList tail
| [] -> ""
let jabber = ["'Twas "; "brillig, "; "and "; "the "; "slithy "; "toves "; "..."]
let completJabber = conactStringList jabber
print_endline completJabber
The results of this example, when compiled and executed, are as follows:
'Twas brillig, and the slithy toves ...
Pattern matching has a couple of other uses within F#, but I have not yet covered in detail the types on which these other kinds of pattern matching are based. You can find further details on pattern matching with record types and union types in the next section, "Defining Types." You can find details of pattern matching and exception handling in the section "Exceptions and Exception Handling," and you can find details of how to pattern match over types from non-F# libraries in Chapter 3.
Defining Types
The type system in F# provides a number of features for defining custom types. All of F#'s type definitions fall into two categories. The first category is types that are tuples or records. These are a set of types composed to form a composite type (similar to structs in C or classes in C#). The second category is sum types, sometimes referred to as union types.
Tuples are a way of quickly and conveniently composing values into a group of values. Values are separated by commas and can then be referred to by one identifier, as shown in the first line of the next example. You can then retrieve the values by doing the reverse, as shown in the second and third lines, where identifiers separated by commas appear on the left side of the equals sign, with each identifier receiving a single value from the tuple. If you want to ignore a value in the tuple, you can use _ to tell the compiler you are not interested in the value, as in the second and third lines.
#light
let pair = true, false
let b1, _ = pair
let _, b2 = pair
Tuples are different from most user-defined types in F# because you do not have to explicitly declare them using the type keyword. To define a type, you use the type keyword followed by the type name, an equals sign, and then the type you are defining. In its simplest form, you can use this to give an alias to any existing type, including tuples. Giving aliases to single types is not often useful, but giving aliases to tuples can be very useful, especially when you want to use a tuple as a type constraint. The next example shows how to give an alias to a single type and a tuple and also how to use an alias as a type constraint:
#light
type Name = string
type Fullname = string * string
let fullNameToSting (x : Fullname) =
let first, second = x in
first + " " + second
Record types are similar to tuples in that they compose multiple types into a single type. The difference is that in record types each field is named. The next example illustrates the syntax for defining record types. You place field definitions between braces and separate them with semicolons. A field definition is composed of the field name followed by a colon and the field's type. The type definition Organization1 is a record type where the field names are unique. This means you can use a simple syntax to create an instance of this type where there is no need to mention the type name when it is created. To create a record, you place the field names followed by equals signs and the field values between braces ({}), as shown in the Rainbow identifier:
#light
type Organization1 = { boss : string ; lackeys : string list }
let rainbow =
{ boss = "Jeffrey" ;
lackeys = ["Zippy"; "George"; "Bungle"] }
type Organization2 = { chief : string ; underlings : string list }
type Organization3 = { chief : string ; indians : string list }
let thePlayers =
{ new Organization2
with chief = "Peter Quince"
and underlings = ["Francis Flute"; "Robin Starveling";
"Tom Snout"; "Snug"; "Nick Bottom"] }
let wayneManor =
{ new Organization3
with chief = "Batman"
and indians = ["Robin"; "Alfred"] }
F# does not force field names to be unique, so sometimes the compiler cannot infer the type of a field from the field names alone. In this case, you must use the syntax that specifies the type. Again, you place the record definition between braces, but the new keyword, the type name, and the keyword with precede the field definitions. The field definitions themselves remain the same but are separated with the keyword and instead of semicolons. This is illustrated by the types Organization2 and Organization3 and their instances thePlayers and wayneManor. (This syntax is similar to that used for object expressions, which are a way of creating .NET objects in F# and are discussed in Chapter 5.)
Ordinarily the scope of a type definition is from where it is declared forward to the end of the source file in which it is declared. If a type needs to reference a type declared after it, it can do so if they are declared together, in the same block. Types declared in the same block must be declared next to each other, that is, no value definitions in between, and the keyword type is replaced by the keyword and for every type definition after the first one. Types declared in this way are not any different from types declared the regular way. They can reference any other type in the block, and they can even be mutually referential. The next example shows two types, recipe and ingredient, declared in the same block. If they were declared separately, recipe would not be able to reference ingredient because recipe is declared before ingredient; because their declarations are joined with the keyword and, recipe can have a field of type ingredient.
#light
type recipe =
{ recipeName : string ;
ingredients : ingredient list ;
instructions : string }
and ingredient =
{ ingredientName : string ;
quantity : int }
let greenBeansPineNuts =
{ recipeName = "Green Beans & Pine Nuts" ;
ingredients =
[{ ingredientName = "Green beans" ; quantity = 250 };
{ ingredientName = "Pine nuts" ; quantity = 250 };
{ ingredientName = "Feta cheese" ; quantity = 250 };
{ ingredientName = "Olive oil" ; quantity = 10 };
{ ingredientName = "Lemon" ; quantity = 1 }] ;
instructions = "Parboil the green beans for about 7 minutes. Roast the pine
nuts carefully in a frying pan. Drain the beans and place in a salad bowl
with the roasted pine nuts and feta cheese. Coat with the olive oil
and lemon juice and mix well. Serve ASAP." }
let name = greenBeansPineNuts.recipeName
let toBuy =
List.fold_left
(fun acc x ->
acc +
(Printf.sprintf " %s - %i
" x.ingredientName x.quantity) )
"" greenBeansPineNuts.ingredients
let instructions = greenBeansPineNuts.instructions
printf "%s
%s
%s" name toBuy instructions
The results of this example, when compiled and executed, are as follows:
Green Beans & Pine Nuts
Green beans - 250
Pine nuts - 250
Feta cheese - 250
Olive oil - 10
Lemon - 1
Parboil the green beans for about 7 minutes. Roast the pine
nuts carefully in a frying pan. Drain the beans and place in a salad bowl
with the roasted pine nuts and feta cheese. Coat with the olive oil
and lemon juice and mix well. Serve ASAP.
As well as demonstrating two types being declared together, this example also demonstrates how you access fields in records. One advantage that records have over tuples is that accessing their contents is easier. The construct is simply an identifier dot (.) field name, as shown when associating values with the identifiers name, toBuy, and instructions.
Record types can also be pattern matched; that is, you can use pattern matching to match fields within the record type. The findDavid function in the next example does this. As you would expect, the syntax for examining a record using pattern matching is similar to the syntax used to construct it.
You can compare a field to a constant with field = constant. You can assign the values of fields with identifiers with field = identifier. Or, you can ignore a field with field =_. The first rule in the find_david function is the one that does the real work, where you check the her field of the record to see whether it is "Posh", David's wife. The him field is associated with the identifier x so it can be used in the second half of the rule.
#light
type couple = { him : string ; her : string }
let couples =
[ { him = "Brad" ; her = "Angelina" };
{ him = "Becks" ; her = "Posh" };
{ him = "Chris" ; her = "Gwyneth" };
{ him = "Michael" ; her = "Catherine" } ]
let rec findDavid l =
match l with
| { him = x ; her = "Posh" } :: tail -> x
| _ :: tail -> findDavid tail
| [] -> failwith "Couldn't find David"
print_string (findDavid couples)
The results of this example, when compiled and executed, are as follows:
Becks
Field values can also be functions. Since this technique is mainly used in conjunction with mutable state to form values similar to objects, I won't discuss this here but in its own section in Chapter 4.
Union types, sometimes called sum types or discriminated unions, are a way of bringing together data that may have a different meaning or structure. The next example defines a type volume whose values can have three different meanings—liter, U.S. pint, or imperial pint. Although the structure of the data is the same and is represented by a float, the meanings are quite different. Mixing up the meaning of data in an algorithm is a common cause of bugs in programs, and the volume type is in part an attempt to avoid this.
You define a union type using the type keyword, followed by the type name, followed by an equals sign—just as all type definitions. Then comes the definition of the different constructors, separated by vertical bars. The first vertical bar is optional. A constructor is composed of a name that must start with a capital letter; this is to stop the common bug of getting constructor names mixed up with identifier names. The name can optionally be followed by the keyword of and then the types that make up that constructor. Multiple types that make up a constructor are separated by asterisks. The names of constructors within a type must be unique. If several union types are defined, then the names of their constructors can overlap; however, you should be careful when doing this, because it can be that further type annotations are required when constructing and consuming union types.
The following Volume type is a union type with three constructors, each composed of a single item of type float. The syntax for constructing a new instance of a union type is the constructor name followed by the values for the types, with multiple values separated by commas. Optionally, you can place the values in parentheses. You use the three different Volume constructors to construct three different identifiers, vol1, vol2, and vol3.
#light
type Volume =
| Liter of float
| UsPint of float
| ImperialPint of float
let vol1 = Liter 2.5
let vol2 = UsPint 2.5
let vol3 = ImperialPint (2.5)
To deconstruct the values of union types into their basic parts, you always use pattern matching. When pattern matching over a union type, the constructors make up the first half of the pattern matching rules. You don't need a complete list of rules, but if you don't, there must be a default rule, using either an identifier or a wildcard to match all remaining rules. The first part of a rule for a constructor consists of the constructor name followed by identifiers or wildcards to match the various values within it. The following functions, convertVolumeToLiter, convertVolumeUsPint, and convertVolumeImperialPint, demonstrate this syntax:
let convertVolumeToLiter x =
match x with
| Liter x -> x
| UsPint x -> x * 0.473
| ImperialPint x -> x * 0.568
let convertVolumeUsPint x =
match x with
| Liter x -> x * 2.113
| UsPint x -> x
| ImperialPint x -> x * 1.201
let convertVolumeImperialPint x =
match x with
| Liter x -> x * 1.760
| UsPint x -> x * 0.833
| ImperialPint x -> x
let printVolumes x =
printfn "Volume in liters = %f,
in us pints = %f,
in imperial pints = %f"
(convertVolumeToLiter x)
(convertVolumeUsPint x)
(convertVolumeImperialPint x)
printVolumes vol1
printVolumes vol2
printVolumes vol3
The results of these examples, when compiled and executed, are as follows:
Volume in liters = 2.500000,
in us pints = 5.282500,
in imperial pints = 4.400000
Volume in liters = 1.182500,
in us pints = 2.500000,
in imperial pints = 2.082500
Volume in liters = 1.420000,
in us pints = 3.002500,
in imperial pints = 2.500000
Both union and record types can be parameterized. Parameterizing a type means leaving one or more of the types within the type being defined to be determined later by the consumer of the types. This is a similar concept to the variable types discussed earlier in this chapter. When defining types, you must be a little bit more explicit about which types are variable.
F# supports two syntaxes for type parameterization. In the first, you place the type being parameterized between the keyword type and the name of the type, as follows:
#light
type 'a BinaryTree =
| BinaryNode of 'a BinaryTree * 'a BinaryTree
| BinaryValue of 'a
let tree1 =
BinaryNode(
BinaryNode ( BinaryValue 1, BinaryValue 2),
BinaryNode ( BinaryValue 3, BinaryValue 4) )
In the second syntax, you place the types being parameterized in angle brackets after the type name, as follows:
#light
type Tree<'a> =
| Node of Tree<'a> list
| Value of 'a
let tree2 =
Node( [ Node( [Value "one"; Value "two"] ) ;
Node( [Value "three"; Value "four"] ) ] )
Like variable types, the names of type parameters always start with a single quote (') followed by an alphanumeric name for the type. Typically, just a single letter is used. If multiple parameterized types are required, you separate them with commas. You can then use the type parameters throughout the type definition. The previous examples defined two parameterized types, using the two different syntaxes that F# offers. The BinaryTree type used OCaml-style syntax, where the type parameters are placed before the name of the type. The tree type used .NET-style syntax, with the type parameters in angle brackets after the type name.
The syntax for creating and consuming an instance of a parameterized type does not change from that of creating and consuming a nonparameterized type. This is because the compiler will automatically infer the type parameters of the parameterized type. You can see this in the following construction of tree1 and tree2 and their consumption by the functions printBinaryTreeValues and printTreeValues:
let rec printBinaryTreeValues x =
match x with
| BinaryNode (node1, node2) ->
printBinaryTreeValues node1;
printBinaryTreeValues node2
| BinaryValue x -> print_any x; print_string ", "
let rec printTreeValues x =
match x with
| Node l -> List.iter printTreeValues l
| Value x ->
print_any x
print_string ", "
printBinaryTreeValues tree1
print_newline()
printTreeValues tree2
The results of this example, when compiled and executed, are as follows:
1, 2, 3, 4,
"one", "two", "three", "four",
You may have noticed that although I've discussed defining types, creating instances of them, and examining these instances, I haven't discussed updating them. This is because it is not possible to update these kinds of types because the idea of a value that changes over time goes against the idea of functional programming. However, F# does have some types that are updatable, and I discuss them in Chapter 4.
Exceptions and Exception Handling
Exception definitions in F# are similar to defining a constructor of a union type, and the syntax for handling exceptions is similar to pattern matching.
You define exceptions using the exception keyword followed by the name of the exception and then optionally the keyword of and the types of any values the exception should contain, with multiple types separated by asterisks. The next example shows the definition of an exception, WrongSecond, which contains one integer value:
exception WrongSecond of int
You can raise exceptions with the raise keyword, as shown in the else clause in the following testSecond function. F# also has an alterative to the raise keyword, the failwith function, as shown in the following if clause. If, as is commonly the case, you just want to raise an exception with a text description of what went wrong, you can use failwith to raise a generic exception that contains the text passed to the function.
let primes =
[ 2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59 ]
let testSecond() =
try
let currentSecond = System.DateTime.Now.Second in
if List.exists (fun x -> x = currentSecond) primes then
failwith "A prime second"
else
raise (WrongSecond currentSecond)
with
WrongSecond x ->
printf "The current was %i, which is not prime" x
testSecond()
As shown in testSecond, the try and with keywords handle exceptions. The expressions that are subject to error handling go between the try and with keywords, and one or more pattern matching rules must follow the with keyword. When trying to match an F# exception, the syntax follows that of trying to match an F# constructor from a union type. The first half of the rule consists of the exception name, followed by identifiers or wildcards to match values that the exception contains. The second half of the rule is an expression that states how the exception should be handled. One major difference between this and the regular pattern matching constructs is that no warning or error is issued if pattern matching is incomplete. This is because any exceptions that are unhandled will propagate until they reach the top level and stop execution. The example handles exception wrongSecond, while leaving the exception raised by failwith to propagate.
F# also supports a finally keyword, which is used with the try keyword. You can use the finally keyword in conjunction with the with keyword as well as some rules for error handling or no rules. Always place the finally expression after the with block, if it exists; the finally expression will be executed whether an exception is thrown. The next example shows a finally block being used to ensure a file is closed and disposed of after it is written to:
#light
let writeToFile() =
let file = System.IO.File.CreateText("test.txt") in
try
file.WriteLine("Hello F# users")
finally
file.Dispose()
writeToFile()Caution Programmers coming from an OCaml background should be careful when using exceptions in F#. Because of the architecture of the CLR, throwing an exception is pretty expensive—quite a bit more expensive than in OCaml. If you throw lots of exceptions, profile your code carefully to decide whether the performance costs are worth it. If the costs are too high, revise the code appropriately. I discuss tools for profiling F# applications in Chapter 12.
Lazy Evaluation
Lazy evaluation is something that goes hand in hand with functional programming. The theory is that if there are no side effects in the language, the compiler or runtime is free to choose the evaluation order of expressions. As you know, F# allows functions to have side effects, so it's not possible for the compiler or runtime to have a free hand in function evaluation; therefore, F# is said to have a strict evaluation order or be a strict language. You can still take advantage of lazy evaluation but must be explicit about which computations can be delayed, that is, evaluated in a lazy manner. You use the keyword lazy to delay a computation, that is, invoke lazy evaluation. The computation within the lazy expression remains unevaluated until evaluation; it is explicitly forced with the force function from the Lazy module. When the force function is applied to a particular lazy expression, the value is computed; then the result is cached, and subsequent calls to the force function return the cached value, whatever it is, even if this means raising an exception. The following code shows a simple use of lazy evaluation:
#light
let lazyValue = lazy ( 2 + 2 )
let actualValue = Lazy.force lazyValue
print_int actualValue
print_newline()
On the first line, you delay a simple expression for evaluation later. The next line forces evaluation. Then you print the value. The value has been cached, so any side effects that take place when the value is computed will occur only the first time the lazy value is forced. This is fairly easy to demonstrate. In the next example, you create a lazy value that has a side effect when it is calculated: it writes to the console. To show that this side effect takes place only once, you force the value twice, and it is plain to see from the result that writing to the console takes place only once.
#light
let lazySideEffect =
lazy
( let temp = 2 + 2
print_int temp
print_newline()
temp )
print_endline "Force value the first time: "
let actualValue1 = Lazy.force lazySideEffect
print_endline "Force value the second time: "
let actualValue2 = Lazy.force lazySideEffect
The results of this example are as follows:
Force value the first time:
4
Force value the second time:
Laziness can also be useful when working with collections. The idea of a lazy collection is that elements in the collection are calculated on demand. Some collection types also cache the results of these calculations, so there is no need to recalculate elements. F# provides the LazyList collection type, which caches computed results and is useful for functional programming and search. The second lazy collection is the seq type, a shorthand for the BCL's IEnumerable type. This plays a similar role to LazyList but does not cache computed results. LazyList and seq values are created and manipulated using functions in the LazyList and Seq modules, respectively. Many other values are also compatible with the type seq; for example, all F# lists and arrays are compatible with this type, as are most other collection types.
The next example shows how to use the LazyList module. Possibly its most important function, and probably the most difficult to understand, is unfold. This function allows you to create a lazy list. What makes it complicated is that you must provide a function that will be repeatedly evaluated to provide the elements of the list. The function passed to LazyList.unfold can take any type of parameter and must return an option type. An option type is a union type that can be either None or Some(x), where x is a value of any type. None is used to represent the end of a list. The Some constructor must contain a tuple. The first item in the tuple represents the value that will become the first value in the list. The second value in the tuple is the value that will be passed into the function the next time it is called. You can think of this value as an accumulator.
The next example shows how this works. The identifier lazyList will contain three values. If the value passed into the function is less than 13, you append the list using this value to form the list element and then add 1 to the value passed to the list. This will be value passed to the function the next time it is called. If the value is greater than or equal to 13, you terminate the list by returning None. To display the list, you use the function display, a simple recursive function that processes the head of the list and then recursively processes the tail.
#light
let lazyList =
LazyList.unfold
(fun x ->
if x < 13 then
Some(x, x + 1)
else
None)
10
let rec display l =
match l with
| LazyList.Cons(h,t) ->
print_int h
print_newline ()
display t
| LazyList.Nil ->
()
display lazyList
The results of this example, when compiled and executed, are as follows:
10
11
12
Lazy lists are also useful to represent lists that don't terminate. A nonterminating list can't be represented by a classic list, which is constrained by the amount of memory available. The next example demonstrates this by creating fibs, an infinite list of all the Fibonacci numbers; it uses the Seq module, although it could just as well have used the LazyList module because the unfold function works in the same way in both. To display the results conveniently, you use the function Seq.take to turn the first 20 items into an F# list, but you carry on calculating many more Fibonacci numbers as you use F# bigint integers, so you are limited by the size of a 32-bit integer.
#light
let fibs =
Seq.unfold
(fun (n0, n1) ->
Some(n0, (n1, n0 + n1)))
(1I,1I)
let first20 = Seq.take 20 fibs
print_any first20
The results of this example are as follows:
[1I; 1I; 2I; 3I; 5I; 8I; 13I; 21I; 34I; 55I; 89I; 144I; 233I; 377I; 610I; 987I;
1597I; 2584I; 4181I; 6765I]
These examples are too simple to really demonstrate the power of lazy evaluation. You'll look at lazy evaluation again in several places in this book, notably in Chapter 7, where you'll see how to use lazy evaluation in user-interface programming to make user interfaces more responsive by ensuring computations do not happen until really needed.
Summary
In this chapter, you looked at the major functional programming constructs in F#. This is the core of the language, and I hope you've developed a good feel for how to approach writing algorithms and handling data in F#. The next chapter will cover imperative programming, and you'll see how to mix functional and imperative programming techniques to handle tasks such as input/output (I/O).