Table 3-1 lists the basic numeric types used in F# code and their corresponding literal forms. The table also lists the non-numeric types bool and unit.

Table 3-2 lists the most commonly used arithmetic operators. These are overloaded to work with all the numeric types listed in Table 3-1.

The behavior of these and other operators can be extended for user-defined types, a topic covered in Chapter 6. In F#, addition, subtraction, and multiplication over integers are unchecked; that is, if overflow or underflow occurs beyond the representable range, then wraparound occurs. For example, 2147483647 is the largest representable 32-bit integer of the int type:

> 2147483647+1;;
val it : int = −2147483648

You can access checked versions of arithmetic operators that raise System.OverflowException exceptions by opening the Microsoft.FSharp.Core.Operators.Checked module. If avoiding overflow is a priority, then using the decimal, bigint, and bignum types is recommended. Division by zero raises a System.DivideByZeroException exception, except in the case of floating-point numbers, where it returns one of the special floating-point numbers Infinity and -Infinity. Operator overloading interacts with type inference—if a use of an overloaded operator isn't otherwise constrained to work on a particular type, then F# assumes it works on 32-bit integers.

To constrain a use of an operator to a particular type, you must give a type annotation that has the effect of telling the compiler the type on the left of the two arguments to the binary operator. For example, in the absence of additional type information, the following function is assumed to work with integers:

> let squareAndAdd a b = a * a + b;;
val squareAndAdd : int -> int -> int

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

> let squareAndAdd (a:float) b = a * a + b;;
val squareAndAdd : float -> float -> float

If you want, you can also give full type annotations for the arguments and return type of a function:

> let squareAndAdd (a:float) (b:float) : float = a * a + b;;
val squareAndAdd : float -> float -> float

All the integer types listed in Table 3-1 support bitwise manipulations on their underlying representations. Table 3-3 shows the bitwise manipulation operators.

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

let encode (n: int32) =
    if   (n >= 0    && n <= 0x7F)   then [ n ]
    elif (n >= 0x80 && n <= 0x3FFF) then [ (0x80 ||| (n >>> 8)) &&& 0xFF;
                                           (n &&& 0xFF) ]
    else  [ 0xC0; ((n >>> 24) &&& 0xFF);
                  ((n >>> 16) &&& 0xFF);
                  ((n >>> 8)  &&& 0xFF);
                   (n         &&& 0xFF) ]

Here's an example of the function in action:

> encode 32;;
val it : int32 list = [32]

> encode 320;;
val it : int32 list = [129; 64]

> encode 32000;;
val it : int32 list = [192; 0; 0; 125; 0]

Numeric types aren't implicitly converted—conversions between different numeric types must be made explicitly. You do this by using overloaded conversion operators. These work the same way as overloaded infix operators such as + and *. Table 3-4 shows the primary conversion operators.

These conversions are all unchecked in the sense that they won't raise exceptions. Again, the Microsoft.FSharp.Core.Operators.Checked module has corresponding definitions of these operators. An alternative is to use the .NET static methods contained in the type System.Convert, such as System.Convert.ToDouble( ). These do perform checking, which means they raise an exception if the source number can't be represented within the numeric range of the target type. As with many .NET constructs, uses of System.Convert methods may require type annotations to resolve overloading, discussed further in Chapters 5 and 6.

When used with numeric values, the binary comparison operators =, <>, <, <=, >, >=, min, and max perform comparisons according to the natural ordering for each particular numeric type. You can also use these operators on other data types, such as to compare lists of integers, and you can customize their behavior for new types you define. Chapter 5 discusses generic comparison in detail, and Chapter 8 discusses customizing generic comparison.

When used with floating-point values, these operators implement the IEEE semantics for NaN (Not a Number) values. For example, (NaN = NaN) is false, as are (NaN <= NaN) and (NaN < NaN).

The module Microsoft.FSharp.Core.Operators includes the definition of a number of useful overloaded math operators. These are shown in Table 3-5 and are overloaded either on a suitable range of integer types or on the basic floating-point types.

Table 3-6 shows the different forms for writing string literals.

Table 3-7 shows the escape characters you can use in strings and characters.

As shown in Table 3-6, a literal form is also available for arrays of bytes: the characters are interpreted as ASCII characters, and non-ASCII characters can be embedded using escape codes. This can be useful when you're working with binary protocols:

> "MAGIC"B;;
val it : byte [] = [|77uy; 65uy; 71uy; 73uy; 67uy|]

Verbatim string literals are particularly useful for file and path names that contain the backslash character ():

> let dir  = @"c:Program Files";;
val dir : string

You can also use multiline string literals:

> let s = "All the kings horses
- and all the kings men";;
val s : string

The operator .[] is used to access the elements of a string, and the property Length retrieves its length:

> let s = "Couldn't put Humpty";;
val s : string

> s.Length;;
val it : int = 19

> s.[13];;
val it : char = 'H'

The operator .[index..index] can be used to take substrings:

> let s = "Couldn't put Humpty";;
val s : string

> s.[13..16];;
val it : string = "Hump"

Strings are immutable; that is, a string value can't be modified after it's built. For example, the Substring method on the string type doesn't modify the original string but returns a new string representing the result. As mentioned in Chapter 2, immutability is a key concept for many F# values, and you encounter it many places in this book. If you attempt to mutate a string, you get an error like the one shown here:

> let s = "Couldn't put Humpty";;
val s : string = "Couldn't put Humpty"

> s.[13] <- 'h';;

  s.[13] <- 'h';;
  ^^
stdin(75,0): error: FS0001: Type error in the use of the overloaded operator
'set_Item'. The type 'string' does not support any operators named 'set_Item'

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

> "Couldn't put Humpty" + " " + "together again";;
val it : string = "Couldn't put Humpty together again"

You can also build strings using objects of the .NET type System.Text.StringBuilder. These objects are mutable buffers that you can use to accumulate and modify text, and they're more efficient than repeated uses of the + operator. Here's an example:

> let buf = new System.Text.StringBuilder();;
val buf : System.Text.StringBuilder

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

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

> buf.ToString();;
val it : string = "Humpty Dumpty sat on the wall"

F# lists are a common data structure used in functional programming. You saw some examples of concrete lists in Chapter 2. Table 3-8 shows the primitive constructs for building lists.

Here are some basic list values:

let oddPrimes = [3; 5; 7; 11]
let morePrimes = [13; 17]
let primes = 2 :: (oddPrimes @ morePrimes)

The value and type of primes are as follows:

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

Lists are immutable: the cons :: and append @ operations don't modify the original lists; instead, they create new lists. You can see this in the following interactive session:

> let people = [ "Adam"; "Dominic"; "James" ];;
val people : string list

> people;;
val it : string list = [ "Adam"; "Dominic"; "James" ]

> "Chris" :: people;;
val it : string list = [ "Chris"; "Adam"; "Dominic"; "James" ]

> people;;
val it : string list = [ "Adam"; "Dominic"; "James" ]

Note that people has not been changed by the construction of a new list using the cons operator. F# lists are represented in memory as linked lists; each F# list value is a cons cell containing a value plus a pointer to the next chain in the list, or else it's a special nil object. When you create a new list using the :: operator, then the tail of the new list points to the old list, which ensures that the inner memory associated with lists is often reused as part of multiple list values.

You can decompose lists from the head downward by using pattern matching. You saw some simple examples of pattern matching on tuples in Chapter 2, and we look at pattern matching in more detail in "Getting Started with Pattern Matching" later in this chapter. Here is an example of using pattern matching with lists:

let printFirst primes =
    match primes with
    | h :: t -> printfn "The first prime in the list is %d" h
    | [] -> printfn "No primes found in the list"

> printFirst oddPrimes;;
The first prime in the list is 3
val it : unit = ()

The first line after the match is a pattern-matching rule that matches the input primes against the pattern h :: t. If primes is a nonempty list, then the match is successful, and the first printfn is executed with h bound to the head of the list and t to its tail. The second line considers the case where primes is an empty list. Note that the :: and [] symbols can be used both to build up lists in expressions and to decompose them in pattern matching. The F# library also includes a module List that contains some useful functions related to programming with lists. You see many of these functions in the next section and throughout this book. Table 3-9 shows some of them.

F# lists aren't appropriate for all circumstances; for example, very large data structures should probably be represented using arrays or other data structures or even managed by an external tool such as a relational database. We discuss a number of immutable data structures in the "Some Common Immutable Data Structures" sidebar.

Here are examples of how to use some of the functions from Table 3-9. The last two examples use function values, which we cover in more detail in "Introducing Function Values" later in this chapter.

> List.head [5; 4; 3];;
val it : int = 5

> List.tail [5; 4; 3];;
val it : int list = [ 4; 3 ]

> List.map (fun x -> x*x) [1; 2; 3];;
val it : int list = [ 1; 4; 9 ]

> List.filter (fun x -> x % 3 = 0) [2; 3; 5; 7; 9];;
val it : int list = [ 3; 9 ]

Like lists and tuples, option values are simple constructs frequently used as workhorses in F# coding. An option is simply either a value Some(v) or the absence of a value None. For example, options are useful for returning the value of a search where you may or may not have a result. You see in the section "Defining Discriminated Unions" that the option type is defined in the F# library as follows:

type 'T option =
    | None
    | Some of 'T

The following is a data structure that uses options to represent the (optional) parents of some well-known characters:

> let people = [ ("Adam", None);
                 ("Eve" , None);
                 ("Cain", Some("Adam","Eve"));
                 ("Abel", Some("Adam","Eve")) ];;
val people : (string * (string *string) option) list

Pattern matching is frequently used to examine option values:

> let showParents (name,parents) =
      match parents with
      | Some(dad,mum) -> printfn "%s has father %s, mother %s" name dad mum
      | None          -> printfn "%s has no parents!" name;;
val showParents : (string * (string * string) option) -> unit

> showParents ("Adam",None);;
Adam has no parents
val it : unit = ()

The F# library also includes a module Option that contains useful functions for programming with options. Table 3-10 shows some of these. Although it's easy to code them by hand using pattern matching, it can also be useful to learn and rely on the standard definitions.

You can use option values for both data and control; they're often used to represent the success or failure of a computation. This can be useful when you're catching an exception, as shown in the following example (which uses the function http from Chapter 2):

let fetch url =
    try Some (http url)
    with :? System.Net.WebException -> None

Chapter 4 describes exceptions in more detail—what matters here is that if a network error occurs during the HTTP request, the exception is caught, and the result of the fetch function is the value None. Successful web page requests return a Some value. Option values can then be discriminated and decomposed using pattern matching, as shown here:

> match (fetch "http://www.nature.com") with
  | Some text -> printfn "text = %s" text
  | None -> printfn "**** no web page found";;
text = <HTML> ... </HTML>  (note: the HTML is shown here if connected to the web)
val it : unit = ()

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

let round x =
    if x >= 100 then 100
    elif x < 0 then 0
    else x

Conditionals are really shorthand for pattern matching; for example, the previous code could be written like this:

let round x =
    match x with
    | _ when x >= 100 -> 100
    | _ when x < 0    -> 0
    | _               -> x

Conditionals are always guarded by a Boolean-valued expression. You can build them using && and || (the "and" and "or" operators) as well as any library functions that return Boolean values:

let round2 (x, y) =
    if x >= 100 || y >= 100 then 100,100
    elif x < 0 || y < 0 then 0,0
    else x,y

The operators && and || have the usual short-circuit behavior in that the second argument of && is evaluated only if the first evaluates to true, and likewise, the second argument of || is evaluated only if the first evaluates to false.

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

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

> let primeCubes = List.map (fun n -> n * n * n) primes;;
val primeCubes: int list

> primeCubes;;
val it : int list = [8; 27; 125; 343]

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

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

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

> List.map (fun (_,p) -> String.length p) resultsOfFetch;;
val it : int list = [3932; 2827 ]

Here you see two things:

Functions such as List.map are called aggregate operators, and they're powerful constructs, especially when combined with the other features of F#. Here is a longer example that uses the aggregate operators Array.filter and List.map to count the number of URL links in an HTML page and then collects stats on a group of pages (this sample uses the function http defined in Chapter 2):

let delimiters = [| ' '; '
'; '	'; '<'; '>'; '=' |]
let getWords (s: string) = s.Split delimiters
let getStats site =
    let url = "http://" + site
    let html = http url
    let hwords = html |> getWords
    let hrefs = html |> getWords |> Array.filter (fun s -> s = "href")
    (site,html.Length, hwords.Length, hrefs.Length)

Here, you use the function getStats with three web pages:

> let sites = [ "www.live.com";"www.google.com";"search.yahoo.com" ];;
val sites : string list

> sites |> List.map getStats;;
val it : (string * int * int * int) list
  = [("www.live.com", 7728, 1156, 10);
     ("www.google.com", 2685, 496, 14);
     ("search.yahoo.com", 10715, 1771, 38)]

The function getStats computes the length of the HTML for the given web site, the number of words in the text of that HTML, and the approximate number of links on that page.

The previous code sample extensively uses the |> operator to pipeline operations, discussed in the "Pipelining with |>" sidebar. The F# library design ensures that a common, consistent set of aggregate operations is defined for each structured type. Table 3-11 shows how the same design patterns occur for the map abstraction.

WYou may see types that define methods such as Map that provide a slightly more succinct way of transforming data. For example, this might allow you to write a transformation like so:

site.Map getStats

This may require the use of a type annotation. Both styles are used in F# programming, depending on the methods and properties available for a particular data type.

let (|>) x f = f x

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

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

val (|>) : 'T -> ('T -> 'U) -> 'U

You saw earlier how to use the |> forward pipe operator to pipe values through a number of functions. This was a small example of the process of computing with functions, an essential and powerful programming technique in F#. This section covers ways to compute new function values from existing ones using compositional techniques. First, let's look at function composition. For example, consider the following code:

let google = http "http://www.google.com"
google |> getWords |> List.filter (fun s -> s = "href") |> List.length

You can rewrite this code using function composition as follows:

let countLinks = getWords >> List.filter (fun s -> s = "href") >> List.length
google |> countLinks

You define countLinks as the composition of three function values using the >> forward composition operator. This operator is defined in the F# library as follows:

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

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

val (>>) : ('T -> 'U) -> ('U -> 'c) -> ('T -> 'c)

Note that >> is typically applied to only two arguments: those on either side of the binary operator, here named f and g. The final argument x is typically supplied at a later point.

F# is good at optimizing basic constructions of pipelines and composition sequences from functions—for example, the function countLinks shown earlier becomes a single function calling the three functions in the pipeline in sequence. This means sequences of compositions can be used with relatively low overhead.

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

let shift (dx,dy) (px,py) = (px + dx, py + dy)
let shiftRight = shift (1,0)
let shiftUp    = shift (0,1)
let shiftLeft  = shift (−1,0)
let shiftDown  = shift (0,−1)

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

val shift : int * int -> int * int -> int * int
val shiftRight : int * int -> int * int
val shiftLeft  : int * int -> int * int
val shiftUp    : int * int -> int * int
val shiftDown  : int * int -> int * int

Here is an example of how to use shiftRight and how to apply shift to new arguments (2,2):

> shiftRight (10,10);;
val it : int * int = (11,10)

> List.map (shift (2,2)) [ (0,0); (1,0); (1,1); (0,1) ];;
val it : int * int list = [ (2,2); (3,2); (3,3); (2,3) ]

In the second example, the function shift takes two pairs as arguments. You bind the first parameter to (2, 2). The result of this partial application is a function that takes one remaining tuple parameter and returns the value shifted by two units in each direction. This resulting function can now be used in conjunction with List.map.

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

open System.Drawing;;
let remap (r1: Rectangle) (r2: Rectangle) =
    let scalex = float r2.Width / float r1.Width
    let scaley = float r2.Height / float r1.Height
    let mapx x = int (float r2.Left + truncate (float (x - r1.Left) * scalex))
    let mapy y = int (float r2.Top + truncate (float (y - r1.Top) * scaley))
    let mapp (p: Point) = Point(mapx p.X, mapy p.Y)
    mapp

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

val remap : Rectangle -> Rectangle -> (Point -> Point)

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

> let mapp = remap (Rectangle(100,100,100,100)) (Rectangle(50,50,200,200));;
val mapp : Point -> Point

> mapp (Point(100,100));;
val it : Point = X=50,Y=50

> mapp (Point(150,150));;
val it : Point = X=150,Y=150

> mapp (Point(200,200));;
val it : Point = X=250,Y=250

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

In the previous example, mapx, mapy, and mapp are local functions—functions defined locally as part of the implementation of remap. Local functions can be context dependent; in other words, they can be defined in terms of any values and parameters that happen to be in scope. Here, mapx is defined in terms of scalex, scaley, r1, and r2.

The function remap from the previous section generates values of type Point -> Point. You can think of this type as a way of representing "the family of transformations for the type Point." Many useful concepts can be modeled using function types and values. For example:

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

let sites = [ "http://www.live.com";
              "http://www.google.com";
              "http://search.yahoo.com" ]

sites |> List.iter (fun site -> printfn "%s, length = %d" site (http site).Length)

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

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

Many additional aggregate iteration techniques are defined in the F# and .NET libraries, particularly by using values of type seq<type>, discussed in "Getting Started with Sequences" later in this chapter.

As a second example of how you can abstract control using functions, let's consider the common pattern of timing the execution of an operation (measured in wall-clock time). First, let's explore how to use System.DateTime.Now to get the wall-clock time:

> open System;;
> let start = DateTime.Now;;
val start : DateTime

> http "http://www.newscientist.com";;
val it : string = "<html>...</html>"

> let finish = DateTime.Now;;
val finish : DateTime

> let elapsed = finish - start;;
val elapsed : TimeSpan

> elapsed;;
val it : TimeSpan = 00:00:01.9799671

Note that the type TimeSpan has been inferred from the use of the overloaded operator in the expression finish - start. Chapter 6 discusses overloaded operators in depth. You can now wrap up this technique as a function time that acts as a new control operator:

open System
let time f =
    let start = DateTime.Now
    let res = f()
    let finish = DateTime.Now
    (res, finish - start)

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

val time : (unit -> 'T) -> 'T * TimeSpan

Here 'T is a type variable that stands for any type, and thus the function can be used to time functions that return any kind of result. Note that F# automatically infers a generic type for the function, a technique called automatic generalization that lies at the heart of F# type inference. Chapter 5 discusses automatic generalization in detail. Here is an example of using the time function, which again reuses the http function defined in Chapter 2:

> time (fun () -> http "http://www.newscientist.com");;
val it : string * TimeSpan = ...   (The HTML text and time will be shown here)

You can use existing .NET methods as first-class functions. For example:

> open System.IO;;
> [@"C:Program Files"; @"C:Windows"] |> List.map Directory.GetDirectories;;

val it : string [] list =
  [ [|"C:\Program Files\Adobe"; "C:\Program Files\Apoint";
      "C:\Program Files\CA"; "C:\Program Files\CE Remote Tools"; ...]; ... ]

Sometimes you need to add extra type information to indicate which overload of the method is required. Chapter 6 discusses method overloading in more detail. For example, the following causes an error:

> open System;;
> let f = Console.WriteLine;;

C:misc	est.ml(11,8): error: FS0041: The method WriteLine is overloaded.
Possible matches are shown below. Resolve the overloading by adding further
type annotations to the arguments.

Possible overload: 'Console.WriteLine(bool value) : unit'.

Possible overload: 'Console.WriteLine(char value) : unit'.
...

However, the following succeeds:

> let f = (Console.WriteLine : string -> unit);;
val f : string -> unit

Pattern matching can be used to decompose structured values. Here is an example where you match nested tuple values:

> let highLow a b =
    match (a,b) with
    | ("lo", lo), ("hi", hi) -> (lo,hi)
    | ("hi", hi), ("lo", lo) -> (lo,hi)
    | _ -> failwith "expected a both a high and low value";;

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

> highLow ("hi",300) ("lo",100);;
val it : int * int = (100,300)

The first rule matches if the first parts of the input pairs are the strings "lo" and "hi", respectively. It then returns a pair made from the respective second parts of the tuples. The second rule is the mirror of this in case the values appeared in reverse order.

The final cases of both of the previous examples use wildcard patterns to cover remaining cases. This makes the patterns exhaustive. Frequently, no wildcard is needed to ensure this, because for many input types F# is able to determine whether the given set of rules is sufficient to cover all possibilities for the given shape of data. However, if a match isn't exhaustive, a warning is given:

> let urlFilter3 url agent =
      match url,agent with
      | "http://www.control.org", 86 -> true
      | "http://www.kaos.org", _ -> false;;

  match url,agent with
  ^^^^^^^^^^^^^^^^^^^^
warning: Incomplete pattern matches on this expression. ...

In these cases, it may be necessary to add an extra exception-throwing clause to indicate to the F# compiler that the given inputs aren't expected:

let urlFilter4 url agent =
    match url,agent with
    | "http://www.control.org", 86 -> true
    | "http://www.kaos.org", _ -> false
    | _ -> failwith "unexpected input"

Nonexhaustive matches are automatically augmented by a default case where a MatchFailureException is thrown. Chapter 4 discusses exceptions.

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

> let urlFilter2 url agent =
      match url,agent with
      | "http://www.control.org", _ -> true
      | "http://www.control.org", 86 -> true
      | _ -> false;;

     | "http://www.control.org", 86 -> true
     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
warning: This rule will never be matched.

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

let sign x =
    match x with
    | _ when x < 0 -> −1
    | _ when x > 0 ->  1
    | _ -> 0

You can combine two patterns to represent two possible paths for matching:

let getValue a =
    match a with
    | (("lo" | "low") ,v) -> v
    | ("hi",v) | ("high",v) -> v
    | _ -> failwith "expected a both a high and low value"

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

You can generate simple sequences using range expressions. For integer ranges, these take the form of seq {n .. m} for the integer expressions n and m:

> seq {0 .. 2};;
val it : seq<int> = seq [ 0; 1; 2; ]

You can also specify range expressions using other numeric types, such as double and single:

> seq {-100.0 .. 100.0};;
val it : seq<double> = seq [ −100.0; −99.0; −98.0; ... ]

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

> seq {1I .. 1000000000000I};;
val it : seq<bigint> = seq [1I; 2I; 3I; 4I; ... ]

The default increment for range expressions is always 1. A different increment can be used via range expressions of the form seq { n .. skip .. m }:

> seq { 1 .. 2 .. 5 };;
val it : seq<int> = seq [ 1; 3; 5 ]

> seq { 1 .. −2 .. −5 };;
val it : seq<int> = seq [ 1; −1; −3; −5 ]

If the skip causes the final element to be overshot, then the final element isn't included in the result:

> seq { 0 .. 2 .. 5 };;
val it : seq<int> = seq [ 0; 2; 4 ]

The (..) and (.. ..) operators are overloaded operators in the same sense as (+) and (-), which means their behavior can be altered for user-defined types. Chapter 6 discusses this in more detail.

You can iterate sequences using the for ... in ... do construct, as well as the Seq.iter aggregate operator discussed in the next section. Here is a simple example of the first:

> let range = seq {0 .. 2 .. 6};;
val range : seq<int>

> for i in range do
      printfn "i = %d" i;;
i = 0
i = 2
i = 4
i = 6

This construct forces the iteration of the entire seq. Use it with care when you're working with sequences that may yield a large number of elements.

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

> let range = seq {0 .. 10};;
val range : seq<int>

> range |> Seq.map (fun i -> (i,i*i));;
val it : seq<int * int> = seq [ (0, 0); (1, 1); (2, 4); (3, 9) ... ]

Table 3-13 shows some important functions in this library module. The following operators necessarily evaluate all the elements of the input seq immediately:

Most of the other operators in the Seq module return one or more seq<type> values and force the computation of elements in any input seq<type> values only on demand.

Table 3-13 includes many uses of types such as seq<'T>. When a type appears as the type of an argument, the function accepts any value that's compatible with this type. Chapter 5 explains the notions of subtyping and compatibility in more detail; the concept should be familiar to OO programmers because it's the same as that used by other .NET languages such as C#, which itself is close to that used by Java. In practice, you can easily discover which types are compatible with which by using F# Interactive and tools such as Visual Studio: when you hover over a type name, the compatible types are shown. You can also refer to the online documentation for the F# libraries and the .NET Framework, which you can easily search using the major search engines.

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

The following types aren't directly type compatible with seq<'T> but can be converted readily into sequences when needed:

Expressions of the form for pat in seq are described in the section "Using Sequence Expressions" and in Chapter 4.

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

open System.IO
let rec allFiles dir =
    Seq.append
        (dir |> Directory.GetFiles)
        (dir |> Directory.GetDirectories |> Seq.map allFiles |> Seq.concat)

This gives the following type:

val allFiles : string -> seq<string>

Here is an example of the function being used on one of our machines:

> allFiles @"c:WINDOWSsystem32";;
val it : seq<string> =
       = seq ["c:\WINDOWS\system32\$winnt$.inf";
              "c:\WINDOWS\system32\12520437.cpx";
              "c:\WINDOWS\system32\12520850.cpx";
              "c:\WINDOWS\system32\6to4svc.dll"; ...]

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

One subtlety with programming with on-demand or lazy values like sequences is that side effects such as reading and writing from an external store shouldn't in general happen until the lazy sequence value is consumed. For example, the previousallFiles function reads the top-level directory C: as soon as allFiles is applied to its argument. This may not be appropriate if the contents of C: are changing. You can delay the computation of the sequence by using the library function Seq.delay or by using a sequence expression, covered in the next section, where delays are inserted automatically by the F# compiler.

The simplest form of a sequence expression is seq { for value in expr .. expr -> expr }. Here, -> should be read "yield." This is a shorthand way of writing Seq.map over a range expression. For example, you can generate an enumeration of numbers and their squares as follows:

> let squares = seq { for i in 0 .. 10 -> (i,i*i) };;
val squares : seq<int * int>

> squares;;
val it : seq<int * int> = [ (0,0); (1,1); (2,4); (3,9); ... ]

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

> seq { for (i,iSquared) in squares -> (i,iSquared,i*iSquared) };;
val it : seq<int * int * int> = [ (0,0,0); (1,1,1); (2,4,8); (3,9,27); ... ]

The input seq can be a seq<type> or any type supporting a GetEnumerator method. (The latter is supported because some important types from the .NET libraries support this method without directly supporting the seq interface.)

A sequence expression often begins with for ... in ..., but you can use additional constructs. For example:

Secondary iterations generate additional sequences, all of which are collected and concatenated together. Filters let you skip elements that don't satisfy a given predicate. To see both of these in action, the following computes a checkerboard set of coordinates for a rectangular grid:

let checkerboardCoordinates n =
   seq { for row in 1 .. n do
             for col in 1 .. n do
                 if (row+col) % 2 = 0 then
                     yield (row,col) }

> checkerboardCoordinates 3;;
val it : seq<(int * int)> = seq [(1, 1); (1, 3); (2, 2); (3, 1); ...]

Using let clauses in sequence expressions allows you to compute intermediary results. For example, the following code gets the creation time and last-access time for each file in a directory:

let fileInfo dir =
    seq { for file in Directory.GetFiles dir do
              let creationTime = File.GetCreationTime file
              let lastAccessTime = File.GetLastAccessTime file
              yield (file,creationTime,lastAccessTime) }

In the previous examples, each step of the iteration produces zero or one result. The final yield of a sequence expression can also be another sequence, signified through the use of the yield! keyword. The following sample shows how to redefine the allFiles function from the previous section using a sequence expression. Note that multiple generators can be included in one sequence expression; the results are implicitly collated together using Seq.append:

let rec allFiles dir =
    seq { for file in Directory.GetFiles dir do
              yield file
          for subdir in Directory.GetDirectories dir do
              yield! allFiles subdir }

You can also use range and sequence expressions to build list and array values. The syntax is identical, except the surrounding braces are replaced by the usual [ ] for lists and [| |] for arrays (Chapter 4 discusses arrays in more detail):

> [ 1 .. 4 ];;
val it: int list = [ 1; 2; 3; 4 ]

> [ for i in 0 .. 3 -> (i,i*i) ];;
val it : (int * int) list = [ (0,0); (1,1); (2,4); (3,9) ]

> [| for i in 0 .. 3 -> (i,i*i) |];;
val it : (int * int) [] = [ (0,0); (1,1); (2,4); (3,9) ]

Type abbreviations are the simplest type definitions:

type index = int
type flags = int64
type results = string * TimeSpan * int * int

It's common to use lowercase names for type abbreviations, but it's certainly not compulsory. Type abbreviations can be generic:

type StringMap<'T> = Microsoft.FSharp.Collections.Map<string,'T>
type Projections<'T,'U> = ('T -> 'U) * ('U -> 'T)

Type abbreviations aren't concrete, because they simply alias an existing type. They're expanded during the process of compiling F# code to the format shared between multiple .NET languages. The difference can, for example, be detected by other .NET languages; because of this, a number of restrictions apply to type abbreviations. For example, you can't augment them with additional members, as can be done for concrete types such as records, discriminated unions, and classes. In addition, you can't truly hide a type abbreviation using a signature (see Chapter 7).

The simplest concrete type definitions are records. Here's an example:

type Person =
    { Name: string;
      DateOfBirth: System.DateTime; }

You can construct record values by using the record labels:

> { Name = "Bill"; DateOfBirth = new System.DateTime(1962,09,02) };;
val it : Person = { Name="Bill"; DateOfBirth = 09/02/1962 }

Should there be a conflict between labels among multiple records, you can also construct record values by using an explicit type annotation:

> ({ Name = "Anna"; DateOfBirth = new System.DateTime(1968,07,23) } : Person);;
val it : Person = { Name="Anna"; DateOfBirth = 23/07/1968 }

Record values are often used to return results from functions:

type PageStats =
    { Site: string;
      Time: System.TimeSpan;
      Length: int;
      NumWords: int;
      NumHRefs: int }

This technique works well when returning a large number of heterogeneous results:

let stats site =
    let url = "http://" + site
    let html,t = time (fun () -> http url)
    let hwords = html |> getWords
    let hrefs = hWords |> List.filter (fun s -> s = "href")
    { Site=site; Time=t; Length=html.Length;
      NumWords=hwords.Length; NumHRefs=hrefs.Length }

Here is the type of stats:

val stats  : string -> PageStats

Here is how F# Interactive shows the results of applying the function:

> stats "www.live.com";;
val it : PageStats = { Site="www.live.com"; Time=0.872623628;
                       Length=7728, NumWords=1156; NumHRefs=10; }

Record labels need not be unique among multiple record types. Here is an example:

type Person =
    { Name: string;
      DateOfBirth: System.DateTime; }

type Company =
    { Name: string;
      Address: string; }

When record names are non-unique, constructions of record values may need to use object expressions in order to indicate the name of the record type, thus disambiguating the construction. For example, consider the following type definitions:

type Dot = { X: int; Y: int }
type Point = { X: float; Y: float }

On lookup, record labels are accessed using the dot (.) notation in the same way as properties. One slight difference is that in the absence of further qualifying information, the type of the object being accessed is inferred from the record label. This is based on the latest set of record labels in scope from record definitions and uses of open. For example, given the previous definitions, you have the following:

> let coords1 (p:Point) = (p.X,p.Y);;
val coords1 : Point -> float * float

> let coords2 (d:Dot) = (d.X,d.Y);;
val coords2 : Dot -> int * int

> let dist p = sqrt (p.X * p.X + p.Y * p.Y);; // use of X and Y implies type "Point"
val dist : Point -> float

The accesses to the labels X and Y in the first two definitions have been resolved using the type information provided by the type annotations. The accesses in the third definition have been resolved using the default interpretation of record field labels in the absence of any other qualifying information.

Records support a convenient syntax to clone all the values in the record, creating a new value with some values replaced. Here is a simple example:

type Point3D = { X: float; Y: float; Z: float }
let p1 = { X=3.0; Y=4.0; Z=5.0 }

> let p2 = { p1 with Y=0.0; Z=0.0 };;
val p2 : Point3D

The definition of p2 is identical to this:

let p2 = { X=p1.X; Y=0.0; Z=0.0 }

This expression form doesn't mutate the values of a record, even if the fields of the original record are mutable.

The second kind of concrete type definition discussed in this section is a discriminated union. Here is a very simple example:

type Route = int
type Make = string
type Model = string
type Transport =
    | Car of Make * Model
    | Bicycle
    | Bus of Route

Each alternative of a discriminated union is called a discriminator. You can build values by using the discriminator much as if it were a function:

> let nick = Car("BMW","360");;
val nick : Transport

> let don = [ Bicycle; Bus 8 ];;
val don  : Transport list

> let james = [ Car ("Ford","Fiesta"); Bicycle ];;
val james  : Transport list

You can also use discriminators in pattern matching:

let averageSpeed (tr: Transport) =
    match tr with
    | Car _ -> 35
    | Bicycle -> 16
    | Bus _ -> 24

Several of the types you've already met are defined as discriminated unions. For example, the 'T option type is defined as follows:

type 'T option =
    | None
    | Some of 'T

Discriminated unions can include recursive references (the same is true of records and other type definitions). This is frequently used when representing structured languages via discriminated unions, a topic covered in depth in Chapter 9:

type Proposition =
    | True
    | And of Proposition * Proposition
    | Or of Proposition * Proposition
    | Not of Proposition

Recursive functions can be used to traverse such a type. For example:

let rec eval (p: Proposition) =
    match p with
    | True -> true
    | And(p1,p2) -> eval p1 && eval p2
    | Or (p1,p2) -> eval p1 || eval p2
    | Not(p1) -> not (eval p1)

The F# type of immutable lists is defined in this way:

type 'T list =
    | ([])
    | (::) of 'T * 'T list

A broad range of tree-like data structures are conveniently represented as discriminated unions. For example:

type Tree<'T> =
    | Tree of 'T * Tree<'T> * Tree<'T>
    | Tip of 'T

You can use recursive functions to compute properties of trees:

let rec size tree =
    match tree with
    | Tree(_,l,r) -> 1 + size l + size r
    | Tip _ -> 1

Here is the inferred type of size:

val size : Tree<'T> -> int

Here is an example of a constructed tree term and the use of the size function:

> let small = Tree("1",Tree("2",Tip("a"),Tip("b")),Tip("c"));;
val small : Tree<string>

> small;;
val it : Tree<string> = Tree ("1",Tree ("2",Tip("a"),Tip("b")),Tip("c"))

> size small;;
val it : int = 5

Chapters 8, 9, and 12 discuss symbolic manipulation based on trees.

Discriminated union types with only one data tag are an effective way to implement record-like types:

type Point3D = Vector3D of float * float * float
let origin = Vector3D(0.,0.,0.)
let unitX  = Vector3D(1.,0.,0.)
let unitY  = Vector3D(0.,1.,0.)
let unitZ  = Vector3D(0.,0.,1.)

These are particularly effective because they can be decomposed using succinct patterns in the same way as tuple arguments:

let length (Vector3D(dx,dy,dz)) = sqrt(dx*dx+dy*dy+dz*dz)

This technique is most useful for record-like values where there is some natural order on the constituent elements of the value (as shown earlier) or where the elements have different types.

Multiple types can be declared together to give a mutually recursive collection of types, including record types, discriminated unions, and abbreviations. The type definitions must be separated by the keyword and:

type Node =
    { Name : string;
      Links : Link list }
and Link =
    | Dangling
    | Link of Node