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.

Type Inference

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 okay, 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.

let aString = "Spring time in Paris"

let anInt = 42

val aString : string

val anInt : int

The types of these two identifiers are unsurprising—string and int, respectively. 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.

The definition of the function makeMessage in the next example is a little more interesting.

let makeMessage x = (Printf.sprintf "%i" x) + " days to spring time"

let half x = x / 2

val makeMessage : int -> string

val half : int -> int

Note that the makeMessage function’s definition is prefixed with the keyword val, just like the two values you saw before; even though it is a function, the F# compiler still considers it to be a value. Also, the type itself uses the notation int -> string, meaning a function takes an integer and returns a string. The -> (ASCII arrow) between the type names represents the transformation of the function being applied. 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.

The types of functions that can be partially applied and functions that take tuples differ. The following functions, div1 and div2, illustrate this.

let div1 x y = x / y

let div2 (x, y) = x / y

let divRemainder x y = x / y, x % y

val div1 : int -> int -> int

val div2 : int * int -> int

val divRemainder : int -> int -> int * int

The function div1 can be partially applied, and its type is int -> int -> int, representing that the arguments can be passed in separately. Compare this with the function div2, which 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.

The next function, doNothing, looks inconspicuous enough, but it is quite interesting from a typing point of view.

let doNothing x = x

val doNothing : 'a -> 'a

This function has the type 'a -> 'a, meaning it 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 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 that, even though the compiler 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.

Note: The concept of a variable type, or type parameterization, is closely related to the concept of generics that were introduced in CLR version 2.0 and have now become part of the ECMA specification for 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. Don Syme, the creator of F#, designed and implemented generics in the .NET CLR before he started working on F#. One might be tempted to infer that he did this so he could create F#!

The function doNothingToAnInt, shown in the next sample, is an example of a value being constrained—a type constraint. In this case, the function parameter x is constrained to be an int. It is possible to constrain any identifier, not just function parameters, to be of a certain type, though it is more typical to need to constrain parameters. The list stringList here shows how to constrain an identifier that is 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 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.

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 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 undetermined types. You can place the type between angle brackets after the type 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.

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 cases, the compiler has less type information, so it is often necessary to give it enough information to disambiguate values.

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:

• Tuples or records, which are a set of types composed to form a composite type (similar to structs in C or classes in C#).
• Sum types, sometimes referred to as union types.

Tuple and Record 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 equal 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.

let pair = true, false

let b1, _ = pair

let _, b2 = pair

Tuples are different from most user-defined types in F# because you do not need to explicitly declare them using the type keyword. To define a type, you use the type keyword, followed by the type name, an equal 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.

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.

// Define an organization with unique fields.

type Organization1 = { boss: string; lackeys: string list }

// Create an instance of this organization.

let rainbow =

    { boss = "Jeffrey";

      lackeys = ["Zippy"; "George"; "Bungle"] }

// Define two organizations with overlapping fields.

type Organization2 = { chief: string; underlings: string list }

type Organization3 = { chief: string; indians: string list }

// Create an instance of Organization2.

let (thePlayers: Organization2) =

    { chief = "Peter Quince";

      underlings = ["Francis Flute"; "Robin Starveling";

                    "Tom Snout"; "Snug"; "Nick Bottom"] }

// Create an instance of Organization3.

let (wayneManor: Organization3) =

    { chief = "Batman";

      indians = ["Robin"; "Alfred"] }

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 equal signs and the field values between braces ({}), as shown in the Rainbow identifier.

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 such a case, the compiler cannot infer the type of the record. To create records with nonunique fields, the compiler needs to statically know the type of the record being created. If the compiler cannot infer the type of the record, you need to use a type annotation as described in the Type Inference section. Using a type annotation is illustrated by the types Organization2 and Organization3, and their instances thePlayers and wayneManor. You can see the type of the identifier given explicitly just after its name.

Accessing the fields in a record is fairly straightforward. You simply use the syntax record identifier name, followed by a dot, followed by field name. The following example illustrates this, showing how to access the chief field of the Organization record.

// Define an organization type.

type Organization = { chief: string; indians: string list }

// Create an instance of this type.

let wayneManor =

    { chief = "Batman";

      indians = ["Robin"; "Alfred"] }

// Access a field from this type.

printfn "wayneManor.chief = %s" wayneManor.chief

Records are immutable by default. To an imperative programmer, this may sound like records are not very useful, since there will inevitably be situations where you need to change a value in a field. For this purpose, F# provides a simple syntax for creating a copy of a record with updated fields. To create a copy of a record, place the name of that record between braces followed by the keyword with, and then followed by a list of fields to be changed with their updated values. The advantage of this is that you don’t need to retype the list of fields that have not changed. The following example demonstrates this approach. It creates an initial version of wayneManor and then creates wayneManor', in which "Robin" has been removed.

// Define an organization type.

type Organization = { chief: string; indians: string list }

// Create an instance of this type.

let wayneManor =

    { chief = "Batman";

      indians = ["Robin"; "Alfred"] }

// Create a modified instance of this type.

let wayneManor' =

    { wayneManor with indians = [ "Alfred" ] }

// Print out the two organizations.

printfn "wayneManor = %A" wayneManor

printfn "wayneManor' = %A" wayneManor'

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

wayneManor = {chief = "Batman";

 indians = ["Robin"; "Alfred"];}

wayneManor' = {chief = "Batman";

 indians = ["Alfred"];}

Another way to access the fields in a record is using pattern matching; that is, you can use pattern matching to match fields within the record type. 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. You can ignore a field with field = _. The findDavid function in the following example illustrates using pattern matching to access the fields in a record.

// Type representing a couple.

type Couple = { him : string ; her : string }

// List of couples.

let couples =

    [ { him = "Brad" ; her = "Angelina" };

      { him = "Becks" ; her = "Posh" };

      { him = "Chris" ; her = "Gwyneth" };

      { him = "Michael" ; her = "Catherine" } ]

   

// Function to find "David" from a list of couples.

let rec findDavid l =

    match l with

    | { him = x ; her = "Posh" } :: tail -> x

    | _ :: tail -> findDavid tail

    | [] -> failwith "Couldn't find David"

// Print the results.

printfn "%A" (findDavid couples)

The first rule in the findDavid function is the one that does the real work, checking 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.

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

Becks

It’s important to note that you can use only literal values when you pattern match over records like this. So, if you wanted to generalize the function to allow you to change the person you are searching for, you would need to use a when guard in your pattern matching:

let rec findPartner soughtHer l =

    match l with

    | { him = x ; her = her } :: tail when her = soughtHer -> x

    | _ :: tail -> findPartner soughtHer tail

    | [] -> failwith "Couldn't find him"

// Print the results.

printfn "%A" (findPartner "Angelina" couples )

Field values can also be functions, which can occasionally be useful to provide object-like behavior as each record instance of the record could have a different implementation of the function.

Union or Sum Types

Union types, sometimes called sum types or discriminated unions, are a way of bringing together data that may have a different meaning or structure.

You define a union type using the type keyword, followed by the type name, followed by an equal sign—the same as with all type definitions. Next are the definitions of the different constructors separated by pipes. The first pipe is optional.

A constructor is composed of a name that must start with a capital letter, which is intended to avoid 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 is possible that further type annotations are required when constructing and consuming union types.

The next example defines a type Volume whose values can have three different meanings: liter, US 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.

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)

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.

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 the list is incomplete, 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 convertVolumeToLiter, convertVolumeUsPint, and convertVolumeImperialPint functions demonstrate this syntax:

// Type representing volumes.

type Volume =

    | Liter of float

    | UsPint of float

    | ImperialPint of float

// Various kinds of volumes.

let vol1 = Liter 2.5

let vol2 = UsPint 2.5

let vol3 = ImperialPint 2.5

// Some functions to convert between volumes.

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

// A function to print a volume.

let printVolumes x =

    printfn "Volume in liters = %f,

in us pints = %f,

in imperial pints = %f"

        (convertVolumeToLiter x)

        (convertVolumeUsPint x)

        (convertVolumeImperialPint x)

// Print the results.

printVolumes vol1

printVolumes vol2

printVolumes vol3

An alternative solution to this problem is to use F#’s units of measure, which allow types to be applied to numeric values.

Type Definitions with Type Parameters

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 more explicit about which types are variable.

To create a type parameter or parameters, place the types being parameterized in angle brackets after the type name, as follows:

type BinaryTree<'a> =

| BinaryNode of 'a BinaryTree * 'a BinaryTree

| BinaryValue of 'a

let tree1 =

    BinaryNode(

        BinaryNode ( BinaryValue 1, BinaryValue 2),

        BinaryNode ( BinaryValue 3, BinaryValue 4) )

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 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 their consumption by the function printBinaryTreeValues:

// Definition of a binary tree.

type BinaryTree<'a> =

    | BinaryNode of 'a BinaryTree * 'a BinaryTree

    | BinaryValue of 'a

// Create an instance of a binary tree.

let tree1 =

    BinaryNode(

        BinaryNode ( BinaryValue 1, BinaryValue 2),

        BinaryNode ( BinaryValue 3, BinaryValue 4) )

// Function to print the binary tree.

let rec printBinaryTreeValues x =

    match x with

    | BinaryNode (node1, node2) ->

        printBinaryTreeValues node1

        printBinaryTreeValues node2

    | BinaryValue x ->

        printf "%A, " x

       

// Print the results.

printBinaryTreeValues tree1

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

1, 2, 3, 4,

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. 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.

Summary

This has been a brief tour of how to create types in F#. You’ll find that F#’s type system provides a flexible way to represent data in your programs.